본문 바로가기

전체 글

그래프 기초(의미, 분류, 구현 방법) 기초소개 그래프는 자료구조의 일종으로, 배열과 달리 데이터간의 관계를 나타낼 수 있는 자료구조입니다. 형태에 따라 각기 다른 특성을 가지고 있기 때문에 여러 세부 분류로 나뉘기도 합니다. 그래프란? 데이터에 해당하는 정점과 정점을 이으며 정점끼리의 관계를 나타내는 간선으로 이루어진 자료구조입니다. 위 그림처럼 생긴 자료구조입니다. 이 그래프는 무엇을 나타내는 그래프일까요? 정점을 사람, 간선을 친구 관계로 표현한다면 집단에서 친구인 사람들을 표현하는 그래프가 됩니다. 정점을 도시, 간선을 길으로 생각한다면 지도처럼 도시 사이를 이동하는 경로를 표시하는 그래프가 됩니다. 이처럼 정점과 간선을 적절히 설정한다면 그래프가 많은 것들을 나타내도록 할 수 있습니다. 간선의 방향 방향은 일방 통행 도로처럼 간선에서.. 더보기
제 4회 천하제일 코딩대회 본선 후기 몇 시간 전(2020년 12월 22일 7시) 제 4회 천하제일 코딩대회가 끝났습니다. 2학년 선배 두 분과 팀을 이뤄 참여했고, 11문제 중 5문제를 풀고 전체 4위로 동상을 받았습니다. 원래 오프라인에서 진행되는 대회이지만 코로나19 상황이 악화되어 온라인으로 진행되었습니다. 팀원과는 디스코드로 소통했고, 부정행위 방지를 위해서인지 대회가 끝날 때까지 계속 캠을 켜고 화면도 공유해야 했습니다. 오프라인 행사를 기대했던 저는 아쉬움이 남았지만, 현재 상황에서 취할 수 있는 최선의 방법이었다고 생각합니다. 시작이 10분 연기되었던 점만 빼면 대회는 전반적으로 원활하게 진행되었습니다. 처음에 디스코드 방으로 들어가니 딜레이가 너무 심하고, 마이크도 잘 되지 않는 것 같아 당황했습니다. 다행히 시간이 지나자 .. 더보기
백준 4195번 친구 네트워크 http://icpc.me/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 Union-find와 map STL을 사용해 풀었습니다. 사용자가 문자열 이름이 아닌 번호로 주어졌다고 가정합시다. 이러한 경우에는 Union-find로 각 사용자와 친구 네트워크의 크기를 관리하며 쉽게 풀 수 있습니다. union-find 트리를 나타낼 배열과 각 사용자의 친구 네트워크의 크기를 나타낼 배열이 필요합니다. 두 사용자가 친구 관계를 맺으면 union연산을 통해 두 사용자가 속해 있는 친구 네트워.. 더보기
백준 1422번 숫자의 신 http://icpc.me/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 풀이 뒤에서 설명할 비교 연산을 편하게 하기 위해 n개의 수를 문자열 자료형으로 받습니다. k개의 수 중 가장 길이가 길고 큰 수를 최대한 많이 반복하는 것이 이득입니다. 따라서 길이순(길이가 같다면 크기순)으로 정렬하여 n - k번 반복할 수를 먼저 선택하고, 정답을 나타낼 벡터에 선택한 수를 n - k번 넣고 k개의 수를 모두 하나씩 넣습니다. 이후 선택한 n개의 수로 가장 큰 수를 만들 수 있도.. 더보기
백준 13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부www.acmicpc.net풀이마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다. 쿼리 1 : 0 b원래 명령과 반대로 b와 .. 더보기
백준 20052번 괄호 문자열? https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ?괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이www.acmicpc.net풀이유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다.유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다. 풀이 1(유니온 파인드 이용)이 풀이의 핵심은 유니온 파인드를 이용해 이어져 있는 괄호쌍을 하나로 묶어 관리하는 것입니다. 입력받은 괄호 문자열을 탐색하며 이어져 있는 괄호쌍을 묶는 작업을 마치면 아래 그림처럼 괄호 문자열이 여러.. 더보기
백준 1781번 컵라면 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라� www.acmicpc.net 문제 설명 문제가 N개 주어지며, 각각의 문제마다 데드라인과 받을 수 있는 컵라면 수가 있습니다. 문제를 데드라인 안에 해결하면 컵라면을 받을 수 있습니다. 모든 문제의 데드라인은 N 이하이며, 푸는데는 1만큼의 시간이 필요합니다. 이때 받을 수 있는 컵라면의 최대 수를 구하는 문제입니다. 풀이 데드라인을 이미 넘긴 문제는 풀 필요가 없으므로, 풀어야 할 문제를 골라야 합니다. 데드라인 순서대로 문제를 .. 더보기
백준 17298번 오큰수 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 설명 길이가 $N$인 수열 A가 주어집니다. A의 i번째 원소 $A_i$의 오큰수는 자신보다 오른쪽에 있고 큰 수 중 가장 가까운 수입니다. 수열의 모든 원소의 오큰수를 찾아 출력하는 문제입니다. 풀이 각 원소의 오큰수를 찾을 때마다 오른쪽 원소를 모두 탐색하면 $O(N^2)$로 시간초과일 것입니다. 스택을 이용하면 $O(N)$만에 모든 원소의 오큰수를 찾을 수 있습니다. 수열 A의 오른쪽에서부터 원소를 .. 더보기

티스토리툴바