[알고리즘] 카카오 공채 - 자물쇠와 열쇠 Python
안녕하세요 오랜만에 알고리즘 풀이를 포스팅해보려 합니다 :) 오늘 포스팅할 문제는 카카오 blind recruitment에 나왔던 '자물쇠와 열쇠' 입니다. programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr [문제 설명] [제한사항 & 입출력 예] 이 문제는 2차원 배열을 잘 다룰 수 있는지 확인하는 문제로, 2차원 배열의 회전과 이동방법을 구현해서 완전탐색을 수행하면 풀리는 문제입니다. [접근 방식] 1. key가 회전 가능하기 때문에, key를 회전시키기 위한 rotat..
[알고리즘] Dynamic programming (동적 계획법) 완전정복 with Python
동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 여러 개의 소문제로 분할하여...??? 응?? DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ 바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다. 이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한..
[알고리즘] 탐색(2) - 레드 블랙 트리
이진 탐색 트리의 경우 탐색에 소요되는 평균 시간 복잡도는 O(logN)이지만 최악의 경우 O(N)이 나오게 되는데요. 다음과 같이 한쪽으로 편향되어 있을 때, 즉 트리의 균형이 맞지 않을 때 탐색에 소요되는 시간이 증가하게 됩니다. 그래서 나온 것이 균형 트리(balanced tree)입니다. 균형 트리는 신규 노드 삽입시 특정 조건을 만족하도록 하여 균형 잡힌 트리를 만들어주게 됩니다. 대표적인 균형트리에는 레드-블랙트리, AVL트리 등이 있는데요. 오늘 알아볼 균형 트리는 레드-블랙 트리입니다. 레드-블랙트리는 이름에서 볼 수 있듯이 검정색 노드와 빨간색 노드를 사용하는 트리로 균형 잡힌 이진 탐색 트리라고 할 수 있습니다. 레드 블랙 트리는 신규 노드(신규 노드는 색상 레드) 삽입 시 다음과 같이..
[알고리즘] 탐색(1) - 이진 탐색, 이진 탐색 트리 with Python
탐색 알고리즘? - 컴퓨터에 저장된 자료를 신속하고 정확하게 찾아주는 알고리즘 이진 탐색(binary search) 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 탐색 시간 복잡도는 O(logN) 탐색 방법: 분할-정복 방법 사용 ex) 정렬된 배열 [12,15,23,48,62,98,111,130] 에서 23을 찾는다면?? 1. 가운데 값 선택 -> 48 2. 우리가 찾고자하는 23은 48 좌측에 위치함으로 탐색범위가 12~23으로 줄어듬, 줄어든 탐색범위에서 중간 값 선택 -> 15 3. 23은 15 우측에 위치, 값은 하나만 남게 되고 이 값은 23과 일치 소스코드(파이썬) def binary_search(a:list, search_key): left, right = 0, len(a) wh..