문제 https://www.acmicpc.net/problem/18234 18234번: 당근 훔쳐 먹기 첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다. 다음 N개의 줄에 걸쳐서 i+1번째 www.acmicpc.net 풀이 "당근을 먹지 않을 수도 있다"와 "항상 w
문제 https://programmers.co.kr/learn/courses/30/lessons/64061 코딩테스트 연습 - 크레인 인형뽑기 게임 [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] [1,5,3,5,1,2,1,4] 4 programmers.co.kr 풀이 문제의 설명이 아주 친절하기 때문에 그대로 풀면되는 간단한 구현 문제였다. 이중 for문을 통해 해당 열의 가장 위에 있는 인형을 확인한다. 이 과정에서 기존 스택의 가장 위에 있는 인형(basket.peek( ))과 가장 위에 있는 인형(value)을 비교해서 동일하다면 스택에 있는 인형을 제거하고, 아니라면 인형을 스택에 넣는다. 이때, 스택에 먼저 인형을 하나 넣음으로써 ..
문제 https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 풀이 정렬을 통해 해결할 수 있는 문제였다. 내림차순으로 정렬된 리스트가 하나 있다고 가정해보자. List = [L1, L2, L3, ... , Ln] (L1 > L2 >L3 > ... > Ln) L1을 기준으로 차이가 가장 적게 나는 원소 2개는 L2와 L3일 것이다. 마찬가지로 L2가 기준이라면 L3, L4일 것이고, 이는 계속해서 반복된다. 또한, 내림차순으로 정렬되어 있기 때문에 당..
문제 https://www.acmicpc.net/problem/2668 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 풀이 윗줄에서 1, 3, 5를 뽑으면 첫째 줄과 둘째 줄에서 동일한 집합을 만들어낼 수 있다. 여기서 생각해볼 수 있는 것은 결국 다른 것들은 고려할 필요없이 첫째 줄과 둘째 줄에서 같은 열에 놓이는 대응되는 숫자들이 중요하다는 것이다! 여기서 좀 더 추상화를 해보자. 위의 표를 둘째 줄의 노드가 윗줄의 노드를 가리키고 있는 한 방향 그래프로 바꾸어 생각해보면, 다음과 같은 연결..
문제 https://www.acmicpc.net/problem/2660 2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 풀이 그래프 탐색 문제였다. 각 노드를 기준으로 모든 노드에 대해 거리를 구해주는 문제였다. 모든 노드에 대해 거리를 구한다는 점에서 플로이드-와샬 알고리즘을 적용해서 푸는 방법도 있지만, 나는 BFS를 이용해서 풀었다. 언뜻 보면 복잡해보이지만, 아주 간단하다. 매 탐색시마다 visited를 초기화시키고, 인접한 노드를 방문할 때마다 거리를 기록해주면 된다. 별개의 리스트를 이용할 수도 있..
