Algorithm

[백준 2617번] 구슬 찾기 (C++)

https://www.acmicpc.net/problem/2617 2617번: 구슬 찾기 모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 www.acmicpc.net 구슬 찾기 문제는 그래프로 해결할 수 있습니다. 무게가 중앙값이 될 수 없는 구슬을 찾는 문제입니다. 따라서, 무게가 중앙값인 구슬은 본인보다 가벼운 구슬이 (n - 1) / 2개, 무거운 구슬이 (n - 1) / 2개 있어야 합니다. 따라서, 가벼운 구슬이 (n - 1) / 2개보다 많거나, 무거운 구슬이 (n - 1) / 2개보다 많은 구슬은 무게가 중앙값이 될 수 없습니다..

[백준 1707번] 이분 그래프 (C++)

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 다음과 같은 조건을 만족시키는 집합의 분할을 가질 수 있다면, K분 그래프라고 합니다. 위키백과 인접한 두 정점은 서로 다른 정점 집합에 속한다. k = 2일 때, 이를 이분 그래프라고 합니다. 따라서 인접한 정점의 색이 서로 다르도록 색을 칠해주어야 하고, 색의 수는 2가 되어야 합니다. 따라서, BFS를 이용하여 각 정점에 색을 부여하되, 이미 방문한 정점의 색이 인접한 정점과 색이 같으면 이..

[백준 19700번] 수업 (C++)

https://www.acmicpc.net/problem/19700 19700번: 수업 키가 188cm, 154cm인 학생들을 한 팀으로, 키가 180cm, 161cm인 학생들을 한 팀으로, 키가 172cm인 학생을 혼자 팀으로 묶으면 총 3개의 팀을 구성할 수 있다. 더 적은 갯수의 팀으로 학생들을 묶을 수 있 www.acmicpc.net 수업 문제는 그리디와 이진검색트리를 이용하여 해결할 수 있습니다. 학생의 키가 중복되지 않기 때문에, 키가 큰 사람부터 그룹에 넣어주면, 먼저 그룹이 할당된 수강생들의 키는 현재 그룹을 할당하려는 수강생보다 키가 큽니다. 따라서, i번째 학생은 그룹의 크기가 Ki보다 작은 그룹 중 하나에 할당시켜주면 됩니다. 하지만, 그룹의 수를 최소로 만들어 주어야하기 때문에, K..

[백준 23326번] 홍대 투어리스트 (C++)

https://www.acmicpc.net/problem/23326 23326번: 홍익 투어리스트 도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고, www.acmicpc.net 홍익 투어리스트 문제는 이진 검색 트리를 이용하여 해결할 수 있습니다. 명소의 위치만 이진 검색 트리에 저장해주면 됩니다. 1번 연산 : 이진 검색 트리에 존재한다면, 제거하고, 존재하지 않는다면, 명소로 추가, 시간 복잡도 : O(logN) 2번 연산 : 도현이의 위치만 이동, 시간 복잡도 : O(1) 3번 연산 : lower_bound()를 이용하여, 가장 가까운 명소의 위..

[백준 21939번] 문제 추천 시스템 Version 1 (C++)

https://www.acmicpc.net/problem/21939 21939번: 문제 추천 시스템 Version 1 tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령 www.acmicpc.net 문제 추천 시스템은 이진 검색 트리를 이용하여 해결할 수 있습니다. 이진 검색 트리를 이용하면, 최대/최소값 구하기, 삽입, 삭제을 모두 O(logN)에 수행할 수 있습니다. 또한, 이진 검색 트리에 {l, p}를 삽입하면, 먼저, 난이도를 기준으로 정렬하고, 난이도가 같을 땐 문제 번호로 정렬하므로, 마지막 원소가 난이도가 가장 높으면서, 번호가 가장 큰 번호입니다..

[백준 1202번] 보석 도둑 (C++)

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 보석 도둑 문제는 이진검색트리를 이용하여 해결할 수 있습니다. 훔칠 수 있는 보석의 가격을 구해야하는데, 가방에는 최대 한 개의 보석만 넣을 수 있습니다. 가방에 넣을 수 있는 보석 중 가장 가치가 큰 것을 선택하면 됩니다. 그럼 어느 가방에 먼저 넣어야할까요? 아래 예에서, 가방에 담을 수 있는 최대 무게가 가장 무거운 가방부터 넣어보..

[백준 22862번] 가장 긴 짝수 연속한 부분 수열 (large) (C++)

https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 가장 긴 짝수 연속한 부분 수열 (large) 문제는 투 포인터를 이용하여 해결할 수 있습니다. 수열의 각 원소들을 시작점으로 잡았을 때, 최대 K개의 홀수를 제거하여 만들 수 있는 짝수 수열의 최대 길이를 계산하고, 이중 가장 긴 길이를 출력하면 됩니다. 하지만, N이 최대 1,000,000이기 때문에, O(N2) 알고리즘은 시간 초과가 발생할 수 있습니다. 수열의 시작점이 st, 끝점이 en일 때, 홀수의 개수가 cnt이라면..

[백준 13144번] List of Unique Numbers (C++)

https://www.acmicpc.net/problem/13144 13144번: List of Unique Numbers 길이가 N인 수열이 주어질 때, 수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수를 구하는 프로그램을 작성하여라. www.acmicpc.net List of Unique Numbers 문제는 투 포인터로 해결할 수 있습니다. 중복이 없는 수열의 시작점을 st, 끝점을 en라고 하겠습니다. 따라서, st + 1부터 en까지도 중복이 없습니다. 하지만, seq[st]를 제외하였으므로, en을 이동시켜 중복이 없는 수열의 끝점을 다시 찾아야합니다. (단, seq는 입력 받은 수열을 의미함) seq = {1, 2, 3, 1, 2}로 예를 들어보겠습니다..