본문 바로가기

전체 글

 (18)
Programming Advanced [파이썬 S/W 문제해결 구현02 완전 검색] SWEA 5188 - 최소합 (D3) Problem 그림처럼 NxN 칸에 숫자가 적힌 판이 주어지고, 각 칸에서는 오른쪽이나 아래로만 이동할 수 있다. 맨 왼쪽 위에서 오른쪽 아래까지 이동할 때, 지나는 칸에 써진 숫자의 합계가 최소가 되도록 움직였다면 이때의 합계가 얼마인지 출력하는 프로그램을 만드시오. 1 2 3 2 3 4 3 4 5 그림의 경우 1, 2, 3, 4, 5순으로 움직이고 최소합계는 15가 된다. 가능한 모든 경로에 대해 합을 계산한 다음 최소값을 찾아도 된다. [입력] 첫 줄에 테스트케이스의 수 T가 주어진다. 1
Programming Advanced [파이썬 S/W 문제해결 구현01 시작하기] SWEA 5186 - 이진수2 (D2) Problem 0보다 크고 1미만인 십진수 N을 이진수로 바꾸려고 한다. 예를 들어 0.625를 이진 수로 바꾸면 0.101이 된다. N = 0.625 0.101 (이진수) = 1*2-1 + 0*2-2 + 1*2-3 = 0.5 + 0 + 0.125 = 0.625 N을 소수점 아래 12자리 이내인 이진수로 표시할 수 있으면 0.을 제외한 나머지 숫자를 출력하고, 13자리 이상이 필요한 경우에는 ‘overflow’를 출력하는 프로그램을 작성하시오. [입력] 첫 줄에 테스트케이스의 수 T가 주어진다. 1 이진수 변환에 13자리 이상이 필요한 것 -> overflow else: result = 'overflow' print('#{} {}'.format(tc, result))
Programming Advanced [파이썬 S/W 문제해결 구현01 시작하기] SWEA 5185 - 이진수 (D2) Problem 16진수 1자리는 2진수 4자리로 표시된다. N자리 16진수가 주어지면 각 자리 수를 4자리 2진수로 표시하는 프로그램을 만드시오. 단, 2진수의 앞자리 0도 반드시 출력한다. 예를 들어 47FE라는 16진수를 2진수로 표시하면 다음과 같다. 0100011111111110 [입력] 첫 줄에 테스트케이스의 수 T가 주어진다. 1
SWEA 1233 - 사칙연산 유효성 검사 Programming - Intermediate - SW 문제해결 기본 Tree - 1233 사칙연산으로 구성되어 있는 식은 이진 트리로 표현할 수 있다. 아래는 식 “(8/2)*(6-4)”을 이진 트리로 표현한 것이다. 임의의 정점에 연산자가 있으면 해당 연산자의 왼쪽 서브 트리의 결과와 오른쪽 서브 트리의 결과를 사용해서 해당 연산자를 적용한다. 사칙연산 “+, -, *, /”와 양의 정수로만 구성된 임의의 이진 트리가 주어질 때, 이 식의 유효성을 검사하는 프로그램을 작성하여라. 여기서 말하는 유효성이란, 사칙연산 “+, -, *, /”와 양의 정수로 구성된 임의의 식이 적절한 식인지를 확인하는 것으로, 계산이 가능하다면 “1”, 계산이 불가능할 경우 “0”을 출력한다. (단, 계산이 가능한지가 아..
힙(Heap) 힙(Heap) 힙 : 완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조 최대 힙(max heap) 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 > 자식 노드의 키 값 루트 노드 : 키 값이 가장 큰 노드 최소 힙(min heap) 키 값이 가장 작은 노드를 찾기 위한 완전 이진 트리 부모 노드의 키 값 < 자식 노드의 키 값 루트 노드 : 키 값이 가장 작은 노드 힙 연산 - 삽입 힙 연산 - 삭제 힙에서는 루트 노드의 원소만을 삭제할 수 있다. 루트 노드의 원소를 삭제하여 반환한다. 힙의 종류에 따라 최대값 또는 최소값을 구할 수 있다.
이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(BST : Binary Search Tree) 탐색 작업을 효율적으로 하기 위한 자료구조 모든 원소는 서로 다른 유일한 키를 갖는다. key(왼쪽 서브트리) 루트 노드의 키 값) : 루트 노드의 오른쪽 서브트리에 대해서 탐색연산 ..
이진 트리(Binary Tree) 이진 트리 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리 각 노드가 자식 노드를 최대한 2개 까지만 가질 수 있는 트리 : 왼쪽 자식 노드(left child node), 오른쪽 자식 노드(right child node) 이진 트리의 예 이진 트리 - 특성 레벨 i에서의 노드의 최대 개수는 2^i개 높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개, 최대 개수는 (2^(h+1) - 1)개 이진 트리 - 종류 포화 이진 트리(Full Binary Tree) 모든 레벨에 노드가 포화상태로 차있는 이진 트리 높이가 h일 때, 노드의 개수가 (2^(h+1) - 1)인 이진 트리 높이가 3일 때 노드의 개수 : 2^(3+1) - 1 = 15개 루트를 1번으로 하여 2^(h+1) -..
병합 정렬(Merge Sort) - Merge Sort 기본 개념 리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복 (cnoquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합 (combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 병합한다. - 소스 코드 def merge_sort(arr, n): if n == 1: return arr # 분할(divide) : 부분 리스트 나누기 mid = n // 2 left_arr = arr[:mid] right_arr = arr[mid:] # 정복(conquer) : 각 부분 리스트 재귀적으로 병합 정렬 sorted_left..

티스토리툴바