lsh424

이 문제 포스팅할 생각이 없었는데, 생각보다 테스트케이스 5번과 10번에 대해 어려움을 겪는 사람들이 많은것 같아서 포스팅해보려구 합니다 ㅎㅎ (저도 5번, 10번 통과가 안되어서 뭐가 문제인지 헤멨어요 ㅜㅜ) programmers.co.kr/learn/courses/30/lessons/17679 코딩테스트 연습 - [1차] 프렌즈4블록 프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록". 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙 programmers.co.kr 문제는 위와 같은 격자 배열에서, 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임입니다. 해당 블록이 사라지면 위에 있..

오늘은 정규표현식에 대해 정리해보려고 합니다. 정규표현식을 모르는 사람이 표현식을 보면 매우 난해하게 느껴지지만 알고 사용하면 정말 정말 유용하기 때문에, 겁먹지 마시고 공부해보시길 바랍니다 (문자열 처리에 수십 줄의 코드를 작성해야 할 걸 단 몇 줄 만에 끝낼 수 있거든요!) 정규표현식은 특정한 규칙을 가진 문자열의 집합을 표현하는 데 사용하는 형식 언어 입니다. (위키 참고) 이 정규표현식을 사용하면 특정한 규칙을 만족하는지 유효성 검사에 유용하기 때문에 사용자가 입력한 이메일이나 비밀번호가 우리가 만들어 놓은 패턴 혹은 규칙과 부합하는지 쉽게 확인할 수 있습니다. 우선 정규표현식을 사용하려면 사용방법을 알아야겠죠? 정규 표현식에는 다음과 같은 *메타 문자들이 사용됩니다. * 메타 문자: 원래 그 문..

안녕하세요 오랜만에 알고리즘 풀이를 포스팅해보려 합니다 :) 오늘 포스팅할 문제는 카카오 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..

스트링 편집 거리(string edit distance) 알고리즘이란 두 문자열의 유사도를 측정하기 위해 사용되는 알고리즘으로 Levenshtein distance(LD)라고도 합니다. 스트링 편집 거리 알고리즘은 논문, 보고서 등의 표절 검사, DNA 염기 서열의 유사도 검사 등에 사용되어지는데요. 두 문자열의 유사도는 S: 원래 스트링 T: 비교 스트링이라 했을 때 S -> T로 변환하는데 필요한 삽입, 삭제, 대치 연산의 최소 비용(최소 편집 횟수)을 구함으로써 판단합니다. (비용이 작게 나올수록 유사도가 큼) 만약 GUMBO라는 단어와 GAMBOL이라는 단어의 편집 거리를 구해보면, U -> A로 대치 (비용 +1), 맨 마지막에 L 추가 (비용 +1)로 편집 거리는 2가 되게 됩니다. (삽입, ..

동적 계획법 - 주어진 문제를 여러 개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 또 여러 개의 소문제로 분할 가능하다. 각 소문제는 원래 주어진 문제와 동일한 문제이지만 입력의 크기가 작다. 여러 개의 소문제로 분할하여...??? 응?? DP를 처음 공부하신다면 이게 무슨 말이지? 이해가 잘 안 가실 수 있으실 텐데요. 그래서 하나의 좋은 예시가 있습니다 ㅎㅎ 바로 피보나치 수열인데요. 피보나치 수는 1, 1, 2, 3, 5, 8... 로 다음과 같은 점화식으로 나타낼 수 있습니다. 이제 이런 피보나치 수열을 다음과 같이 분해해서 트리 형태로 나타내 보면, 소문제가 상위 문제를 해결하기 위해 사용되는 것을 볼 수 있습니다. 이 말이 즉, 위에서 설명한..

AVL트리 역시 레드-블랙 트리와 마찬가지로 자가 균형 이진 탐색 트리입니다. 레드-블랙 트리와 다른 점은 균형(balance)을 유지하기 위해 적용하는 조건이 다른데요. 그래서 같은 자가 균형 이진 탐색 트리이지만 같은 키를 삽입해도 트리의 결과는 다르게 나올 수 있습니다. ex) KEY = [2, 1, 8, 9, 7, 3, 6, 4, 5] 삽입 시 AVL트리 조건은 다음과 같습니다. 1. *높이 차가 2 이상이 되면 회전을 통해 높이차를 1 이하로 유지 * 높이 차 = 오른쪽 서브 트리의 높이 - 왼쪽 서브 트리의 높이 조건은 엄청 간단하죠?? 여기서 높이 차에 대해 예시를 통해 설명드리자면 각각의 노드 옆에 높이차를 적게 되는데, 이 높이 차는 해당 노드의 우측 서브 트리 높이- 왼쪽 서브 트리 높..

레드 블랙트리 개념설명에서 이어지는 포스팅으로 레드-블랙트리 개념에 대해 잘 모르시면 이 글을 먼저 읽고 와주세요! 레드블랙 트리 파이썬 코드 class Node(): def __init__(self, data): self.data = data self.parent = self.left = self.right = None self.color = 'Red' # 신규 삽입되는 노드는 항상 빨강 class RedBlackTree: # 조부모 노드 찾기 def find_grandparent_node(self,node): if (node != None and node.parent != None): return node.parent.parent else: return None # 삼촌 노드 찾기 def find_u..

이진 탐색 트리의 경우 탐색에 소요되는 평균 시간 복잡도는 O(logN)이지만 최악의 경우 O(N)이 나오게 되는데요. 다음과 같이 한쪽으로 편향되어 있을 때, 즉 트리의 균형이 맞지 않을 때 탐색에 소요되는 시간이 증가하게 됩니다. 그래서 나온 것이 균형 트리(balanced tree)입니다. 균형 트리는 신규 노드 삽입시 특정 조건을 만족하도록 하여 균형 잡힌 트리를 만들어주게 됩니다. 대표적인 균형트리에는 레드-블랙트리, AVL트리 등이 있는데요. 오늘 알아볼 균형 트리는 레드-블랙 트리입니다. 레드-블랙트리는 이름에서 볼 수 있듯이 검정색 노드와 빨간색 노드를 사용하는 트리로 균형 잡힌 이진 탐색 트리라고 할 수 있습니다. 레드 블랙 트리는 신규 노드(신규 노드는 색상 레드) 삽입 시 다음과 같이..

탐색 알고리즘? - 컴퓨터에 저장된 자료를 신속하고 정확하게 찾아주는 알고리즘 이진 탐색(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..

이전에 시간 복잡도 O(N^2)인 정렬 알고리즘들에 대해 포스팅했었는데요. 오늘은 시간 복잡도가 O(NlogN)인 정렬 알고리즘에 대해 알아보려 합니다! 시간복잡도가 O(NlogN)인 대표적인 정렬에는 퀵 정렬, 합병 정렬, 힙 정렬이 있습니다. 1. 퀵 정렬 분할 정복(divide and conquer)기법을 사용한 정렬로, 평균적으로 아주 빠른 성능을 갖는 알고리즘입니다. 정렬 방법 1. 주어진 리스트에서 하나의 원소를 고른다. (피벗) 2. 피벗을 기준으로 두 개의 파티션으로 분할한다. 파티션 1: 피벗보다 작은 원소, 파티션 2: 피벗보다 큰 원소 3. 분할된 파티션에 대해서도 리스트의 크기가 0 혹은 1이 될 때까지 1,2 과정을 반복한다. 소스코드(파이썬) def quick_sort(a: li..