https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 난이도 : 실버 1 태그 : 다이나믹 프로그래밍 설명 다이나믹 프로그래밍을 응용할 수 있겠는데요. XXXX7 라는 계단 수를 만들려면, 바로 직전 계단수는 뭘까요? 바로 XXX6, XXX8 입니다. 직전 값과 1만큼 차이가 나면 되는 것이죠. 즉, XXXX7이 될 수 있는 경우의 수는 XXX6의 경우의 수와 XXX8의 경우의 수를 더한 것과 같습니다. XXXX7는 5자리, 현재 값은 8 입니다. 이를 dp[자리 수(i)][값(j)] 으로 나타내면, dp[i][j] = dp[i-1][j-1] + dp[i-1][j..

https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1 ≤ N ≤ 1,000)과 도로의 개수 M(1 ≤ M ≤ N(N-1)/2) 이 주어진다. 입력의 두 번 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프 이론, 최소 스패닝 트리 설명 최소 스패닝 트리를 응용하여 각 간선의 최소값을 구하면서, 최대 스패닝 트리를 구해 각 간선의 최댓값을 구하는 문제입니다. 최대 스패닝 트리의 경우, 최소 스패닝 트리에서 단순히 정렬 조건만 반대로 지정하여 한 번 더 수행하면 구할 수 있습니다. 최소 스패닝 트리를 잘 모르신다면 아래 포스팅을 참..

https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 난이도 : 골드 2 태그 : 그래프이론, 그래프탐색, 깊이 우선 탐색, 트리 설명 해당 문제 같은 경우는 DFS + Inorder(중위순회) 를 통해 구현할 수 있겠습니다. 위와 같은 노드가 있다고 가정해봤을때, 이를 인오더로 탐색하면 어떻게 될까요? 7-4-8-2-1-5-3-6-9 순으로 방문을 하게 됩니다. 즉, 좌-부모-우 순으로 탐색을 하기 때문에 좌측에 노드가 있을 경우..

https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 난이도 : 골드 4 태그 : 자료구조, 그래프 이론, 분리집합, 트리 설명 각 뉴런은 시냅스로 연결됩니다. 뉴런은 노드(Node) 혹은 정점(Vertex), 시냅스는 간선(Edge)로 볼 수 있겠습니다. 모든 뉴런이 시냅스로 연결되면서 사이클이 없어야 하는 트리(사이클이 없는 연결 그래프) 구조여야 합니다. 사이클이 생기지 않으면서, 각 노드를 간선으로 병합하는 과정에서는 분리집합 - 유니온파인..

https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 난이도 : 골드 2 태그 : 자료 구조, 그래프 이론, 그래프 탐색, 너비 우선 탐색, 해시를 사용한 집합과 맵 설명 BFS + Map을 사용한 문제입니다. 처음에는 9개 좌표의 방문체크를 어떻게 해야하나... 9차원 visited 배열...?을 생각했으나, 그냥 Map을 사용해 방문체크를 할 수 있습니다. 103 425 786 위의 3x3 퍼즐이 주어졌다면, 이를 103425786와 같이 문자열 혹은 CharArray 형태로 바꿔 생각할 수 있습니다. 즉, map["103..

https://www.acmicpc.net/problem/9063 9063번: 대지 첫째 줄에는 점의 개수 N (1 ≤ N ≤ 100,000) 이 주어진다. 이어지는 N 줄에는 각 점의 좌표가 두 개의 정수로 한 줄에 하나씩 주어진다. 각각의 좌표는 -10,000 이상 10,000 이하의 정수이다. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 구현, 기하학 설명 직사각형의 최소 크기를 출력해야 합니다. 직사각형의 최소 크기를 구하려면, 직사각형의 윗 변의 y좌표가 작을수록, 아랫 변의 y좌표가 클 수록, 오른쪽 변의 x 좌표가 작을 수록, 왼쪽 변의 x 좌표가 클 수록 직사각형의 넓이가 작아집니다. 따라서, 상하좌우의 좌표값을 저장해놓고, 매 값이 들어올 때마다 작거나 큰 값으로 갱..

https://www.acmicpc.net/problem/1103 1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 난이도 : 골드 2 태그 : 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색, 깊이 우선 탐색 설명 0,0 부터 시작하여 해당 칸에 적힌 숫자만큼 상하좌우 중 한 방향으로 이동한다 했을 때, 최대 몇 번 이동할 수 있는지 구하는 문제입니다. 단순히, DFS로 가장 깊은 depth가 어디인지 확인하면 될 것 같았습니다. 네. 아니였습니다. 시간초과가 나버렸으니 시간을 단축시킬 수 있는 테크닉이 필..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 난이도 : 실버 3 태그 : 다이나믹 프로그래밍, 브루트포스 알고리즘 설명 다이나믹 프로그래밍 (DP, Dynamic Programming)을 연습하기 좋은 문제인 것 같습니다. 동적계획법 혹은 다이나믹 프로그래밍은 메모리에 값을 저장해놨다가, 다음 연산에서 이전에 계산했던 값을 이용해 효율적으로 계산하는 프로그래밍 패러다임으로써, 메모리에 값을 저장해놓고 동일한 반복계산을 줄인다는 메모이제이션(Memoization)에 기반을 두고 있습니다. 백준의 예제를 가져왔습니다. 1일째에는 3일의 시간이 걸리므로, 4일에 10의 비용을 얻을 ..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 난이도 : 골드 3 태그 : 그래프이론, 그래프탐색, 너비우선탐색 설명 앞서 포스팅한 다리만들기 2와 비슷하지만, 1이기 때문에 2보단 쉽습니다. 여러개의 섬이 있을 때, 두 섬을 하나의 다리로 이으면 되기 때문입니다. 접근방법 1) DFS / BFS로 모든 섬을 그룹화한다. 이 때, 모든 섬의 좌표를 저장해놓는다. 2) 1번 과정에서 저장해놓은 각 섬의 모든 좌표를 기준으로 BFS를 수행한다. 2-1..

https://www.acmicpc.net/problem/23235 23235번: The Fastest Sorting Algorithm In The World It is common to compare sorting algorithms based on their asymptotic speeds. Some slower algorithms like selection sort take O(N2) time to sort N items, while comparison-based sorts like merge sort can go no faster than O(N log(N)) time, under reasonable a www.acmicpc.net 난이도 : 브론즈 5 태그 : 구현 설명 제목을 보고 꽤 재밌을 ..