Gi-Log

문제 링크: https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제 풀이에 이용된 자료구조: 맵 이 문제에서 중요한 부분은 세 가지로 생각된다. 1. 입력받는 나무의 수가 제시되어 있지 않은데 어느 시점에서 어떻게 입력 받는 것을 중단할 지.... string 자료형 wood 값을 입력 받기 위해서 getline(cin, wood) 함수를 이용하는데 백준에서는 입력이 파일로 들어오므로, 해당 함수가 EOF를 읽게 되면 입력이 종료된다.

문제 링크: https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 이분 탐색 수직선 상에 집들이 존재하고, 어떤 집들에 공유기를 설치할 수 있다고 할 때, C개 만큼만 설치하되, 공유기 간 인접한 거리 중 가장 가까운 거리가 최대가 되는 경우를 찾고, 그 때의 인접한 공유기 간 거리를 출력하는 문제이다. 집집 마다 공유기를 설치할 지 말 지, 결정하고 그 때의 공유기 ..

문제 링크: https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 이분 탐색 주어진 서로 다른 길이의 k개의 랜선을 똑같은 길이로 토막을 내어서, 동일한 길이의 랜선 n개를 만드는 가장 긴 랜선 토막의 길이를 찾는 문제이다. 랜선 토막의 길이를 1부터 1씩 증가시켜 나가면, 조건을 만족하는 가장 긴 토막의 길이를 구하는 것은 굉장히 단순하지만 확실한 방법이라는 것은 모두가 알 것이다. 하지만..

문제 링크: https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도 www.acmicpc.net 문제 풀이에 이용된 알고리즘(?): 단순 구현, 시뮬레이션 문제를 잘 읽고, 문제에서 시키는 대로만 하면 된다. 시키는 대로 하기 위해서, 각 행위를 코드로 얼마나 잘 "구현"하는 지가 관건인 문제이다. dx, dy 배열을 이용한 좌표 조정법은 굉장히 흔한 방법이므로 잘 숙지해야 하고, 주사위가 굴러가는 동서남북 방향에..

문제 링크: https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 크루스칼 알고리즘 주어진 그래프에서, 노드들을 연결하는 최단 거리 트리를 생성하는 문제이다. 즉, 최소 신장 트리 문제이며 크루스칼 알고리즘으로 간단히 풀 수 있다. 단, 간선을 입력 받을 때 "남초남초" 혹은 "여초여초"를 연결하는 간선은 애초에 크루스칼 알고리즘의 대상이 되는 간선 그룹에 포함시키지 않는다는 점..

문제 링크: https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 정렬, 투 포인터 두 배열을 합치고, 오름차순 정렬한 결과를 출력하는 문제이다. 가장 간단히 떠올릴 수 있는 방법으로는, 하나의 배열에 모든 원소를 입력 받고 sort 함수를 이용하는 것이다. 이 방법으로 문제를 풀었을 때 생각보다 수행 시간이 너무 길어서, 혹시 투 포인터를 이용하면 조금 다른 성능(느리거나, 빠르거나..

문제 링크: https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 이진 탐색, 파라메트릭 서치 주어진 상황에서 가장 최적의 값을 고르는 문제이므로, 아직 실력이 부족한 나는... 탐욕법을 떠올렸다. 하지만 입력의 크기를 보아하니, 탐색의 범위가 굉장히 크다는 점과 결국 확인해야할 것은 "1회 인출 시 금액"으로 1번째 날부터 n번째 날까지 생활이 가능한 지, 불가능한 지 결정하는 문제 같다고 생각하여 이진 탐색으로 접근하기로..

문제 링크 : https://www.acmicpc.net/problem/16398 16398번: 행성 연결 홍익 제국의 중심은 행성 T이다. 제국의 황제 윤석이는 행성 T에서 제국을 효과적으로 통치하기 위해서, N개의 행성 간에 플로우를 설치하려고 한다. 두 행성 간에 플로우를 설치하면 제국의 함 www.acmicpc.net 모든 행성 간에 플로우를 설치하고 싶지만, 플로우를 설치할 때 사용되는 군대 주둔 비용이 비싸서, 가장 효율적으로 플로우를 설치해야 하는 문제이다. 개인적으로 이런 그래프에서 효율성이나 일의 순서를 파악하는 문제를 보면, 신장 트리와 위상 정렬을 떠올린다. 효율성과 관련된 것은 최소 신장 트리(MST), 일이나 작업 순서를 파악해야하는 문제는 위상 정렬을 이용하며 현재 문제는 최소 ..