Gi-Log

문제 링크: https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 풀이에 이용된 알고리즘: DP 문제를 읽고 시그마 기호를 이용한 점화식을 간단히 작성 후 코드로 옮기면 되는 굉장히 간단한 문제이다!!!!! 그리고 점화식에서 t(n)을 계산할 때 t(n-1), t(n-2), t(n-3)... 등 n보다 ..

문제 링크: https://www.acmicpc.net/problem/17503 17503번: 맥주 축제 첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M > n >> m >> k; for (int i = 0; i > v >> c; beers.push_back({v, c}); // 선호도, 도수 레벨 } sort(beers.begin(), beers.end(), [](pair p1, pair p2) -> bool { return p1.second n) // 이미 술이 n개 선택된 상황이었다면 { // (직전의 삽입으로 주머니에 n + 1개의 맥주가 담겨있다면) total -= pq.top(); // 가장 작은 선호도의 술을 뺀다 pq.po..

문제 링크: https://www.acmicpc.net/problem/17503 17503번: 맥주 축제 첫 번째 줄에 축제가 열리는 기간 N (1 ≤ N ≤ 200,000) 과, 채워야 하는 선호도의 합 M (1 ≤ M n >> m >> k; int c_max = 0; // 도수 레벨 중 최대 값 for (int i = 0; i > v >> c; beers.push_back({v, c}); // 선호도, 도수 레벨 c_max = max(c_max, c); // 탐색 범위의 maximum 값 } sort(beers.begin(), beers.end(), [](pair p1, pair p2) -> bool { return p1.second b; }); // 도수 레벨 mid 보다 낮은 도수 레벨의 술을 선..

문제 링크: https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 풀이에 이용된 알고리즘: BFS, 순열(DFS), Brute Force 삼성 전자 코딩 테스트 기출 문제 풀이를 진행했거나 최근 bfs, dfs 등을 공부하는 사람에게는 익숙한 미로 탐색 유형이다. 아... 미로 탐색 유형이 익숙하다는 것이고, 16985 문제의 경우는 익숙하지 않은 미로 탐색처럼 느껴질 수 있다고 생각된다. 일단 단순히 미로를 탐색하는 것이 아니..

문제 링크: 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 풀이에 이용된 알고리즘: 위상정렬(의 개념) 스타크래프트에서 아이디어를 얻은 문제로 보인다ㅋㅋㅋ 실제 해당 게임에서도 어떤 건물을 짓기 위해서 미리 건설되어야 하는 다른 건물들이 있다. 이 문제에서도 그런 조건을 만족하며 상대방의 건물 건설/파괴 로그에 이상한 점이 있는지 즉, 치트키를 몰래 사용했는지 확인하는 문제이다. 어떤 작업의 순서와 관련돼 보여..