일지
-
JUNGOL...110일지 2021. 8. 6. 14:44
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
알고리즘...33일지 2021. 8. 6. 11:43
이진 검색 트리 구현 연결 자료구조를 이용하여 이진 검색 트리를 구현한다. BinarySearchTree.h #pragma once #include "../Common.h" /// /// 이진 검색 트리에 사용할 노드 /// struct BinarySearchNode { BinarySearchNode() : data{ 0 }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} BinarySearchNode(int data) : data{ data }, parent{ nullptr }, left{ nullptr }, right{ nullptr } {} void Clear() { data = 0; parent = nullptr; left = nullptr; ..
-
JUNGOL...109일지 2021. 8. 5. 13:37
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
알고리즘...32일지 2021. 8. 5. 10:29
이진 검색 트리에서의 삭제 이진 검색 트리서 노드를 삭제할 때에는 다음과 같이 케이스를 나눠서 진행해야 한다. 삭제할 노드에 자식이 없는 경우 삭제할 노드에 자식이 하나 있는 경우 삭제할 노드에 자식이 둘 있는 경우 - 자식이 없는 경우 해당 노드를 바로 삭제한다. - 자식이 하나 있는 경우 해당 노드를 삭제한 뒤 자식 노드를 삭제한 노드의 위치에 놓아준다. - 자식이 둘 있는 경우 해당 노도를 삭제한 뒤 이진 검색 트리의 서브 트리의 조건을 깨지 않는 자식 노드를 골라 삭제한 노드의 위치에 놓아준다. 이때, 서브 트리의 조건을 깨지 않는 조건은 다음과 같다. 오른쪽 자식의 서브 트리에서 가장 작은 값을 가진 노드 왼쪽 자식의 서브 트리에서 가장 큰 값을 가진 노드 ※ 선택된 노드에 자식이 존재하는 경우..
-
JUNGOL...108일지 2021. 8. 4. 13:28
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
알고리즘...31일지 2021. 8. 4. 13:18
이진 검색 트리에서의 삽입 이진 검색 트리에 노드를 삽입하는 방법은 다음과 같다. 삽입하려는 값이 이진 검색 트리에 존재하는지 확인하기 위해 검색을 진행한다. 값이 이미 존재하는 경우 종료한다. 값이 존재하지 않아 말단 노드에 도달한 경우 해당 노드에 삽입하려는 값을 가진 노드를 추가한 뒤 종료한다. 이진 검색 트리에서의 삽입 알고리즘 TreeInsert(t, x) { if (t = NIL) then { r = NEW_NODE; key[r] ← x; left[r] ← NIL; right[r] ← NIL; return r; } if (x < key[t]) then { left[t] ← TreeInsert(left[t], x); return t; } else { right[t] ← TreeInsert(rig..
-
JUNGOL...107일지 2021. 8. 3. 15:05
Intermediate_Coder/분할정복/모자이크 문제 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 정사각형 모양의 칸을 만들고, 각 칸마다 같은 색의 물감으로 색칠을 하였다. 그런데 잘못 칠해진 칸이 있음을 발견하게 되었다. 수찬이는 도화지와 색깔이 같은 색종이를 사서 잘못 칠해진 칸에 색종이를 붙이고 다시 그리는 것이 좋겠다고 생각하고 선생님께 상의를 드렸다. 선생님께서는 정해진 장수의 색종이를 사용하여 아래와 같은 조건을 따르면서 잘못 칠해진 칸을 모두 가리되, 가장 작은 색종이의 크기를 구하는 새로운 문제를 내셨다. (조건 1) 사용되는 색종이는 모두 크..
-
알고리즘...30일지 2021. 8. 3. 14:48
이진 검색 트리에서의 검색 특정 키를 가진 노드를 검색하는 방법은 다음과 같다. 이진 검색 트리의 루트 노드에서부터 비교를 시작한다. 주어진 키와 노드의 키를 비교하여 주어진 키가 노드의 키가 같으면 노드를 반환한다. 주어진 키가 노드의 키보다 작으면 왼쪽 서브 트리로 이동하여 다시 비교한다. 주어진 키가 노드의 키보다 크면 오른쪽 서브 트리로 이동하여 다시 비교한다. 위 과정을 노드를 찾거나 말단 노드에 도달할 때까지 반복한다. 이진 검색 트리에서의 검색 알고리즘 TreeSearch(t, x) { if (t = NIL or key[t] = x) then return t; if (x < key[t]) then { return TreeSearch(left[t], x); } else { return Tree..