백준30 [알고리즘] 어른 상어 (백준 19237번) 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 시뮬레이션으로 악명 높은 삼성 기출 문제다. 삼성은 맵 위에 물체들이 동시에 움직이는 시뮬레이션 문제를 좋아하는 것 같다. 저번에도 몇 번 삼성 익스퍼트 아카데미에서 비슷한 부류의 문제를 본 적이 있다. 각 물체들의 동작이 서로 비동기적으로 일어나는 것을 표현해줘야 하기에 생각보다 어렵다. Solution 1. 전역 변수들 lateinit var map : Array lateinit var sharkList : List.. 2020. 9. 22. [알고리즘] 아기상어 (백준 16236번) 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 예전에 푼 적이 있는 문제임에도 생각보다 시간이 더 오래 걸렸다. 그것도 예전에 풀었던 솔루션보다 시간이 더 길게 나오더라..;; BFS + 시뮬레이션 방식의 문제이다. N의 범위가 작아서 시간초과 걱정없이 풀 수 있는 문제이다. Solution fish_count : map에 있는 총 물고기의 수. queue에 맨 처음 상어 위치를 넣는다. fish_count가 1마리 이상 있으면 계속 반복문 진행 bfs 탐색 시작 현재 위치에서 최단 거리에 있는 먹.. 2020. 9. 17. [알고리즘] 벽 부수고 이동하기 (백준 2206번) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 지도의 끝까지 이동할 때의 최단 경로를 구하는 BFS 문제이다. 다만 벽을 1개까지 부수고 이동할 수 있다는 조건이 있다. 만약에 브루트 포스로 구한다고 가정해보자. 모든 경우의 수를 따지려면 맵의 벽의 개수 만큼 BFS를 돌려야 하는데 한 번 BFS를 돌릴 때 최악의 연산 횟수가 3백만번 정도된다. (O(V+E) = 1000 * 1000 + 1000 * 999 + 1000 * 999) 거기에 벽의 개수 최악의 경우 NM개를 곱하게 .. 2020. 9. 3. [알고리즘] 숫자 카드 2 (백준 10816번) 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 이분탐색이라 쉬울 줄 알았는데 중복된 수를 허용하기 때문에 처음 만나보는 유형이었다. 사실 HashMap으로 풀면 그만이지만 너무 쉬운거 보단 그래도 이분탐색으로 풀어보고 싶어서 해봤는데 계속 시간 초과가 나서 결국 질문을 보아하니 lowerBound와 upperBound를 사용해야 한다고 한다. Solution 1) HashMap 사용 그냥 입력 받는 값들을 key값으로 HashMap에 저장하고 value는 해당 key의 개수를.. 2020. 9. 1. 이전 1 2 3 4 5 6 7 8 다음
