Gi-Log

문제 링크: https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 풀이에 이용된 알고리즘: 위상정렬(의 개념) 스타크래프트에서 아이디어를 얻은 문제로 보인다ㅋㅋㅋ 실제 해당 게임에서도 어떤 건물을 짓기 위해서 미리 건설되어야 하는 다른 건물들이 있다. 이 문제에서도 그런 조건을 만족하며 상대방의 건물 건설/파괴 로그에 이상한 점이 있는지 즉, 치트키를 몰래 사용했는지 확인하는 문제이다. 어떤 작업의 순서와 관련돼 보여..

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

문제 링크: https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1≤n≤100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이다. www.acmicpc.net 문제 풀이에 이용된 알고리즘: 세그먼트 트리 사탕 상자 내에 k번째로 맛있는 사탕을 구하기 위해서, 어떤 식으로 세그먼트 트리를 만들지와 어떤 식으로 쿼리를 날릴지를 결정하면 쉽게 풀 수 있는 문제이다.(본인에게는 앞에 두세가지 조건이 많이 어려웠다.) 사탕의 맛은 1~1000000까지 연속적이다. 맛이 i인 사탕이 몇개인지를 arr[i]라고 하고, 세그먼트 트..

문제 링크: 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/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net 문제 풀이에 이용된 알고리즘: bfs, (자료구조)set 집을 설치하는 다양한 경우의 수가 존재하므로 가장 먼저 떠올리는 것은 완전 탐색이었다. 하지만 탐색 범위가 너무 넓기 때문에 말이 되지 않고, 그렇다고 이진 탐색을 이용하기에도 적합하지 않았다. 가장 가까운 샘물까지의 거리를 1, 2, 3...으로 하나씩 증가시키며, 집을 설치할 수 있는 경우의 수..