본문 바로가기

Algorithm76

[알고리즘] 순위 (프로그래머스 Level3) 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 그래프 탐색 문제이다. 순위라고 했으므로 현재 그래프 내에서의 각 노드들의 위치를 알아내야 하는 문제이다. 즉, 각 선수마다 해당 선수보다 강한 선수 + 약한 선수의 수를 구해서 합쳐서 n이 된다면 랭킹을 정확하게 구할 수 있는 선수이다. 예전에도 비슷한 문제를 풀어본 기억이 있는데 'DFS + 역그래프 + DP + Set'을 적절히 활용하면 쉽게 풀 수 있다. Solution 예시 input을 단방향 그래프로 그린 모습이다. 보다시피 2번 선수 뒤에는 1, 3, 4번, 앞에는 5번 선수가 있으므로 다른 모든 선수와의 관계를 명확히 할 수 있다. 5번 또한 본인 뒤에 .. 2020. 9. 7.
[알고리즘] 등굣길 (프로그래머스 Level3) 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 문제 그림만 봐도 느껴지겠지만 탐색 문제이다. 다만 문제에서 최단 경로라고 언급을 했으니 BFS를 이용하기로 했다. 하지만 Level3 문제답게 단순한 BFS 문제는 아니다. 단순히 '최단 경로' 만 구하라고 한 것이 아니라 '최단 경로의 개수'를 구하라고 했다. 즉 특정 노드를 기준으로 그곳에 도착한 경로들의 개수들을 세어야 하고 이것은 동적 프로그래밍을 이용해서 메모이제이션해야한다. 즉 BFS + DP 문제이다. (추후에 알게된 사실인데 BFS도 .. 2020. 9. 7.
[알고리즘] 벽 부수고 이동하기 (백준 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.

티스토리툴바