본문 바로가기

PS 문제 풀이/Jungol101

[Jungol] 정올 1013 Fivestar 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=292&sca=50 Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 가로로만 막대를 놓는 경우 그리디 알고리즘으로 쉽게 막대의 개수를 구할 수 있습니다. 앞에서부터 차례대로 아직 덮지 않은 '*'를 덮어 나가면 됩니다. 이 때 가능한 오른쪽으로 덮을 수 있는 '*'을 최대한 함께 덮어야 합니다. 행의 수가 5개 미만이 경우 열의 최대 길이는 최대 10이므로 ***** 막대기를 놓는 경우는 0~2개 입니다. 중간에 하나의 점만 포함되어도 2개의 막대기를 가로로 놓을 수 없습니다. ex) "*****.****" / "********.*" 한쪽으로 몰려서 5.. 2021. 2. 27.

[Jungol] 정올 2270 여객선(Cruise) 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1983&sca=9040 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com 최대 수용무게가 10인 배를 이용해서 1, 2번째 승객을 태운 다음, 최대 수용무게가 15인 배를 이용해서 3, 4, 5, 6번째 승객을 태우면 최대 수용무게가 12인 배를 출항하지 않으므로 최적이 된다. ① 배들을 배치하는 경.. 2021. 2. 27.

[Jungol] 정올 1929 책꽂이 만들기 출처: http://kcwjwbw.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1202&sca=3080 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 21 = 13 + 8 → 비용 21 발생 13 = 8 + 5 → 비용 13 발생 ▶ 총 비용 = 21 + 13 = 34 15 = 6 + 0 → 비용 15 발생 6 = 3 + 3 → 비용 6 발생 9 = 4 + 5 → 비용 9 발생 3 = 1 + 2 → .. 2021. 2. 27.

[Jungol] 정올 1318 못생긴 수 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=597&sca=30 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 1부터 차례대로 못생긴 수인지 확인하는 방법 가능 ▶ ugly[i] = i번째 못생긴 수 하지만 아래와 같이 각 수가 (2, 3, 5)로 이루어져 있는지 확인하는 것은 TLE 발생 bool isUgly(int num) { int i, mod[3] = { 2, 3, .. 2021. 2. 27.

[Jungol] 정올 1190 모두더하기 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=473&sca=50 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com N개의 수가 주어졌을 때 덧셈 연산은 총 N-1번 필요합니다. 더할 때 마다 더하는 두 수를 최소로 해야 하므로 N개의 수들을 계산할 때, 남은 숫자들 중에서 매번 최솟값 2개로해서 더해갑니다. 결국, 매 연산마다 최솟값을 빨리 찾아야 하므로 최소 힙 구조 이용 #.. 2021. 2. 27.

[Jungol] 정올 1570 중앙값 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=843&sca=4020 Approach 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com - 첫 입력을 mid로 중앙값이라고 하자. - 우선순위 큐로 maxpq와 minpq 생성 (각각 최대힙과 최소힙) - 첫 수 이후 들어오는 두 개의 수에 대하여 mid 보다 작으면 maxpq / mid 보다 크다면 minpq에 담습니다. ① 두 pq 크기가 같다면 mid 값 출력 ② maxpq.si.. 2021. 2. 27.

[Jungol] 정올 2082 힙정렬2 (Heap_Sort) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=2283&sca=4020 Approach [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com ▶ 최대힙(Max Heap)을 만들어 출력한다. 최대힙 특징 ① 완전 이진 트리(Complete Binary Tree) ② 부모 노드의 값 ≥ 자식 노드의 값 (마지막 노드가 반드시 전체원소의 최소값은 아닙니다. 다만, 단말(leaf) 노드 중에 최소값은 존재.. 2021. 2. 27.

[Jungol] 정올 1405 하노이3(4기둥) 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=681&sca=4030 Input 2 Output 3 1 : A->B 2 : A->D 1 : B->D ▶ hanoi4(n, 1, 2, 3, 4) : 1번 기둥에 있는 n개의 원판을 4번 기둥으로 이동시키는데 2, 3번을 여분의 기둥으로 이용 hanoi4(n, 1, 2, 3, 4)에서 n개의 원판 중 일부인 K개를 2번 기둥에 이동시키는 것을 hanoi4(k, 1, 3, 4, 2)라고 할 수 있습니다. (여분의 기둥을 한 개 활용하고자 하는 것이기 때문에 3번 기둥으로 이동한다고 생각해도 상관 X) (이때, K는 임의의 수가 될 수 없으면 최적화 수치가 필요합니다.) k개를 2번 기둥에 옮겨놓았.. 2021. 2. 27.

[Jungol] 정올 1912 미로탐색 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1185&sca=30 Input 5 6 1 3 3 4 4 2 2 1 1 4 4 5 Output 1 2 4 3 5 N이 작지 않은 숫자이기 때문에 인접행렬 보다는 인접리스트로 그래프 연결 정보를 표시합니다. 그래프 정보에 앞서 주어지는 Input Data 정렬되어 있지 않기 때문에 시간효율을 위해서는 mergeSort나 quickSort를 이용해서 정렬해야 합니다. ex) 정렬 시 양방향 연결을 고려해서 연결정보를 표시한 후 정렬 (2, 4) (1, 3)가 주어질 때 → (1, 3) (2, 4) 주어진 것들만 정렬하는 것이 아닌 → (1, 3) (2, 4) (3 1) (4 2) 양방향 정보를 배.. 2021. 2. 27.

[Jungol] 정올 1824 스도쿠 출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1097&sca=3030 Input 0 3 5 4 6 9 2 7 8 7 8 2 1 0 5 6 0 9 0 6 0 2 7 8 1 3 5 3 2 1 0 4 6 8 9 7 8 0 4 9 1 3 5 0 6 5 9 6 8 2 0 4 1 3 9 1 7 6 5 2 0 8 0 6 0 3 7 0 1 9 5 2 2 5 8 3 9 4 7 6 0 Output 1 3 5 4 6 9 2 7 8 7 8 2 1 3 5 6 4 9 4 6 9 2 7 8 1 3 5 3 2 1 5 4 6 8 9 7 8 7 4 9 1 3 5 2 6 5 9 6 8 2 7 4 1 3 9 1 7 6 5 2 3 8 4 6 4 3 7 8 1 9 5 2 2 .. 2021. 2. 27.

이전 1 ··· 6 7 8 9 10 11 다음

티스토리툴바