Gi-Log

문제 링크: https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net 문제 풀이에 이용된 알고리즘: 단순 구현 거스름돈으로 주는 동전의 개수를 최소화하고 싶다면, 우선 5원짜리 동전을 최대한 많이 사용하고 남은 금액을 2원으로 만들면 된다. 따라서 for문을 이용해서, 지급 가능한 5원짜리 동전을 하나씩 줄여가며, 매 경우에 5원으로 지급하고 남은 금액을 2원으로 지급 가능하다면 그 경우가 답이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36..

문제 링크: https://www.acmicpc.net/problem/17140 17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 풀이에 이용된 알고리즘: 구현, 시뮬레이션 문제에 주어진 대로 구현하면 쉽게 풀리는 문제였던 것으로 기억한다. 처음 입력 시 arr[r][c] == k 라면 추가적인 탐색없이 0을 출력할 수 있도록 하는 로직을 넣어주지 않아서 시간을 낭비했었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27..

문제 링크: https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 풀이에 이용된 알고리즘: 구간합, 누적합 고정된 길이 x의 구간 내 원소의 합이 가장 큰 구간을 찾고 그 합을 출력하는 문제이다. 또한 서로 다른 구간일지라도 동일한 합을 보이는 경우, 그 합이 등장한 횟수를 증가시켜가며 최종적으로 횟수 또한 출력한다. for문 사용하여 어떤 원소들의 합을 구하면 되고, 해당 구간을 한칸씩 이동시켜나가면서 그 합의 maximum 값을 찾으면 되..

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