Gi-Log

문제 링크: https://www.acmicpc.net/problem/1749 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 문제 풀이에 이용된 알고리즘: 누적합, 다이나믹 프로그래밍 처음에는 만들 수 있는 모든 부분 행렬을 구하고, 각 부분 행렬 내 원소의 총 합 중 최대값을 구하는 방법에 대해서 생각해봤다. 부분 행렬을 결정하는 것은, 부분 행렬의 "좌측 상단"과 "우측 하단" 2가지 이다. 좌측 상단을 알고 있다면, 부분 행렬의 가로 길이와 세로 길이를 통해 우측 하단의 좌표를 구할 수 있다. 따라서 좌측 상..

문제 링크: 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 문제의 경우는 익숙하지 않은 미로 탐색처럼 느껴질 수 있다고 생각된다. 일단 단순히 미로를 탐색하는 것이 아니..