모바일 개발하는 자바리안의 메모장

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 유호석 강사님의 알고리즘 강의 중, 투포인터를 배우며 접한 예제 문제. 두개의 포인터를 활용하여 [정답을 찾기 위해 봐야 하는 것들]에 접근할 수 있는 알고리즘이다. 즉, 답을 구하기 위한 정말 필요한 데이터에만 접근하여 전체적인 탐색범위를 크게 압축할 수 있는 알고리즘이다. 이번 예제는 주어진 수열에서 L(eft), R(ight) 두 포인터를 활용하여, 확인한 범위를 줄이고 늘리며..

https://programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 완전탐색으로 풀었다가 효율성 테스트에서 좌절,, 풀이를 찾다가 Trie라는 자료구조에 대해 처음 접할 수 있었다. Trie는 아래와 같이 Tree 형태로 String을 Character로 쪼개어 각 노드에 입력한다 : 새로운 문자열을 추가할 때마다 문자열에 포함된 Charcter 노드의 카운트수를 더해준다. 각 Query에서 ?가 위치한 바로 앞 Character 노드의 Count를 반환하여 답을 구할 수 있었다. 실행 순서는 다음과 같다 : 1. Trie와 Node 클레스 및 입력, Count 메소드 생성 2. 입력 문자열 & Reverse..

https://programmers.co.kr/learn/courses/30/lessons/60057 코딩테스트 연습 - 문자열 압축 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문 programmers.co.kr 카카오 코테를 준비하며 접한 문제,, 너무 긴장해서 그런가 문제가 잘 파악이 안되서 정확히 이해하기까지 시간이 많이 소요됐다.. 어떤 알고리즘으로 어떻게 효율적으로 쪼갤지 고민을 참 많이하게 한 문제,, 하지만,, 모든 문제를 시원하게 해결해 준 결정적 힌트는 문제 맨 마지막, 5번 예제 설명에 있었다.. '문자열은 제일 앞부터 정해진 길이만큼 잘라야 합..

https://programmers.co.kr/learn/courses/30/lessons/42839 코딩테스트 연습 - 소수 찾기 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 programmers.co.kr 재귀를 이용한 완전탐색으로 풀 수 있었던 문제. 문제를 보자마자 재귀를 통해 완전탐색을 구현해야 함은 알았으나,, 중복 문자를 제거해가며 모든 조합을 어떻게 효율적으로 만들 수 있을지 생각해보다가 substring을 사용. 소수 검증 로직은 몇몇가지 조건으로 예외 처리 후, 제곱근 값까지만 확인. 앞에 0이 붙은 문자열의 경우 int로 parsin..

https://programmers.co.kr/learn/courses/30/lessons/12913# 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr DP(동적 계획법)을 이용하여 풀 수 있었던 문제. 처음엔 정렬 문제일거라 생각했으나,, 각 행의 열이 다른 값들 중, 가장 큰 값을 다음 행에 더해나가며 정답을 구할 수 있었다. 실행 순서는 다음과 같다 : 1. input 첫번째 행부터 마지막 행까지 확인하며, 2. 다음 행의 c열에 현재 c 행이 아닌 3개의 값 중, 가장 큰 값을 더해..

https://programmers.co.kr/learn/courses/30/lessons/64061# 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 인형뽑기에서 뽑은 인형들을 바구니에 담았을 때, 마지막 담았던 인형이 방금 집어 넣은 인형과 같을 경우 터지게 되며, 터진 인형의 개수를 return하는 아주 간단한 문제. LIFO 자료구조, Stack을 이용하면 쉽게 풀 수 있다. 라고 생각하고 Submit 했지만, 몇몇 상황에 대한 예외처리가 필요했다. 실행 순서는 다음과 같다 : 1. 크레인을 내릴 위치가 담긴 moves 배열의 ..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr DFS 알고리즘을 사용하여 입력값의 덧,뺄셈에 대한 모든 결과값을 확인할 수 있었음. 재귀 함수를 구현하였으며, 각 연산에 대한 재귀호출 + 예외처리 + 정답에 대한 조건문만으로 쉽게 풀 수 있었던 문제. 실행 순서는 다음과 같다 : 1. 초기값을 넘겨 dfs 재귀함수 호출 2. 다음 index 값 & res..

https://programmers.co.kr/learn/courses/30/lessons/76503 코딩테스트 연습 - 모두 0으로 만들기 각 점에 가중치가 부여된 트리가 주어집니다. 당신은 다음 연산을 통하여, 이 트리의 모든 점들의 가중치를 0으로 만들고자 합니다. 임의의 연결된 두 점을 골라서 한쪽은 1 증가시키고, 다른 한 programmers.co.kr 생각했던것보다 아주 많이,, 오래 걸린 문제. 가중치를 어떻게 올바르게 카운트 할 수 있을지 너무 어렵게 생각했던 것 같다.. 반환값이 long인 부분을 고려하여 입력값을 long 타입으로 옮겨주는 작업, 그리고 아직도 왜 그런지 모르겠지만 변수화 여부에 따라 결과값이 다르게 나오던 문제를 해결하고나서야 겨우 All Pass를 받을 수 있었다...

https://programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 최단경로를 구해야하는 문제로, BFS알고리즘을 사용하여 풀 수 있었다. 딱히 꼬아놓은 내용이 없어서 어렵지 않게 풀 수 있었던 문제였다. 디버깅하며 예상한 방향으로 착하게 잘 움직이는 로봇을 보고 큰 희열을 느꼈던 문제 실행 순서는 다음과 같다 : 1. 방문을 체크하기 위한 배열, 거리를 계산해 줄 count..

https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 단순한 완전탐색 문제. 정해진 학생 수 + 반복되는 패턴을 배열로 만들어 쉽게 정답을 찾을 수 있었다. 실행 순서는 다음과 같다 : 1. 3명 수포자의 반복되는 패턴, 패턴의 사이즈, 정답 개수 카운터 배열로 정의 2. Input의 각 숫자를 확인하여 정답일 경우 카운터 값 증가 3. 정답 카운터 배열에서 가장 높은 점수 확인 4. 가장 높은 점수를 획득한 수포..