Coding Test

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초를 간선의 값이라고 생각하면 최초로 해킹 당한 컴퓨터부터 다른 컴퓨터까지의 최단 경로를 탐색하는 문제라고 생각할 수 있다. 한 노드에 대해서만 최단 경로를 생각하면 되기 때문에 다익스트라 알고리즘을 사용해보자. 다익스트라 알고리즘의 개념에 대해서는 아래 포스트에 정리해두었다. 최단거리 알고리즘 - 다익스트라 & 플로이..

1. 최단거리 알고리즘이란? 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 주로 그래프를 이용하여 표현하며 각 지점은 노드, 지점 간 연결선은 간선으로 표현한다. 이번 포스트에서는 대표적인 최단거리 알고리즘인 다익스트라 알고리즘과 플로이드 워셜 알고리즘에 대해 소개하겠다. 2. 다익스트라 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 음의 간선이 없을 때 정상적으로 동작하며, 매번 가장 비용이 적은 노드를 선택하기 때문에 그리디 알고리즘으로 분류된다. 음의 간선 - 0보다 작은 값을 구하는 간선 음의 간선이 포함되었을 경우에는 벨만 포드 알고리즘을 사용해야 한다. 다익스트라 알고리즘의 구현 🍥 각 노드에 대해 현재까..

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. 문제 설명 이번 문제는 일반적인 구간 합 문제와 달리 수의 변경이 빈번하게 일어나는 것이 핵심적인 차이점이다. 간단한 구간 합 문제는 누적 합의 차로 쉽게 구할 수 있지만, 중간에 계속 수가 변경된다면 누적 합이 일정하지 않으므로 해당 방법을 사용할 수 없다. 이렇게 원소가 변경될 때 구간 합을 구할 때 사용할 수 있는 방법이 세그먼트 트리이다. 자세한 개념 설명은 따로 정리해두었으니 아래 링크를 ..

1. 세그먼트 트리란? 여러 개의 데이터가 존재할 때 특정 구간의 합(최솟값, 최댓값, 곱 등 ...)을 구하는데 사용하는 자료 구조이다. 트리 종류 중 하나로 이진 트리의 형태이며, 특정 구간의 합을 가장 빠르게 구할 수 있다는 장점이 있다. → O(logN) 세그먼트 트리는 이진 트리 중에서도 전 이진트리(Full Binary Tree)에 해당한다. 전 이진 트리: 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리 2. 세그먼트 트리의 구성 먼저 이진 트리를 구성할 때 루트 노드는 1부터 시작한다. (0부터 시작하면 인덱스 관리가 어렵다) 그 아래부터는 부모 노드의 인덱스를 i라고 할 때 왼쪽 자식 노드는 2i, 오른쪽 자식 노드는 2i+1이 된다. 아래는 A={ 1, 2, 3, 4, 5 }라는 ..

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