훈훈훈

이번에는 이진 탐색 트리 개념과 이진 탐색 트리에서 최소합을 찾는 문제에 대하여 정리해보려고 한다. 이진 탐색 트리는 이진탐색과 연결리스트의 장점을 합친 개념으로 그림으로 간단히 그리면 아래와 같다. # 이진탐색트리 예시 이진 트리는 위 그림과 같은 형태로 표햔된다. 구조는 최상위 노드(위 그림에서는 8)를 기준으로 아래에 자식 노드가 존재 한다. 자식노드의 왼쪽은 노드 보다 작은 수, 오른쪽은 노드 보다 큰 수가 배치된다. 그리고 그 하위 노드들도 위와 같은 방법으로 중복 없이 정렬하면 트리가 완성된다. 이진트리는 중복 없이 최상위 노드를 기준으로 크기에 따라 정렬하기 때문에 효율적으로 탐색할 수 있다. 탐색 유형에는 총 3가지가 있으며 간단히 정의하면 아래와 같다. 1. 전위순회 : 부모 방문 -> ..

이번에는 탐색 문제 유형 중 하나인 봉우리 개수 찾는 문제에 대하여 정리를 해보려고 한다, 문제는 다음과 같다. > N*N 격자판이 주어지고, 각각의 격자에는 높이가 들어가 있다. 각 격자를 기준으로 상하좌우를 비교했을 때 가장 큰 높이가 봉우리일 때, 봉우리 개수를 구하라. (단 격자판의 가장자리는 모두 0으로 초기화 한다.) # 접근 방법 위 그림과은 3*3 행렬이 주어진 후, 격자판 가장자리를 0으로 초기화 했을때의 그림이다. 2차원 배열을 탐색하는 문제이기 때문에 이중 for문으로 2차원 배열을 탐색한다. 배열의 각 요소를 탐색하면서 상하좌우로 크기 비교를 진행한다. 만약 matrix[i][j] 를 탐색한다고 했을때, matrix[i+1][j] matrix[i-1][j] matrix[i][j+1]..

이번에는 탐색 유령 중 하나인 너무 유명한 괄호 문제에 대하여 정리해보려고 한다. 문제는 다음과 같다. > 괄호로 이루어진 문자열이 주어지고, 짝이 맞으면 YES, 틀리면 NO를 반환, (단, 문자열의 길이는 6으로 가정한다.) # 접근 방법 접근 방법은 위 그림과 같다. 먼저 주어진 문자열의 처음 길이를 저장 후, 반복문을 돌려 짝이 맞는 괄호를 발견하면 공백으로 제거해주는 작업을 반복한다. 그 다음 처음 문자열 길이와 나중 문자열 길이를 비교 후 YES, NO를 판별한다. # 풀이 def check_func(values): answer = [] str_list = ['[]', '{}', '()'] # 인자로 받은 문자열로 이루어진 리스트 탐색 for element in values: first = 0..

이번에는 알고리즘 유형 중 하나인 큐 유형에 대하여 정리 해보려고 한다. 문제 유형으로는 숫자로 이루어진 문자열과 임의의 숫자 m을 입력 받은 후 문자열에서 1부터 m 까지 카운트 하며, 차례대로 배열 뒤로 배치 후, m번째 있는 숫자를 제거하는 과정을 반복 수행하여 최종적으로 남은 숫자를 반환하는 문제이다. 아래 그림은 1 부터 8까지 숫자들을 정렬 후, 3번째에 위치한 숫자들을 차례대로 제거하는 로직이다. # 풀이 과정 큐는 자료구조는 FIFO(First in First out) 구조를 가지고 있기 때문에 리스트의 가장 앞에 있는 인덱스 부터 제거하는 해당 문제 유형에서 적용하기 알맞다. 파이썬에서는 deque라는 모듈을 지원하기 때문에 리스트 앞에 있는 인덱스를 제거할때는 popleft( ) 모듈을..

이번에는 알고리즘 유형 중 하나인 스택에 대해 정리 해보려고 한다. 문제 유형으로는 숫자로 이루어진 문자열에서 m개의 숫자를 제거할때 가장 큰 수를 출력하는 문제를 선택하였다. # 풀이 과정 입력 받은 m개의 숫자 만큼 반복문을 돌리면서 제거할 숫자를 탐색해야 한다. 탐색하기 위한 가장 좋은 방법은 아래와 같이 "7' 이라는 숫자를 예를 들어 설명하자면, 7 앞에 있는 4와 2는 7 보다 작은 숫자 이기 때문에 제거할 수 있다. 즉, 연속된 두 인덱스의 숫자를 비교하여 크면 stack에 담고 작으면 pop 시킬 수 있다. 이러한 과정을 m번 만큼 반복한 후 최종 stack을 return 시키면 된다. 위 과정대로 m번 만큼 반복이 되어서 깔끔하게 정답이 나올 수 있지만, 예외적으로 리스트의 길이 만큼 탐..

이번에는 알고리즘 유형 중 이분 검색에 대해 정리하려고 한다. 문제 유형으로는 숫자로 이루어진 문자열을 Input으로 받은 후 오름차순으로 정렬하여 특정 숫자의 인덱스 값을 반환하는 문제이다. # 풀이 과정 먼저 입력받은 문자열을 sort 메서드로 오름차순으로 정렬한다. 그 다음 아래 그림과 같이 첫 인덱스를 Left 그리고 마지막 인덱스에 Right를 설정한다. 그리고 Left와 Right의 평균 값을 Middle로 설정한다. 그 후 Middle 값이 찾고자 하는 숫자와 같은지 비교 후 같으면 Middle 값의 인덱스를 리턴하고, 그게 아니라면 Middle과 크기 비교 후 Middle이 크면 Left = Middle + 1 로 설정하고 그게 아니라면 Right = Middle -1 로 설정한다. 그리고..

이번에는 탐색 유형 중 하나인 회문 문자 검사(대소문자를 구분하지 않음) 유형에 대해 정리해보려고 한다. 회문 문자는 문자를 뒤로 뒤집어서 읽어도 같은 문자열이며, 문자열 중앙을 기준으로 대칭인 특징이 있다. 따라서 해당 유형의 알고리즘을 풀떄도 이러한 특징을 이용해서 풀어보려고 한다. # 풀이 과정 먼저 대소문자를 구분하지 않기 때문에 리스트에 있는 모든 요소들을 대문자 혹은 소문자로 변환하는 작업이 필요하다. 필자는 " .lower() " 메서드를 사용하여 모두 소문자로 변환하였다. 그 다음 아래와 같이 대칭되는 요소들을 비교하였다. Input으로 주어지는 문자열의 길이를 2로 나눈 후 그 횟수 만큼 아래와 같이 비교하면 된다. 문자열이 홀수로 주어지더라도 가운데 값은 비교하는데 의미가 없기 때문에 ..

# 문제 - 공통된 시작 단어(prefix)를 반환 # 풀이 def get_prefix(strs): if len(strs) == 0: return '' result = '' strs = sorted(strs) print(strs) for i in strs[0]: if strs[-1].startswith(result+i): result += i print(res) else: break return result # 해설 - 요소가 문자열인 리스트를 받아 알파벳 순으로 정렬 - strs = ['flue', 'fly', 'flower'] 일때 strs = sorted(strs) 을 하면 strs = ['flower', 'flue', 'fly'] 으로 정렬되는 것을 알 수 있음 - 그 후 첫번째 인덱스 문자열과 ..