Gi-Log

문제: SW Expert Academy 1257 K번째 문자열 swea에서 문자열 매칭 강의를 듣고 이 문제를 풀게 되는 사람들이 많을텐데, 강의에서 접미어 배열, 트라이, kmp 등등의 고급(?) 알고리즘이 등장한 것에 비해서 꽤나 쉽게 풀리는 문제이다. 굉장히 단순하게 주어진 문자열을 자를 두 위치를 i와 j로 지정하고, 파생되는 있는 모든 경우의 부분 문자열을 생성한다. 그리고 이 부분 문자열들을 저장할 컨테이너가 필요한데, 예시로 주어진 것처럼 food의 경우 o라는 부분 문자열이 중복(2번) 발생할 수 있다. 여기서 중복을 제거하기 위해서 set을 써야함을 눈치챌 수 있었다면 굉장히 쉽게 풀 수 있다. 특히나 해당 문제는 "k번째" 부분 문자열 출력을 위해서 정렬이 필요한데, set을 쓸 경우 ..

문제: SW Expert Academy 1248번 공통조상 (효율적인 풀이인지 검증이 필요한 풀이입니다) 주어진 트리 정보를 바탕으로, 두 정점의 공통 조상을 파악하고, 그 조상의 자식 노드 수 + 1(=서브 트리 크기)를 구하는 문제이다. 개인적으로 트리 문제가 나오면 긴장하는 편인데, 주어진 정보를 바탕으로 트리를 구현해야하나...라는 고민을 처음에 했고, 배열을 이용해서 트리를 구현하려고 했다. 하지만 공통조상을 찾기 위해서는 트리를 거슬러 올라가야할 필요가 있었기에 단순히 각 노드의 부모가 누구인지 parent라는 배열에 저장하고, 각 노드의 자식 노드는 누구(들)인지 child라는 2차원 배열에 저장하기로 하였다. 이 때 2차원 배열인 이유는, 주어진 트리가 이진 트리이기 때문인데, 그냥 vec..

문제 링크: 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 함수를 이용하는 것이다. 이 방법으로 문제를 풀었을 때 생각보다 수행 시간이 너무 길어서, 혹시 투 포인터를 이용하면 조금 다른 성능(느리거나, 빠르거나..