본문 바로가기

전체 글107

[Binary Search] 이진 탐색이란 무엇인가? 나누면서 탐색? 반으로 나누면서 원하는 값을 찾아가는 탐색방법 - 전제는 정렬 시작점 중간점 끝점이 제일 중요하다 중간점을 기준으로 찾으려는 값이 작으면 중간점 아래로 찾고 중간점을 기준으로 찾으려는 값이 크면 중간점 위로 찾는다 중간점과 찾으려는 값이 같으면 idx 토해내고 시작점이 끝점보다 더 커지는 순간이 온다면 찾지 못했다는 뜻이니 None을 반환 시작점이 왜 끝점보다 클때 그만? 요소가 한개인 경우에는 시작점과 끝점이 같다 한개인 경우에 그게 찾는 수가 아니라면 끝점이 -1 되거나 시작점이 +1 될 것이다 두 경우 모두다 시작점이 끝점을 초과시이므로 그 때 끝낸다 시간복잡도 절반으로 나누어지면서 찾아가기 때문에 트리 모양이다 O(logN) 재귀를 통해 푸는 방법 def binary_search(array, l,.. 2021. 9. 17.
[Sort] 프로그래머스 - 가장 큰 수 1차 시도 사고 과정 - 틀림 가장 최고자리 수를 기준으로 정렬을 하여 모든 것들을 Concat하자 가장 최고자리 수를 찾기위해 1보다 작아질 때까지 각 수를 나누고 그것을 딕셔너리에 IDx값과 함께 넣자 {'Index' : 3, 'top_num' : 9} 이런식으로 넣은 후 key를 최고 자리수로 하여서 정렬시키자 -> [3, 30, 34, 5, 9]일 때의 생각울 못했다! 최고자리가 같은 애들이 여러개일 경우 두번째 자리 기준으로 비교가 다시한번 들어가야 한다는 점을 간과하여 틀렸다 2차 시도 사고 과정 - 반은 맞음 numbers에 들어간 값들을 모두 STring으로 변환시키자 모든 원소는 0~1000까지의 수이므로 3자리 수가 대부분이다. 3, 34, 32가 있다면 34, 3, 32 순으로 정렬이.. 2021. 9. 17.
[BFS] 백준 - 1261번 알고스팟 BFS 벽 부시는 것을 최소화 하는 경로를 찾기 위해서 일단은 주변 방들을 탐색하면서 진행하는 것이 좋다고 판단해 BFS를 사용한다. 벽 부시기 횟수 최소화 하기 위한 조건? 1인 방에 가면 벽을 부셔야 하는 횟수가 늘어나기 때문에 0인 방부터 우선으로 검사할 수 있도록 하자 0인 방은 일단 부시기가 안 일어나므로 Queue에서 appendLeft하여 먼저 pop 될 수 있도록 한다 1인 방은 부시기가 일어나므로 Queue에서 append 하여서 pop 우선순위를 뒤로 미룬다 방문 여부 체크 BFS와 Queue를 통해 가장 빠르고 부시는 수를 최소화 할 수 있는 경로로 찾아가기 때문에 한번 방문한 방을 방문처리를 하지 않는다면 다른 노드에서 다시 방문해서 속도가 떨어질 것이라 판단 visited 배열을 .. 2021. 9. 13.
[Sort] 퀵 정렬 - Quick Sort 기준(Pivot)을 두고 기준 왼쪽에는 작은 수들을, 기준 오른쪽에는 큰 수들을 놓는다. 이러한 과정을 기준을 제외하고 왼쪽 부분(기준보다 작은 아이들) / 오른쪽 부분(기준보다 큰 아이들)에 똑같이 적용하여 반복한다 Pivot을 기준으로 작/큰 분류 - Tree 처럼 반복 / swap 시 Index 범위 조심! 주의 오른쪽부터 탐색하는 포인터(코드에서는 right)가 arr의 범위를 넘어가지 않는 포인터이다. pivot을 항상 맨 첫번째 Idx로 정하기 때문이다. 모두 정렬이 되어있는 경우 왼쪽부터 탐색하는 포인터(코드에서는 left)는 arr의 범위를 넘어간다. 따라서 left와 right가 교차했을 시에, right 자리를 pivot과 swap해주어야 기준이 중간으로 범위 벗어난 문제 없이 이동할 .. 2021. 9. 12.

티스토리툴바