알고리즘 (179) 썸네일형 리스트형 [2019 KAKAO BLIND RECRUITMENT] 길 찾기 게임(Java, 간단한 코드) ## 접근 1. 주어진 노드의 x, y 좌표를 자료구조에 넣고 정렬한다. y는 내림차순으로, x는 오름차순으로 정렬한다. 정렬의 이유는 트리에 삽입하기 위해서다. 2. 루트 노드에서부터 시작하여, 노드를 넣기 위한 위치를 탐색한다. 노드의 x좌표를 기준으로, 작으면 왼쪽, 크면 오른쪽으로 탐색하다가, null을 만나면 삽입한다. 3. 전위순회와, 후위순회 코드를 작성할 때, 출력 부분을 이용해서 정답을 만든다. ## 해설코드(Java). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 5.. [2019 KAKAO BLIND RECRUITMENT] 무지의 먹방 라이브(Java) ## 접근 1. HashMap을 이용해서, 인덱스와 음식을 먹는데 소요되는 시간을 추가한다. 음식을 먹는데 소요되는 시간이 낮은 것부터 정렬한다. 2. 정렬된 키를 이용해서, 순차적으로 접근하며 k를 차감시킨다. k를 차감시킬 때, 식을 정확하게 세워야 한다. 또한, 다음 계산을 위해서 HashMap의 값들을 일일이 차감시키는 방식이 아니다. 계산이 이루어질때, 이전 가장 작은 값을 이용해서 k를 차감시킨다. * k = k - (남아있는 개수) * (현재 가장 작은 값 - 이전 가장 작은 값) 3. 만약, 차감 후에 값이 음수가 나온다면, 현재 존재하는 키들의 개수를 이용해서 순서를 찾으면 된다. ## 유의사항 1. Long의 형태이므로, 중간 과정에서 int로 값이 변환되지 않도록 주의해서 작성한다.(.. [2020 KAKAO BLIND RECRUITMENT] 기둥과 보 설치(Java, 간단한코드) ## 접근 1. 문제에서 준 조건 두 가지를 이용한다. 기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다. 보는 한쪽 끝 부분이 기둥 위에 있거나, 또는 양쪽 끝 부분이 다른 보와 동시에 연결되어 있어야 합니다. 2. 문제에서 제거 및 추가에 대해서, 특정한 맵에 반영하고 위의 조건 두 가지를 만족하는지 확인한다. ## 시행착오 1. 맵을 2차원 배열이 아닌, 기둥과 보를 각각 마크할 수 있는 3차원 배열을 해야한다. 왜냐면, 같은 위치에(x, y) 보와 배열이 설치될 수 있다. 2. if문과 else문 사용 시, 주의해야 한다. continue, break 사용 시에 주의해야 한다. 이것때문에 계속 틀렸었다. ## 해설코드 1 2 3 4 5 6 7 8 9 1.. [2020 KAKAO BLIND RECRUITMENT] 가사검색(Trie, Java, 효율성, 간단한 코드) ## 접근 - Trie의 add 연산은 간단하나, find 연산은 종료 조건을 분류 * "?" 만나서 종료하는 경우, 존재하지 않은 단어를 만날 경우 ## 효율성 - Reverse라는 메소드를 정의해서 사용했는데, 매번 += 연산을 통해서 concat 시켰는데 이게 효율성을 어긋나게 했다. - ReplaceAll으로 '?'를 대체하는 것대신 '?' 발견 시 종료하도록 코드 구성 ## 해설코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 .. [BOJ 14226] 이모티콘(Java, 간단한 코드, 런타임에러, 증명) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만�� www.acmicpc.net 이 문제를 Bottom-up으로 접근할 수 없다. 화면에 있는 이모티콘 중 하나를 삭제하기 때문에, 순차적인 접근이 이루어지기 어렵다. 1. Top-Down 방식으로 DP를 작성한다. DP의 매개변수는, 화면에 이모티콘 수와 클립보드 이모티콘 수로 2개를 사용한다. 2. BFS를 이용해서, 3가지 기능에 대해서 구현해주면 된다. 또한, 메모이제이션 기법을 통해서 중복을 제거해 시간복잡도를 줄이도.. [BOJ 12865] 평범한 배낭(Java, DP) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 1. 전체 물품을 이용해서, 제시된 K 무게까지의 최대 가치를 구해야 한다. 소문제로 나누어서 문제를 풀기 위해서, 두 가지 변수를 사용한다. 물품과 무게를 사용해서 DP를 구성한다. 2. DP의 점화식을 세워야 하는데, DP[i][j] = max(DP[i - 1][j] + DP[i - 1][j - i번째 물품 무게] + i번째 가.. [BOJ 1024] 수열의 합(Java, 단순한 풀이) https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 2가지 방법으로 풀이를 작성하겠다. # 풀이1(직관적이나 시간복잡도가 큼). 1. 길이가 L부터 100까지 탐색을 한다. While문 내에서 합을 L만큼 더해가면서, 합이 N을 만들 수 있는 모든 수를 탐색한다. 2. 합이 N이라면, 정답을 출력한다. 해설코드(Java). 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 .. [BOJ 1068] 트리(Java, 간단한 풀이, Set) https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 입력을 처리할 때, 각 노드의 부모 노드를 기억, 노드의 자식 노드들을 기억할 수 있도록 데이터를 저장하는 자료구조를 사용한다. 2. 제거해야하는 노드가 있으면, 부모 노드의 자식 노드에서 해당 노드를 지우고, 제거해야하는 노드와 연결된 노드들을 큐를 사용해 모두 체크한다. 3. 전체 노드들을 탐색하면서, 자식 노드가 0이며 제거햐아하는 노드와 연결되지 않은 것을 정답의 값에 추가한다... 이전 1 ··· 4 5 6 7 8 9 10 ··· 23 다음