Gi-Log

문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 주어진 예시를 직접 손으로 한 번 써보면, 어떤 계단 형태의 합이 완성되는 것을 알 수 있다. 예를 들면, 가장 앞에 선 사람의 인출 소모 시간은 뒷 사람들의 소모 시간에 포함되기 때문에 지속적으로 전체 소모 시간을 구하는 과정에서 합해지는 것이다. 말이 어려운데 정답부터 이야기하자면, 결국 인출에 소모되는 시간이 긴 사람은 뒤쪽에 서 있는 것이 좋다는 것이다. 인출에 소모 시간이 긴 사람이 내 앞에 서 있다면, ..

문제 링크: https://www.acmicpc.net/problem/13911 13911번: 집 구하기 첫줄에는 정점의 개수 V(3 ≤ V ≤ 10,000)와 도로의 개수 E(0 ≤ E ≤ 300,000)가 주어진다. 그 다음 E줄에 걸쳐 각 도로를 나타내는 세 개의 정수 (u,v,w)가 순서대로 주어진다. 이는 u와 v(1 ≤ u,v ≤ V)사 www.acmicpc.net 문제 풀이에 사용된 알고리즘: 다익스트라, 최단 경로, 더미 노드 문제에서 제시하는 조건(맥세권인지, 스세권인지)를 만족하는 정점(집)들 중에서, (맥도날드까지의 거리) + (스타벅스까지의 거리)가 작은 수치를 보이는 집을 찾는 문제이다. 우선 노드의 수가 굉장히 많고, 인접 행렬이 아닌 간선 형태의 인접 리스트가 주어지기 때문에 ..

문제 링크: 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/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/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제 풀이에 이용된 알고리즘: 조합, 완전 탐색 재귀를 활용한 완전 탐색으로 간단히 풀 수 있는 문제지만, 재귀에 익숙하지 않다면 한도 없이 어려울 수 있는 문제이다. dfs 함수에 이용되는 인자들의 의미는 주석으로 잘 설명해 놓았는데, 잘 이해가 되지 않는다면 재귀를 활용한 조합에 대해서 공부해보고 어느 정도 습득했다면 재귀를 활용한 순열에 대해 ..

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