컴공에서 살아남기

도둑질 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 입출력 예 money return [1, 2, 3, 1] 4 문제 자체는 간단하다. 연속되는 배열 원소와, 처음과 끝 원소를 동시에 선택하지 못하는 경우 중, 숫자가 가장 큰 최댓값을 찾아..

정의 오브젝트 슬라이싱은 Class 상속과정에서 일어날 수 있는 문제로, 파생 클래스 객체가 기본 클래스 객체에 할당되면, 파생 클래스 객체의 추가적인 특성이 잘려나간 채 기본 클래스 객체로 생성되는 것을 말한다. 쉽게말해, 자식 객체에서 부모 객체로 copy 될 때 자식 객체의 정보가 잘려나가는 것이다. 주로 부모 클래스를 call by value로 받는 경우, 오브젝트 슬라이싱이 발생한다. 오브젝트 슬라이싱 발생 상황 #include using namespace std; class Base { protected: int i; public: Base(int a) { i = a; } virtual void display() { cout

랜선 자르기 문제 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 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...