알고리즘/이론 및 스킬 (3) 썸네일형 리스트형 Parametric Search 1. Parametric Search란 무엇일까? 파라매트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어나가는 탐색 알고리즘입니다. 주어진 범위 내에서 원하는 값 또는 원하는 조건에 가장 일치하는 값을 찾아내는 알고리즘. 주어지는 값이 범위이기 때문에 특정한 상황을 최적화 시키는 문제에 용이. 최적화 문제? 최적화 문제(Optimization)는 가능한 해들 중에서 가장 좋은 (최대 또는 최소)의 해를 찾는 문제를 말합니다. 결정문제? true or false로 대답이 가능한 문제를 말합니다. x > 5 인가에 대하여 true인지 false인지 정확하게 답이 나오게 되는 문제를 말합니다. 예시 [-5,-1,-2,-10,8,1,4,10,11,8]에서 "양수의 최소 Index를 찾으시오"라는 최적화 문제를.. 소팅 https://swexpertacademy.com/main/help/review/contentsReviewDetail.do?contentId=9091 Sorting sorting의 구분 inplace outplace stable unstable online offline 소팅의 구현 배열과 List의 차이 배열을 이용한 구현 장점 : 배열의 주소가 연속적으로 잡혀있어서 접근이 빠르다. 데이터 참조가 쉽다. 단점: 크기가 고정되어 있어 사이즈 증감이 어렵다. 중간값 변경시 이후의 데이터를 모두 변경해야함. LinkedList를 이용한 구현 장점 : 배열의 단점을 극복,크기가 유동적이고, 중간 값 변경이 용이함. 단점 : 매번 새로운 메모리를 할당하여 연결하기 때문에 성능이 느림. 포인터 공간이 추가로 생성.. 최소 공통 조상(LCA, Lowest Common Ancestor) 최소 공통 조상(LCA, Lowest Common Ancestor) Ancestor Rooted Tree에서 root를 기준으로 높이가 정해집니다. root의 높이를 0이라고 둘 때 각각의 높이는 1씩 증가합니다. 이 때, 임의의 정점에서 '루트'로 향하는 최단경로에 존재하는 자신보다 height가 낮은 정점들을 Ancestor(조상) 이라고 합니다. 보통 바로 윗 조상을 Parent라고 부릅니다. Common 주어진 두 임의의 정점은 각각 조상을 가집니다. [그림 1]에서 정점 a는 루트로 향하는 조상을 가지고, b도 가지고 있습니다. 이 때 두 정점의 조상들 중 공통된 조상을 공통 조상이라고 부릅니다. [그림 1]에서는 보라색과 빨간색으로 칠해진 Common Ancestor가 있습니다. Lowest .. 이전 1 다음
