겜돌이의 개발일지

문제 백준 2108 통계학 C++ 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 풀이 예전에 재채점으로 틀렸었는데 여유될 때 다시 풀어보았다. 먼저 수를 입력받은 뒤 오름차순 정렬한다. 1. 산술평균 : 루프를 돌면서 계산하면 된다. 반올림 주의 2. 중앙값 : 원소 개수가 홀수일 때와 짝수일 때를 나눠서 계산한다. 3. 최빈값 : 이게 제일 귀찮았는데, 다음과 같은 과정을 거친다. 3-1. 먼저 가장 자주 등장한 횟수를 0으로 초기화해 준다. 3-2. 루프를 돌면서 현재값의 등장 횟수를 1 증가시킨다. 3-3-1. 현재..

문제 백준 1725 히스토그램 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자 www.acmicpc.net 풀이 오름차순 Monotonic Stack을 활용했다. startIdxs(n) 배열을 사용했는데, 이 배열은 i번째 value에 대해, 그보다 작은 값이 그전 원소들 중에서 언제 처음 등장하는지 인덱스를 담고 있는 배열이다. 작은 값이 없다면 0을 담고 있다. 예를 들어서 5 3 2 3 5에 대해 startIdxs는 idx순서대로 각각 0, 0, 0, 2, 3이 된다. 넓이를 구할 때는 특정 원소가 ..

문제 백준 3015 오아시스 재결합 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 풀이 N = 500,000이므로 O(N^2)으로 푸는 것은 불가능하다. 따라서 Monotonic Stack을 활용한다. Monotonic Stack [알고리즘] Monotonic Stack 개요 자신보다 큰 값(혹은 작은 값)이 언제 처음 오는지에 대해 구해야 할 때, 가장 쉽게 떠올릴 수 있는 방법은 2중 for 문을 쓰는 것이다. 예를 들어 다음과 같이 숫자가 있다고 할 때 3 4 1 5 2 각 ga..

문제 백준 2564 경비원 C++ 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 풀이 이해는 바로 했는데 구현을 어떻게 할까 고민을 많이 했던 문제 최단 경로가 맞은편인지, 시계인지, 반시계인지 다 확인을 해줘야 하는데 if 문 덕지덕지 써가면서 각 케이스마다 모두 처리해 주기는 너무 싫었다. 그래서 좌상단을 0으로 기준을 잡고 시계방향(북->동->남->서)으로 각각의 좌표를 RoundPos로 명명하고 RoundPos를 잡아주었다. 이렇게 좌표를 잡아주면 문제 예시의 RoundPos는 다음과 같다. 1번 상점 좌..

문제 백준 4811 알약 C++ 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 풀이 Top-down 방식의 dp를 이용한다. 알약을 꺼낼 때, 경우의 수는 다음과 같다. (반 개 짜리는 h, 한 개 짜리는 w로 지칭한다.) dp[w][h]는 한 개 짜리가 w, 반 개 짜리가 h만큼 있는 경우 알약을 먹을 수 있는 가짓 수를 뜻한다. 1. w != 0, h != 0인 경우 1-1. w를 먹는다. h가 한 개 늘어나고 w는 1 줄어든다. 그 후에 dp[w-1][h+1] 만큼의 경우의 수가 생긴다. 1-2. h를 먹는다. h가 ..

문제 백준 2302 극장 좌석 C++ 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net 풀이 처음에 dp인지 완전탐색인지 헷갈렸던 문제 최대 21억 개의 가짓 수가 있는 것 보고 dp일거 같았다. 자신의 번호와 다른 자리에 앉을 때는, 항상 그 사람과 나의 자리를 바꿔서 앉는다는 것에 초점을 두고 고민했다. 1, 2, 3 세 명을 자리에 앉힌다고 가정하자. 1과 2, 2와 3을 서로 바꿔 앉게 할 수 있다. 1, 2를 먼저 앉힐 때 1 2 또는 2 1이 가능하다. 이 때 3을 앉힐 때 1 2 뒤에 3을 앉혀 1 2 3을 만..

문제 백준 5972 택배 배송 C++ 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 풀이 문제 설명이 애매하게 되어있는데, 하나 이상의 길로 연결되어 있을 수 있다는 점이 거슬렸다. 시작, 끝 점은 똑같은데 비용이 다른 간선을 말한다기보다는 다른 점으로 우회하여 갈 수 있다고 받아들였다. 풀이는 일반적인 다익스트라 문제 해법을 사용해 해결해주면 된다. 우선 순위 큐를 사용하여 시작 점부터 간선 정보를 갱신해 주고, N까지 가는 비용을 출력한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..

문제 백준 10025 게으른 백곰 C++ 10025번: 게으른 백곰 첫 줄에 정수 N과 K가 들어온다. 둘째 줄부터 N째 줄까지, 공백을 사이에 두고 각 양동이의 얼음의 양을 나타내는 gi와 양동이의 좌표를 나타내는 xi가 주어진다. www.acmicpc.net 풀이 일반적인 두 포인터 문제다. 처음부터 마지막까지, 양동이의 양을 더하고 빼주면서 최대합을 구한다. 범위 계산이 귀찮았는데, 정확하게 계산해 범위 초과 이슈가 나지 않도록 유의한다. 소스 코드 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 ..

문제 백준 2473 세 용액 C++ 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 용액문제 (https://gamedoridori.tistory.com/238)의 심화형이다. 오름차순으로 용액이 정렬되어있지 않으므로 먼저 정렬을 해준다. 그리고 각각의 용액에 대해, 그 용액과 합의 절댓값이 최소가 되는 두 용액을 두 포인터로 찾아준다. 여담으로 용액과 두 용액 문제는 입력값이 -10억~10억이라 int 자료형으로도 문제가 없었지만, 세 용액 문제는 int 자료형을 사용할 시에 ab..

문제 백준 2467 용액 C++ 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 일반적인 두 포인터 문제이다. 앞 뒤에서 용액을 확인한 뒤, 주어진 조건에 따라 start와 end를 이동시켜주면 된다. 소스 코드 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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 #include #in..