Gi-Log

문제 링크: https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 풀이에 이용된 알고리즘: 최단거리, 다익스트라 집까지 가는 최단 경로를 찾는 것인데, 가는 중에 건우라는 친구를 도와줄만하면 도와주고, 좀 그렇다(?) 싶으면 버리는 문제이다! 시작점을 1, 도착지 마산을 v, 건우가 있는 곳을 p라고 하자. dist[i][j]를 노드 i에서 j까지의 최단 거리라고 할 때 dist[1][p] + di..

문제 링크: https://www.acmicpc.net/problem/11568 11568번: 민균이의 계략 민균이는 요즘 준민이를 놀리는 일에 재미가 들렸다. 오늘도 그는 준민이를 놀리기 위해 한가지 재미있는 아이디어를 떠올렸다. 그는 하나의 정수가 쓰여 있는 카드 N장을 준비하여 준민이에게 www.acmicpc.net 풀이에 이용된 알고리즘 및 개념: LIS, DP, 이진 탐색(?) 어디선가 들어본 부분 증가 수열 문제구나... 주어진 수열의 가장 첫 원소만 있을 때의 LIS, 두번째 원소까지 있을 때의 LIS, 세번째까지 있을 때의 LIS... 뭔가 이전 결과들 중에 지금 확인하고 있는 원소를 하나 추가해주면 될 것 같은데... 등등의 아주 다량의 사고의 흐름이 있었다. 예전부터 이런 문제를 보면 ..

문제 링크: https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 풀이에 이용된 알고리즘: DFS, BFS 주어진 테스트 케이스보다 풀이자가 다소 확장된 테스트 케이스를 만들어서 도출해보는 것을 추천한다. 9 7 4 1 3 2 3 3 4 3 7 4 6 5 8 7 9 본인은 위 테스트 케이스를 제작 및 이용했다. 4번이 몇 등인지 최고 등수(숫자가 작을 수록 최고라고 표현하겠다.)와 최저..

문제 링크: 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/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 풀이에 이용된 알고리즘: DP 굉장히 쉬운 DP 문제이다. DP는 알고 풀면 너무 쉽고, 모르고 풀면 한 없이 어려워서 다음과 같은 질문이 떠오를 것이다. 1. 왜 쉽냐? --> 음... 비슷한 유형을 풀어봐서, "알고 풀었기" 때문이라고 밖에 말씀드릴 수 없을 것 같다... 2. 왜 DP냐? --> "큰 문제를 해결할 때, 그 큰 문제 구성하는 더 작은 단위의 해답이 이용될 수 있기 때문"이라는 원론적인 이야기 밖에 할 수 없을 것 같다... 결론은, DP는 실버 1 이하의 ..

문제 링크: 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 첫째 ..