끄적끄적

힙이란? 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 Ο(n)만큼 시간이 걸린다. 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다. 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야하는 알고리즘 등에 활용된다. 구현 힙의 구현은 주로 배열로 진행한다. 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다. 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다. 힙에서의 부모 노드와 자식 노드의 관계 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2 오른쪽 자식의 인덱스 = (부모의..

트리란? 정점과 간선을 이용하여 데이터 배치 형태를 추상화한 자료구조로, 그래프의 일종이다. 계층적 관계를 표현하는 비선형 자료구조로, 사이클이 없는 하나의 연결그래프이다. 트리의 특징 사이클이 없다 부모-자식의 계층적 관계로 표현된다, 루트노드를 제외한 모든 노드는 단 하나의 부모노드를 가진다. 저장된 데이터를 더 효과적으로 탐색하기 위해 사용한다. 하나의 루트노드와 0개 이상의 하위 트리로 구성되어있다. 노드가 N개인 트리는 항상 N-1개의 간선을 가진다. 트리가 될 수 없는 경우 node의 edge가 자기 자신을 향하는 경우 path에서 cycle이 생기는 경우 node가 2개 이상의 parent를 가지는 경우 서로 연결되지 않은 subtree가 존재하는 경우 트리 관련 용어 노드 (Node) 트리..

그래프란? 그래프는 정점(Vertext)와 간선(Edge)로 이루어진 자료구조이다. 트리는 그래프의 일종이라고 볼 수 있지만, 그래프는 트리와 달리 루트노드와 부모-자식 개념이 없으며, 정점마다 간선이 있을 수도 있고 없을 수도 있다. 그래프 용어 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다. 인접 정점(adjacent Vertex) : 간선에 의해 직접 연결된 정점 (0과 2은 인접정점) 단순 경로(simple path) : 경로 중에서 반복되는 정점이 없는 경우. ( 0->3->2->1 은 단순경로 ) 차수(degree) : 무방향 그래프에서 하나의 정점에..

문제 링크 성능 요약 메모리: 4.2 MB, 시간: 0.01 ms 구분 코딩테스트 연습 > 동적계획법（Dynamic Programming） 채점결과 정확성: 100.0 합계: 100.0 / 100.0 문제 설명 아래와 같이 5와 사칙연산만으로 12를 표현할 수 있습니다. 12 = 5 + 5 + (5 / 5) + (5 / 5) 12 = 55 / 5 + 5 / 5 12 = (55 + 5) / 5 5를 사용한 횟수는 각각 6,5,4 입니다. 그리고 이중 가장 작은 경우는 4입니다. 이처럼 숫자 N과 number가 주어질 때, N과 사칙연산만 사용해서 표현 할 수 있는 방법 중 N 사용횟수의 최솟값을 return 하도록 solution 함수를 작성하세요. 제한사항 N은 1 이상 9 이하입니다. number는 1..

[unrated] 광물 캐기 - 172927 문제 링크 성능 요약 메모리: 33.5 MB, 시간: 3.43 ms 구분 코딩테스트 연습 > 연습문제 채점결과 정확성: 100.0 합계: 100.0 / 100.0 문제 설명 마인은 곡괭이로 광산에서 광석을 캐려고 합니다. 마인은 다이아몬드 곡괭이, 철 곡괭이, 돌 곡괭이를 각각 0개에서 5개까지 가지고 있으며, 곡괭이로 광물을 캘 때는 피로도가 소모됩니다. 각 곡괭이로 광물을 캘 때의 피로도는 아래 표와 같습니다. 예를 들어, 철 곡괭이는 다이아몬드를 캘 때 피로도 5가 소모되며, 철과 돌을 캘때는 피로도가 1씩 소모됩니다. 각 곡괭이는 종류에 상관없이 광물 5개를 캔 후에는 더 이상 사용할 수 없습니다. 마인은 다음과 같은 규칙을 지키면서 최소한의 피로도로 ..

[Silver V] 분수찾기 - 1193 문제 링크 성능 요약 메모리: 165876 KB, 시간: 144 ms 분류 구현, 수학 문제 설명 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. 출력 첫째 줄에 분수를 출력한다. ..

[Silver II] 연결 요소의 개수 - 11724 문제 링크 성능 요약 메모리: 5940 KB, 시간: 280 ms 분류 그래프 이론, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색 문제 설명 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. 연결 요소가 뭔가 했는데, 연결되어 있는 그래프의 개수를 뜻한다. 즉, 1-3-5 그..

[level2] 최댓값과 최솟값 문제 링크 문제 설명 문자열 s에는 공백으로 구분된 숫자들이 저장되어 있습니다. str에 나타나는 숫자 중 최소값과 최대값을 찾아 이를 "(최소값) (최대값)"형태의 문자열을 반환하는 함수, solution을 완성하세요. 예를들어 s가 "1 2 3 4"라면 "1 4"를 리턴하고, "-1 -2 -3 -4"라면 "-4 -1"을 리턴하면 됩니다. 제한 조건 s에는 둘 이상의 정수가 공백으로 구분되어 있습니다. 제출 코드 #include #include #include #include using namespace std; string solution(string s) { string answer = ""; priority_queue q; string str = ""; for (i..

[level 2] 멀리 뛰기 - 12914 문제 링크 문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. 제한 사항 n은 1 이상, 2000 이하인 정수입니다. 성능 요약 메모리: 4.14 MB, 시간: 0.02 m..

#include #include #include #include using namespace std; int is_possible(int children, int value, vector colorCount) { int check = 0; for (int i = 0; i value) { check++; colorCount[i] -= value; } check++; if (check > children) return 0; } return 1; } int main(void) { int children; int colors; vector colorCount; cin >> children; cin >> colors; fo..