본문 바로가기
728x90
반응형

알고리즘 && 자료구조

 (27)
[백준 1002] 터렛 (Feat. Python) 문제 이석원은 조규현과 백승환에게 상대편 마린(류재명)의 위치를 계산하라는 명령을 내렸다. 조규현과 백승환은 각각 자신의 터렛 위치에서 현재 적까지의 거리를 계산했다. 조규현의 좌표 (x1,y1) 와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오. 풀이 주어진 두 점의 거리는 구하는 공식을 이용하여 두 점의 거리를 계산 = length 주어진 반지름의 차이를 계산 = diff 이 두변수를 사용하여 두개의 원 접점이 하나인지 혹은 동일한 원인지, 혹은 두개인지를 알 수 있다. 만약 두점의 거리가(length) 두 반지름의 차이보다 크고 두 반지름의 합보..
[백준 14215] 세 막대 (Feat.Python) 문제 영선이는 길이가 a, b, c인 세 막대를 가지고 있고, 각 막대의 길이를 마음대로 줄일 수 있다. 영선이는 세 막대를 이용해서 아래 조건을 만족하는 삼각형을 만들려고 한다. 각 막대의 길이는 양의 정수이다 세 막대를 이용해서 넓이가 양수인 삼각형을 만들 수 있어야 한다. 삼각형의 둘레를 최대로 해야 한다. a, b, c가 주어졌을 때, 만들 수 있는 가장 큰 둘레를 구하는 프로그램을 작성하시오. 풀이 삼각형의 가장 작은 두변의 길이의 합은 가장 긴 변의 길이보다 커야한다. 이를 이용하기위해 입력 받은 수를 모두 배열에 넣어 오름차순으로 정렬해주었다. if문에는 주어진 길이들로 삼각형이 될때 else문에는 주어진 길이들로는 삼각형이 되지 않아 가장 짧은 둘레를 가질 수 있도록 가장 작은 두개의 변의..
알고리즘 분석 7 - Introduction To Algorithms ch 13 Red-Black Tree Red-Black Tree red - black tree 란 - 균형이 잡힌 이진 트리 with color - 이진 트리들 중에서 Search tree인 경우 노드가 한쪽으로 치우쳐져 있는 균형을 잃은 tree 형식이 되는 경우가 많은데 잃은 균형을 찾게 해주는 것이 바로 Red - Black Tree 이다. Red-Black Tree Properties - 성립 조건 Red - Black tree 는 각 노드의 색깔을 Red, Balck 중 선택하고 properties들을 다 만족 시켜야 성립 할 수 있다. 모든 노드는 빨강 혹은 검정이다. 모든 Leaf Node (가장 끝에 있는 NULL은) 항상 Black 이다. (다르게 말하면 값이 있는 노드 들은 꼭 2개의 child node 를 가지게 된다) ..
알고리즘6.5 - Stable & In Place sort Stable & UnStable sort - 안정 정렬(stable) 은 정렬할 Input안의 중복된 키(값)들이 정렬이 되었을 때, 그 순서가 그대로 정렬 되는 것을 말한다. - Unstable은 같은 중복된 키(값)들이 순서 그대로 정렬 되지 않는 것을 말한다. 예를 들어) 3(1), 3(2), 2, 1 이 4개의 input을 정렬 한다고 했을 때 Stable : 1, 2, 3(1), 3(2) Unstable: 1, 2, 3(2), 3(1) 이렇게 정리 할 수 있다. Stable 에는 Insertion sort Bubble sort Merge sort Bucket sort Radix sort unstable에는 Quick sort Heap sort 이렇게 나눌 수 있다. In Place sort - ..
알고리즘분석6 - Introduction to Algorithms ch8 Sorting in Linear-Time Sorting in Linear - Time - 말 그대로 Array안에 있는 값을 정렬하는데 liner 한 time complexity를 가진다는 뜻 (n 만큼의 시간복잡도) 지금까지 정리한 Merge sort, Heap sort는 시간복잡도 N log N을 가진다. 지금까지 정리한 sorting 들은 다 "비교" 를 통한 실행을 하는데, 비교를 통한 정렬을 하게 되면 최소한 N log N 만큼의 시간 복잡도가 필요하다는 Theorem이 있다. 그렇다면 어떻게 해야 더 빠르게 정렬할 수 있을까? Counting Sort - 계수 정렬 Counting sort의 경우 heap 이나 merge sort처럼 비교를 하지 않는다. 이름 그대로 숫자를 세서 정렬하는 방식 시간복잡도 Θ(N)을 가진다. Count..
알고리듬분석5 - Introduction to Algorithms ch7 Quick Sort Quick Sort Quick Sort 란 - 분할 정복 ( Divide and Conquer) 방법 사용한다. Divide : sorting 할 배열에서 pivot(임의의 수)를 기준으로 오른쪽 왼쪽으로 나누게 된다. 이때 왼쪽 과 오른쪽의 배열가 동일 하지 않아도 된다. Conquer : pivot을 통해 나뉘어진 두개의 배열을 sorting 한다. Combine : sorting 이 완료된 두개의 배열을 합친다. 2,8,7,1,3,5,6,4 의 배열을 Quick Sort를 이용하여 정렬하는 것을 예시로 보여주고자 한다. A) pivot을 맨 마지막 데이터로 설정 ( 어디든 상관없음), pivot은 4 B) index j가 가르키는 값(2)이 pivot보다 작음으로 index i 의 값이 늘어남 C)..
알고리즘분석4 - Introduction to Algorithm ch6 Heapsort Heap 이란? Heap이란 자료구조 해당하며 이를 이용한 Heap Sort 알고리즘의 Efficiency에 대해서 알아보고자 한다. Heap 은 마지막 level을 제외한 모든 level에서 node 들이 다 채워진 완전 이진 트리(Complete Binary Tree) 이어야 한다. Heap 은 주로 array로 구현하게 된다. Root에 있는 값은 array애서 첫번째에 있는 값으로 생각한다. 어떤 Node 의 이름 i의 값은 A[i] 라고 표현하며, 그 노드의 부모 인 Node 의 값은 A[i/2] 가 된다. 같은 Node i 에서의 왼쪽 자식의 값은 A[2i] 이며 오른쪽은 A[2i + 1] 이 된다. 예를 들어) 5 위치에 있는 값은 A[5], 그 Node의 Parent Node의 값은 A[5..
알고리듬분석3 - Introduction to Algorithms ch4 Divide and Conquer Recurrence Equation - 알고리즘에서 시간 복잡도 함수가 재귀식 형태인 것을 의미함 문제를 해결하는 데 있어서 자기보다 작은 문제들로 나누고 (Divide) 나누어진 문제들을 해결하고 (Conquer) 해결한 문제를 다시 합치는 (Merge) 방식을 말한다. T(n) = T(divide) + T(conquer) + T(merge) Time complexity는 이렇게 표현할 수 있음. Solving Recurrence Equation Substitiution method -> solution을 증명하는 방법 Recursion-tree method Iteration method Master method Recurrence Equation을 해결하는 데 있어서 여러 가지 방식들이 있고 그 방법..
728x90
반응형

티스토리툴바