분류 전체보기

우선순위 큐 - 우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조 우선순위 큐의 구현 방법 ● 배열을 기반으로 구현하는 방법 ● 연결 리스트를 기반으로 구현하는 방법 ● 힙을 이용하는 방법 우선순위 큐의 시간 복잡도 여기서 힙이란 ? 힙은 완전 이진트리를 말하며 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야 한다. 위 트리처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라 한다. 반면 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 최소 힙이라 한다. ▼ 힙에서의 데이터 저장 과정 ▼ 힙에서의 데이터 삭제 과정

1. Root 2. Left 3. Right 결과 : 1 2 4 5 3 1. Left 2. Root 3. Right 결과 : 4 2 5 1 3 1. Left 2. Right 3. Root 결과 : 4 5 2 3 1

https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 이 문제는 문제 자체를 이해하기 힘들었던 문제이다. 둘째 줄부터의 숫자는 서류, 면접 성적의 순위를 입력한 것이며 이에 선발할 수 있는 최대 인원 수를 출력해야 한다. 예제 입력1 과 같은 예시가 있을 때 먼저 서류 면접이 1등인 사원인 1 4 를 기준으로 비교했을 때 2 3 은 면접 성적이 더 높기 때문에 합격이고 3 2 는 2 3 보다 면접 성적이 더 높기 때문에 합격, ..

https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 다음 문제는 로프를 하나 사용해도 되고 2개, 3개 아니면 모두 사용해도 된다. 그리고 그 중에서 최대로 들어올릴 수 있는 최대 중량을 출력하는 문제이다. 예를 들어 3 10 15 60 을 입력으로 받았을 때 들어올릴 수 있는 중량은 60 로프만 선택했을 때, 6060, 15 로프 선택했을 때, 30 (15 x 2 )60, 15, 10 로프 선택했을 때, 30 (10 x 3) 이므로 최대..

노드 : node 트리의 구성요소에 해당하는 A, B, C, D, E, F와 같은 요소 간선 : edge 노드와 노드를 연결하는 연결선 루트 노드 : root node 트리 구조에서 최상위에 존재하는 A와 같은 노드 단말 노드 : terminal node 아래에 또 다른 노드가 연결되어 있지 않은 E, F, C, D와 같은 노드 내부 노드 : internal node 단말 노드를 제외한 모든 노드로 A, B 와 같은 노드 다음 그림과 같이 트리는 작은 트리로 구성된다. 이 때 작은 트리는 서브트리라 부른다. 또 서브트리는 서브트리로 나뉠 수 있다. 이진트리가 되기 위한 두 조건 ● 루트 노드를 중심으로 두개의 서브 트리로 나뉘어진다. ● 나뉘어진 두 서브 트리도 모두 이진 트리여야 한다. 트리에서는 각 ..

https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 본 문제는 A 배열과 B 배열에 있는 수들을 서로 곱한 값을 더하여 출력하는데 이 때 최솟값을 출력해야한다. 그렇게 하기 위해서는 B 배열의 높은 수는 A 배열의 낮은 수와 곱해야하고 B 배열의 낮은 수는 A 배열의 높은 수와 곱해야한다. 즉 A 배열은 내림차순, B 배열은 오름차순 정렬한 후 각각의 인덱스 값을 곱하여 더하면 최솟값이 출력된다. 코드 import java.io.*; imp..

큐란 가장 먼저 들어간 것이 가장 먼저 나오는 특성을 가진 자료구조를 말한다. 다음 그림처럼 먼저 들어간 Data는 나올 때 가장 먼저 나온다. 이러한 구조를 First In First Out(FIFO) 또는 Last In Last Out(LILO) 라 한다. 큐의 ADT는 다음과 같은 연산들을 정의한다. - 큐에 데이터를 넣는 연산 enqueue - 큐에서 데이터를 꺼내는 연산 dequeue ● enqueue 연산 방식 다음 그림은 길이가 4인 배열 대상의 enqueue 연산을 보이며 여기서 F는 Front 를 의미하고 R은 Rear 를 의미하는데 새 데이터는 Rear 부분에 저장되고 R은 그 다음 칸을 가리키게 된다. ● 일반적이지 않은 dequeue 방식 위 그림에서 보이는 방식은 dequeue 연..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 다음 문제는 K 라는 가격을 동전의 가치로 만들어야 하는데 그 중에서 동전의 개수가 최소값이 되는 개수를 출력해야한다. 만약 K가 4200원일 때 (1000원 x 4개) + (100원 x 2개) 해서 6이 출력되어야 한다. 만약 K가 4790원일 때 (1000원 x 4개) + (500원 x 1개) + (100원 x 2개) + (50원..

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 다음 문제는 인출하는데 필요한 시간의 최솟값을 구하는 프로그램이다. 줄 순서대로 앞에서부터 뒤까지 시간을 더하여 최소가 되려면 앞에 오는 숫자가 작아야 한다. 따라서 사람의 수 N 값을 입력받고 배열의 공간을 N만큼 선언하여 값을 삽입한 다음 오름차순 정렬한 뒤 한 변수에 += 연산을 하면 최솟값이 나온다. 코드 import java.io.*; import java.util.*; public class Main { public..

전위 표기법(PreFix) : +AB 중위 표기법(InFix) : A+B 후위 표기법(PostFix) : AB+ 다음과 같이 Infix 로 표기된 수식을 Prefix 로 변환하시오. X = A / B * ( C + D ) + E 항상 식에서 우선순위의 계산 먼저 시작한다. (괄호 > 곱셈,나눗셈 > 덧셈,뺄셈 순으로) 다음과 같이 Infix 로 표기된 수식을 Postfix 로 변환하시오. X = A / B * ( C + D ) + E 다음과 같이 Postfix 로 표기된 수식을 Infix 로 변환하시오. A B C - / D E F + * + 후위 표기법을 중위 표기법으로 변환할 때는 (피연산자 피연산자 연산자) 인지 확인 후 정리해야한다. 다음과 같이 Prefix 로 표기된 수식을 Infix 로 변환하..