[백준 / BOJ] 14442 벽 부수고 이동하기 2 (Java)
문제 출처 : https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다. 벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다. 풀이 BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다. 체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부..
[programmers/kakao] 징검다리 건너기
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/64062?language=java 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 징검다리에 돌이있다. 이 돌에는 밟을수있는 횟수가 정해져있으며, 한번 밟을때마다 횟수가 줄어든다. 또한, 징검다리를 건너뛸수있는 최대 길이 k 가 주어진다. 한 사람이 징검다리를 한번 건널때 밟을 수 있는 모든 돌을 밟는다 했을때, 최대 몇명의 사람이 징검다리를 건널 수 있는지 구하는 문제다. 문제를 읽어보면, "밟을 수 없는돌의 연속길이가 k가 되는지점"을 구하는 문제임을 알수있다. 징검다리의 길이가 200,000 이기때문에, 완전탐색..
[programmers/kakao] [3차] 압축 (Java/Trie)
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 알파벳 'A' - 'Z'로 이루어진 사전과 문자열 msg가 주어진다. 이 msg의 문자중 사전과 최장 일치하는 문자를 찾고, 문자열이 일치하지않는다면, 사전에 추가하며, 일치하는 문자열의 Index(색인 번호)를 출력하는 문제다. 풀이 우선 이 문제에서 msg의 길이는 최대 1,000이다. 완전탐색으로 구현할 경우, 최악의 경우는 (아마)다음과 같을것 이다. msg : ..
[programmers/kakao] [3차] 자동완성 (Java)
문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/17685?language=java 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g programmers.co.kr 검색어 자동완성 기능을 만들고, 모든 문자를 찾기위해서 최소 몇번 타이핑해야하는지 찾는 문제다. 풀이 전형적인 Trie 문제였다 모든 단어의 길이를 합쳤을때 최대 1,000,000길이가 나오니 Trie 구조를 만드는데, 1,000,000번 반복하며, 모든 단어의 길이의 합이 최대 1,000,000 이므로 ..
