Gi-Log

문제 링크: https://www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마 www.acmicpc.net 풀이에 이용된 알고리즘: 투포인터, 구현 투포인터라고는 하였지만, 구현에 가깝다고 생각된다. 1. 어떤 입력데이터의 시작과 끝을 연결해주기 위해서, 원형 리스트 등의 복잡한(?) 자료구조 도입을 고민할텐데, 단순히 입력 데이터 시퀀스를 두 번 연속하여 1차원 배열에 저장해주면 된다. ex1) 입력데이터가 1 3 5라면, 단순히 1 3 5 1 3 5로 배열에 저장해두도록 한다. (m이 n 이하..

문제 링크: https://www.acmicpc.net/problem/20542 20542번: 받아쓰기 세계적인 기업 CTP(Chickens Threaten Programming)에 입사하기 위해서는 영어 받아쓰기 테스트를 통과해야 한다. 영어 받아쓰기는 채용 담당자가 불러주는 단어를 지원자가 받아쓰는 시험이다. CTP에서는 www.acmicpc.net 문제 풀이에 사용된 알고리즘: DP, 편집 거리, Levenshtein Distance (정답 문자열)과 (내가 답안으로 작성한 문자열)이 같아지도록 얼마나 수정(편집, edit)을 진행해야를 수치화하는 문제이다. Levenshtein Distance, 편집거리라고 하는 알고리즘을 적용해서 쉽게 풀 수 있는 문제이다. 동적 프로그래밍(DP)로 구현할 수 ..

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