2660번: 회장뽑기 입력의 첫째 줄에는 회원의 수가 있다. 단, 회원의 수는 50명을 넘지 않는다. 둘째 줄 이후로는 한 줄에 두 개의 회원번호가 있는데, 이것은 두 회원이 서로 친구임을 나타낸다. 회원번호는 1부터 www.acmicpc.net 1. 문제 설명 예제 1에서 1번부터 5번 회원의 점수는 각각 3점, 2점, 2점, 2점, 3점이다. 그러므로 가장 작은 점수는 2점이 되고, 점수가 2점인 2, 3, 4번 회원 총 3명이 회장 후보가 되는 것이다. 2. 구현 아이디어 1 - 틀렸습니다. 1. 현재 노드에서 가장 거리가 먼 노드까지의 거리가 해당 회원의 점수가 된다. 2. 모든 회원의 점수를 배열에 저장하고, 배열의 최솟값(=score)을 찾는다. 3. 값이 score인 원소의 index를 ca..

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 1. 문제 설명 2. 구현 아이디어 - 메모리 초과 문제 설명에 있는 예제 입력에 그린 것처럼 컴퓨터끼리의 관계를 그래프로 표현할 수 있고, 여기서 s초를 간선의 값이라고 생각하면 최초로 해킹 당한 컴퓨터부터 다른 컴퓨터까지의 최단 경로를 탐색하는 문제라고 생각할 수 있다. 한 노드에 대해서만 최단 경로를 생각하면 되기 때문에 다익스트라 알고리즘을 사용해보자. 다익스트라 알고리즘의 개념에 대해서는 아래 포스트에 정리해두었다. 최단거리 알고리즘 - 다익스트라 & 플로이..

2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 1. 문제 설명 이번 문제는 일반적인 구간 합 문제와 달리 수의 변경이 빈번하게 일어나는 것이 핵심적인 차이점이다. 간단한 구간 합 문제는 누적 합의 차로 쉽게 구할 수 있지만, 중간에 계속 수가 변경된다면 누적 합이 일정하지 않으므로 해당 방법을 사용할 수 없다. 이렇게 원소가 변경될 때 구간 합을 구할 때 사용할 수 있는 방법이 세그먼트 트리이다. 자세한 개념 설명은 따로 정리해두었으니 아래 링크를 ..

7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 1. 문제 설명 2. 예제 설명 3. 구현 아이디어 1 - 틀렸습니다. C++의 priority_queue에서는 가장 위(top)의 원소만 반환할 수 있다. 매 연산마다 우선순위 큐를 뒤집는 것은 비효율적이기 때문에 최댓값과 최솟값 둘 다 접근하기 위해서는 우선순위 큐를 2개 만들어야 한다. 그리고 중요한 것이 2개의 우선순위 큐를 동기화해주는 것이다. 최댓값 또는 최솟값을 삭제할 때 하나의 큐에서만 삭제하면 다음 연산을 진행할 때 연산이 원하는대로 이루어지..

9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 1. 문제 설명 예제 입력 1에서 첫 번째 테스트 케이스는 문제 속 예시와 동일하고, 두 번째 테스트 케이스는 하늘색 박스를 친 스티커를 골랐을 때가 점수가 최대가 된다. 2. 구현 아이디어 처음 봤을 때 백준 1149번: RGB 거리와 비슷하게 풀면 될 것 같다는 생각이 들었다. 그래서 점화식을 아래와 같이 세웠다. 🍙 점화식 dp[0][i] = dp[1][i-1] + board[0][i] dp[1][i] = dp[0][i-1] + board[1][..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 1. 문제 각 예제별 트리의 모습을 입력 오른쪽에 그림으로 표현하였다. 2. 구현 아이디어 1 - 틀렸습니다 그래프를 표현하는 방법에는 인접 행렬과 인접 리스트가 있는데, 인접 리스트 방식을 사용하였다. map 자료구조를 사용하여 key는 부모 노드, value는 자식 노드의 배열로 하였다. 재귀(DFS)를 사용하여 자식 노드가 없을 때를 종료 조건으로 하고 종료 조건일 때마다 리프 노드의 개수를 +1하도록 재귀 함수를 구현하였다. 만약 제거할 노드가 루트..