알고리즘(w.KOTLIN) (97) 썸네일형 리스트형 [알고리즘] 에라토스테네스의 체 정의 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 에라토스테네스 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 에라토스테네스(Ερατοσθένης, 기원전 274년 ~ 기원전 196년)는 고대 그리스의 수학자이자 천문학자이다. 헬레니즘 시대 이집트에서 활약했으며, 문헌학 및 ko.wikipedia.org 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기.. [백준][코틀린][6087] 레이저 통신 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 문제 풀이 1. 현재 위치(x, y), 현재 거울 개수, 레이저 방향을 저장하는 Laser Data Class 를 만든다. 2. 주어진 입력에서 C 지점을 laserArea 에 저장한다. 3. laserArea[0] 의 값을 시작으로 BFS 를 수행한다. 4. Queue 에는 1번에서 만든 Laser Class 를 넣고 초기 값으로는 3번에서 찾은 값을 넣는다. 이때 거울 개수를 -1 로.. [백준][16236] 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 풀이 1. 입력은 2차원 배열의 map 에 저장한다. 2. 상어의 위치를 찾고 상어가 이동하기 때문에 상어 위치의 값을 0으로 변경한다. 3. 처음 상어의 위치에서 잡아 먹을 수 있는 물고기를 모두 탐색한다.(상어 정보를 저장하는 queue 를 선언한다.) 4. 3번과정에 잡아 먹은 물고기를 eatenFish queue 에 저장한다. 5. eatenFish 가 비어 있을 경우 현재까지.. [백준][코틀린][16954] 움직이는 미로 탈출 https://www.acmicpc.net/problem/16954 16954번: 움직이는 미로 탈출 욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 www.acmicpc.net 문제 풀이 1. 벽돌 정보를 wall 배열에 저장한다. 2. (7, 0) 을 시작으로 하는 bfs 탐색을 수행한다. 3. 이때 같은 Level 의 Queue 를 순회하고 난 뒤 벽이 이동되기 때문에 새로운 벽의 위치에 대한 BFS 를 수행하는 것으로 간주한다. 4. 그러므로 방문배열을 확인하는 visit 배열도 Level 이 변경될 때 새롭게 초기화해서 방문 배열을 사용한다. 5. 마지.. [백준][코틀린][16946] 벽 부수고 이동하기 4 https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 문제 풀이 1. 주어진 문제를 전체 탐색을 하면서 벽을 하나씩 부수고 BFS 를 수행할 경우 시간 초과가 발생한다. O(N^2 * M^2) 2. BFS 를 수행할 때 이동이 가능한 영역(0)에 대해서 그룹화하여 각 그룹의 개수를 저장한다. 3. 각 그룹의 개수를 저장하는 groupMap 을 선언한다. 4. 결과를 출력한다. 이때 N, M 만큼 탐색하여 map[X][Y] 가 1.. [백준][코틀린][16933] 벽 부수고 이동하기 3 https://www.acmicpc.net/problem/16933 16933번: 벽 부수고 이동하기 3 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 풀이 1. BOJ14442 번에서 낮과 밤의 조건이 추가된 문제이다. 2. 처음 접근시 BOJ14442 에서 방문 여부를 확인하는 3중 visit 배열에서 마지막에 낮/밤을 확인하는 배열을 추가하여 4중 배열로 선언했다. 3. 4중 배열로 선언할 경우 결과가 메모리 초과가 발생한다. 4. 3중 배열로 선언하고 낮과 밤에 대한 조건에 대해서 벽을 만나고 밤일.. [백준][코틀린][14442] 벽 부수고 이동하기 2 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 문제 풀이 1. BOJ 2206 과 매우 유사한 문제 이다. 2. 다른 점은 2206 과 달리 벽을 부술 수 있는 개수가 입력으로 주어진다. 3. 따라서 BOJ2206 풀이 visit 배열을 3중 배열로 선언하는 부분을 조건에 맞게 변경한다. 0th Index : 벽을 부순 개수, 1st Index : 현재 위치 X 좌표, 2nd Index : 현재 위치 Y좌표.. [백준][KOTLIN][2206] 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 풀이 1. 이중 for 문을 이용하여 벽을 하나씩 부순 후 bfs 를 탐색할 경우 시간 초과가 발생한다. 2. bfs 탐색시 visit 방문 배열을 3중 배열로 선언한다. 1st Index : N, 2nd Index : M, 3rd Index : 벽돌 부순 유무 3. 처음 시작 지점(1, 1) 은 벽돌 부순 유무를 모두 true 로 설정한다. 4. queue 에는 현.. 이전 1 2 3 4 5 6 7 ··· 13 다음
