Gi-Log

문제 링크: https://www.acmicpc.net/problem/4446 4446번: ROT13 간달프는 여러 종족의 언어를 꽤 오랜 시간 동안 공부했다. 최근에 간달프는 해커들이 사용하는 언어인 ROT13을 공부했다. 이 언어는 영어와 문법이 같지만, 알파벳의 순서를 어떤 규칙을 이용해 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 구현 문제에서 원하는 조건들을 단순히 구현하면 되는 문제이다. 구현을 하는 방법은 다양하게 있으므로, 무엇이 정답이다!라고 말하기에는 적절하지 않은 것 같다. 다만, 이번 문제처럼 입력 받은 어떤 데이터들을 "사이클"로 만드는 경우에는, 입력 데이터를 두번 이상 반복해서 입력 받는 것이 좋다. 예를 들어, a i y e o u에서 e로부터 오른쪽 세번째는 ..

문제 링크: https://www.acmicpc.net/problem/11505 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 세그먼트 트리 지난 포스팅 중 (https://jinho9610.tistory.com/23)을 먼저 읽고 오길 바란다. 백준(BOJ) 11659 구간 합 구하기 C++ 풀이 문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 ..

문제 링크: https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제 풀이에 이용된 알고리즘: 다이나믹 프로그래밍, 세그먼트 트리 구간 내 누적합을 구하는 문제인데, 단순히 for문을 이용하여 계산할 경우 시간 초과가 발생했던 것으로 기억한다. DP를 이용하여 효율적으로 문제 풀이를 진행할 수 있는데, 최근 세그먼트 트리를 공부하기 위해서 이 문제를 다시 풀어보았다. 세그먼트 트리에 대한 설명은 나동빈님의 블로그(https:..

문제 링크: https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 다익스트라 굉장히 간단한 최단 경로 문제였다. 버스 노선은 곧 간선을 의미한다. 이 때 버스가 양방향 통행이 가능하다는 말이 없으므로, 양방향 간선이 아니라 방향성이 있는 것으로 생각해야 한다. 최단 경로를 구하기 위해서, 다익스트라나 플로이드 알고리즘을 생각할 수 있는데 플로이드 알고리즘은 N^3의 시간복잡도를 갖는다...

문제 링크: 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/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)로 구현할 수 ..