Algorithm/BOJ

[백준 1043] 거짓말 (C++)

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 재미있는 문제였다. 나는 사람과 파티를 똑같이 하나의 정점으로 보았다. 둘다 최대 50이므로 사람은 51부터, 방은 1부터 번호를 가지도록 설정했다. 진실 감별사부터 시작하는 dfs를 수행한다. 이때 연결되는 모든 정점은 진실 감별사로 바뀌게 된다. 처음 주어진 진실 감별사와 연결된 모든 정점을 진실 감별사로 바꾸고, 아직까지 진실 감별사가 되지 않은 사람의 수를 출력하면 답을 구할 수 있다. 처음에 Union find로 풀려고 했다가 너무 어려워졌다. 그래프를 계속 그려..

[백준 2616] 소형기관차 (C++)

2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 현재 칸을 선택할 때, 선택하지 않을 때를 정해서 재귀를 수행하면 되는 문제이다. 현재 칸을 선택하지 않는다면 현재 칸의 번호를 +1 한 채로 다음 칸으로 넘어간다. 현재 칸을 선택한다면? 현재 칸부터 소형 기관차의 크기만큼 연속된 칸에 타있는 손님의 수를 누적합 배열 parr을 통해서 구해준다. 그리고 현재 칸의 번호를 +소형기관차의크기 한 채로 다음 칸으로 넘어간다. 기저 조건은 소형 기관차를 선택한 횟수가 4가 되거나 현재 칸을 선택해도 소형 기관차의..

[백준 2696] 중앙값 구하기 (C++)

2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 일단 처음에 들어오는 값은 반드시 최초의 중앙값이고 최초의 기준값이 된다. 그리고 앞으로 들어오는 값을 현재 기준과 비교해서 기준보다 크다면 최소 힙에, 기준보다 작다면 최대 힙에 넣어준다. 만약 지금까지 입력받은 수가 짝수라면 넘어간다. 하지만 홀수라면 현재 기준값이 중앙값이 되기 위해서는 최소 힙과 최대 힙에 들어있는 원소의 수가 서로 같아야 한다. 코드 : 만약 최소 힙의 수가 더 많다면 최소 힙에서 최상단 원소를 중앙값으로 둘..

[백준 1199] 오일러 회로(인접 리스트) (C++)

[백준 1199] 오일러 회로 C++ 1199번: 오일러 회로 첫 줄에는 정점의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 그리고 다음 N개의 줄에 대해 인접행렬의 정보가 주어진다. i+1번째 줄에는 i번 정점에 대한 인접행렬이 주어진다. 두 정점 hyeo-noo.tistory.com 예전에 풀었던 오일러 회로 문제가 인접행렬로 풀 수 없게 데이터가 추가되면서 많은 사람들이 시간초과의 늪에 빠졌었다. 나도 마찬가지로 시간초과로 틀리게 되었고 4달이 지나서야 인접 리스트 방식의 오일러 회로를 공부하고 다시 풀게 되었다. INPUT 우선 input 부분에 많은 변화가 있었다. i에서 j로 가는 간선을 인접 행렬로 저장하지 않고 간선 그 자체로 저장했다. 대신에 j에서 i로 가는 간선은, 입력에서 i에서 ..

[백준 1948] 임계경로 (C++)

1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 단방향 그래프(DAG)임을 유의 특정 도시에서 모두 만나는데 걸리는 시간은 시작도시에서 특정 도시까지 가는데 걸리는 모든 시간 중 최댓값이 된다. 따라서 BFS를 통해 모든 정점에 대해 걸리는 시간 값을 구할 수 있다. 도착 정점까지 쉬지 않고 달려야 하는 사람이 지나는 도로의 개수의 의미는 도착 정점을 시작점으로 해서 되돌아 갈 때, '도착 정점까지 가는데 걸리는 시간 - 도착 정점을 시작으로 특정 정점까지 가는데 걸리는 시간 = 시..

[백준 17398] 통신망 분할 (C++)

17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제를 읽어보니 통신망들의 집합을 구현해야 했다. 서로 연결이 되어있는 통신망, 즉 하나의 정점으로 귀납되는 노드들 사이의 한 간선을 끊으면 2개로 나뉠 텐데 몇 개씩으로 나눠지는지를 구하면 된다. 풀이 방법을 떠올리기까지 꽤 오래 걸렸는데 처음에 노드의 간선을 끊는 동작을 하나의 쿼리로 보고 세그먼트 트리를 구성해서 풀어야 하나?라는 말만 그럴듯한 이상한 생각을 했다. 그러다가 일단 input에 입력을 다 받고 보니 반대로 생..

[백준 1863] 스카이라인 쉬운거 (C++)

1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1≤n≤50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1≤x≤1,000,000. 0≤y≤500,000) 첫 번째 지점 www.acmicpc.net 스택 높이가 바뀌는 y좌표만 저장하면 된다. 높이가 점점 증가하다가 갑자기 감소했을 때, while문을 돌면서 stack의 top에 위치한 높이가 현재 높이와 같거나 작아질 때까지 pop을 수행한다. 마지막에 stack에 남아있는 건물의 수 만큼 답에 더해준다. 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..

[백준 1103] 게임 (C++)

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 백트래킹과 DP가 합쳐진 문제? 중요 - 방문처리 방문한 곳에 도달했다면 사이클을 이루므로 무한번 이동가능. -1 출력 후 exit()으로 프로그램 종료 나머지는 현재 위치좌표를 가지는 dp배열을 통해 최대 이동 횟수를 재귀적으로 메모이제이션 한다. 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 ..

[백준12762 ] 롤러코스터 (C++)

12762번: 롤러코스터 첫째 줄에 개조하고자 하는 구간의 길이 \(N\)이 주어진다. 구간의 길이는 1,000을 넘지 않는 자연수이다. 둘째 줄에 구간 내에 있는 각 기둥들의 높이가 주어진다. 기둥의 높이는 10,000 이하의 자연 www.acmicpc.net 숫자가 감소하다가 증가하는 경우, 숫자가 계속 증가하는 경우, 숫자가 계속 감소하는경우의 수를 모두 구하면 된다. 여기서 숫자가 계속 증가하는 경우의 수를 구하는 이유는 아래와 같다 1. 기둥을 마음대로 삭제할 수 있다. 2. "그리고 롤러코스터의 진행 방향은 공사가 끝난 후 결정된다." => 앞, 뒤 부터 시작해서 감소하는 수열만 찾으면 된다. 구간의 시작부분이 양 끝 모두 될 수 있다. 따라서 특정 인덱스를 시작으로하는 감소하는 수열의 길이를..

[백준 1234] 크리스마스 트리 (C++)

1234번: 크리스마스 트리 첫째 줄에 트리의 크기 N, 빨강의 개수, 초록의 개수, 파랑의 개수가 주어진다. N은 10보다 작거나 같다. 빨강, 초록, 파랑의 개수는 0보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 레벨이 최대 10이므로 1 + ... + 10 = 55 이다. 따라서 한가지 색을 최대 55개까지만 사용할 수 있다. -> 배열의 크기가 [11][60][60][60]인 이유 cache 배열은 [현재 층][빨간색을 사용한 횟수][초록색을 사용한 횟수][파랑색을 사용한 횟수] = 경우의 수 기저조건은 재귀를 돌면서 현재 층이 N을 넘기면 해당 경우가 있다는 뜻으로 1을 반환하도록 했다. 각 층마다 사용된 색의 개수가 모두 같아야 하고, 각 층마다 색깔에 따라서 순열이..