컴공에서 살아남기

랜선 자르기 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길..

특정한 최단 경로 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a,..

최단경로 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다..

트리의 지름 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 ..

트리의 부모 찾기 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 예제 입력 1 7 1 6 6 3 3 5 4 1 2 4 4 7 예제 출력 1 4 6 1 3 1 4 예제 입력 2 12 1 2 1 3 2 4 3 5 3 6 4 7 4 8 5 9 5 10 6 11 6 12 예제 출력 2 1 1 2 3 3 4 4 5 5 6 6 주어진 입력이 트리의 부모노드와 자식노드로 따로 구분되어있지 않기 때문에..

이진 탐색 트리 (BST, Binary Search Tree) 이진탐색트리는 저장과 동시에 정렬하는 트리입니다. 어느 노드를 선택하든 해당 노드의 left subtree에는 그 노드의 값보다 작은 값들을 지닌 노드들로만 이루어져 있고, 노드의 right subtree에는 그 노드의 값보다 큰 값들을 지닌 노드들로만 이루어져 있습니다. 이진 탐색 트리의 데이터 저장 규칙 규칙 1. 이진 탐색 트리의 노드에 저장된 키는 유일하다. 규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 크다. 규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 작다. 규칙 4. 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다. 시간복잡도 검색, 저장, 삭제 : O(log N) 최악의 경우에 트리가 한쪽으로 치우쳐져있다면 O(n) 이다. ..

정의 이진 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법입니다. 조건 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘입니다. 과정 start, end, mid의 변수 3개를 사용하여 탐색을 수행하고, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾습니다. 시간복잡도 O(log N) 단계마다 탐색 범위를 반으로 나누는 것 "÷2" 과 동일하므로 O(logN)의 시간복잡도를 갖습니다. 구현 이분탐색을 반복문 혹은 재귀함수로 직접 구현할 수도 있고, C++의 lower_bound 함수를 사용할 수도 있습니다. (자세한 사용 방법과 예시는 아래 코딩테스트 문제를 풀었을 때의 내용을 참고) 2023.0..

정렬 알고리즘은 크게 비교(Comparisons) 방식과, 비 비교(Non-Comparisons) 방식으로 나눌 수 있다. 비교 방식 알고리즘 비교 방식 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 힙 정렬, 퀵 정렬이 있다. 버블 정렬 (Bubble Sort) 인접한 두 개의 데이터를 비교하면서 정렬을 진행하는 방식이다. 가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수만큼을 두 번 반복한다. 시간 복잡도 (Time Complexity) O(n^2) > 과정 사진 더보기 > Code 더보기 void BubbleSort(vector arr) { for(int i = 0; i < arr.size()-1; i++) { for (int j = i + 1; j < arr...

주식가격 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,000 이하인 자연수입니다. prices의 길이는 2 이상 100,000 이하입니다. 입출력 예 prices return [1, 2, 3, 2, 3] [4, 3, 1, 1, 0] 입출력 예 설명 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다. 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다. 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점..

섬 연결하기 문제 설명 n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요. 다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다. 제한사항 섬의 개수 n은 1 이상 100 이하입니다. costs의 길이는 ((n-1) * n) / 2이하입니다. 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드..

🎄신장 트리 (스패닝 트리) 최소 신장 트리에서 '신장 트리' 즉, 스패닝 트리는 노드 간의 경로가 오직 하나뿐인 트리를 말한다. 그래프 내의 모든 정점을 포함하며, 그래프의 최소 연결 부분 그래프라고 볼 수 있다. 최소 연결이란 간선의 수가 가장 적다는 뜻으로, n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)개이다. 따라서, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되며, 이것이 바로 스패닝 트리가 된다. 🎄최소 신장 트리 (MST, Minimum Spanning Tree) 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 최소 신장 트리는 이러한 신장 트리중에서 사용된 간선들의 가중치 합이 최소인 트리를 말한다. 즉, 가중치를 간선에 할당한 그래프에 있는 모든 정점들..

등굣길 문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n은 1 이상 ..