본문 바로가기

Algorithm

 (38)
Algorithm/개념정리 탐색 알고리즘(Search Algorithm)의 이진 탐색(Binary Search) 개념 정리 이진 탐색 탐색 알고리즘에는 크게 순차(Linear) 탐색과 이진 탐색(Binary Search)으로 구분된다. 순차 탐색은 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법이고, 이진 탐색은 정렬되어 있는 리스트에서 시작점, 끝점, 중간점으로 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 예시 이미 정렬된 10개의 데이터 중에서 이진 탐색을 통해 값이 4인 원소를 찾는 과정을 살펴보자. [ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]탐색 과정 Step 1 시작점: arr[0], 끝점: arr[9], 중간점: arr[4] (소수점 이하 제거) * * * [ 0, 2, 4, 6, 8, 10, 12, 14, 16, 18 ]찾고자 하는 값(4)이 중간점의 값(8..
Algorithm/개념정리 정렬 알고리즘(Sort Algorithm)의 퀵 정렬(Quick Sort) 개념 정리 들어가며 파이썬을 사용하는 경우 정렬해야 하는 상황에서 sort()를 사용하여 내부적인 정렬을 해주거나, sorted()를 사용하여 정렬된 새로운 값을 받도록 하는 경우가 많다. def use_sort(arr: List) -> List: arr.sort() return arr def use_sorted(arr: List) -> List: return sorted(arr) 이러한 정렬 함수가 내부적으로 어떻게 동작하는지 알기 위해서는 적어도 퀵 정렬 또는 병합 정렬 정도는 알고 있어야 한다고 한다. 따라서, 이번에는 퀵 정렬에 대해서 공부한 내용을 정리해보겠다. 퀵 정렬 퀵 정렬(Quick Sort)에서는 중심점(pivot)과 파티션(partition)이라는 개념이 존재하며, 이는 퀵 정렬의 동작 원리이기..
Algorithm/Baekjoon Baekjoon #2606 - 바이러스 풀이(단방향과 양방향 그래프) 문제 문제의 내용을 요약하자면, 서로 연결된 여러 대의 컴퓨터 중 첫 번째 컴퓨터가 바이러스에 걸렸을 때 바이러스에 감염되는 컴퓨터의 수를 구하는 것이다. 예를 들어, 아래 그림과 같이 컴퓨터가 연결되어 있고, 이 중 1번 컴퓨터가 바이러스에 감염되었다면 1번 컴퓨터와 연결된 모든 컴퓨터(2, 3, 5, 6)의 수량을 출력해야 한다. 입력으로 주어지는 값은 다음과 같다. 이때, 컴퓨터의 수가 7이면, 1번부터 차례대로 번호가 매겨진다. 줄 기호 내용 예시 첫 번째 줄 N 컴퓨터의 수 7 두 번째 줄 M 직접 연결된 컴퓨터 번호 쌍의 수 6 세 번째 줄 + M 직접 연결된 컴퓨터 번호 쌍 1 2 2 3 1 5 5 2 5 6 4 7 풀이 총 두 번의 시도 끝에 성공하였다(소스코드). 정말 놓치기 쉬운 부분을..
Algorithm/LeetCode LeetCode #017 - Letter Combinations of a Phone Number(전화번호 문자 조합) 풀이(2가지 방식) 문제 문제의 내용을 간단히 요약하자면, 입력받은 번호에 해당하는 알파벳을 순서대로 조합한 문자열을 반환하는 것이다. 예를 들어, 아래와 같이 '234'를 입력받았을 때, 조합한 문자열의 길이는 입력받은 문자열의 길이와 동일하게 3이어야 하며, 각각 ['abc'] + ['def'] + ['ghi'] 순서대로 조합된 모든 문자열을 찾아야 한다. input : ['234'] output: ['adg', 'adh', 'adi', 'aeg', 'aeh', 'aei', 'afg', 'afh', 'afi', 'b..
Algorithm/LeetCode LeetCode #561 - Array Partition I(배열 파티션 1) 풀이 문제 문제에서는 길이가 2n인 정수 리스트를 입력받고, 정수를 n쌍으로 묶은 후 각각의 쌍의 최소값을 합한 결과가 최대가 되도록 하여 반환할 것을 요구하고 있다. 내용을 이해하는데 약 30분 정도 소요되었으며, 생각보다 간단하게 해결할 수 있었다. 길이가 6인 정수 리스트를 입력 받는 경우 n은 3이 되고, 리스트를 3조각으로 나누고, 나누어진 조각의 최소값들을 모두 더했을때 가장 큰 값이 되어야 하는 것이다. 풀이 입력받는 리스트를 오름차순으로 정렬하고, 합계를 0으로 초기화한다. nums.sort() sum = 0 입력받은 리스트를 반복하면서 짝수(0, 2, ..., 2n) 번째 인덱스에 해당하는 값을 1의 합계에 더하고, 반복이 종료되면 합계를 반환한다. for i in range(0, len(nu..
Algorithm/LeetCode LeetCode #015 - 3Sum(세 수의 합) 풀이 문제 문제에서는 정수 값을 리스트로 입력받아 세 개의 요소로 구성된 2차원 리스트(ex) [[i, j, k], [x, y, z]]로 반환할 것을 요구하고 있다(이때, 하나의 리스트([i, j, k])의 값은 서로 중첩되면 안 되며, 요소의 합이 0이 되어야 한다). 약 2시간 동안 다음과 같은 두 번의 시도를 하였는데 모두 실패하였고, 결국에는 교재의 풀이 과정을 들여다볼 수 밖에 없었다. 세 개의 요소를 가진 리스트를 만들기 위해 반복문으로 접근하였으나 시간 초과로 인해 실패하였다. 교재에서 언급한 투 포인터 방식과 유사하게 구현은 하였으나, 중복 제거 처리 및 이미 확인한 값을 건너뛰는 코드를 구현하지 않아 실패하였다. 실패 내용 중 첫 번째 방식과 같이 매우 단순 무식한 알고리즘을 브루트 포스라고 ..
Algorithm/LeetCode LeetCode #409 - Longest Palindrome(가장 긴 팰린드롬) 풀이 문제 문제에서 등장하는 팰린드롬은 문자열의 가운데를 기준으로 하여 2개로 나누었을 때, 첫 번째 문자열과 두 번째 문자열의 역순이 같은 문자열을 말하며 다음과 같이 규칙성을 정리해보았다. 문자열을 구성하는 문자의 개수가 모두 짝수인 경우 모든 문자를 팰린드롬으로 배치 가능 ex) 'aabbcc' -> 'aabbcc' 문자열을 구성하는 문자의 개수 중 홀수가 포함되어 있는 경우 개수가 홀수인 문자를 짝수로 활용하고, 가운데에 홀수인 문자로 하여 팰린드롬으로 배치 가능 ex) 'aaabbbccc' -> 'abcccba' 따라서. 문자열을 구성하는 문자의 개수가 홀수인 경우 이를 짝수로 만들고, 문자열의 가운데에 끼워줄 홀수 개의 문자 1개를 나중에 더..
Algorithm/LeetCode LeetCode #622 - Design Circular Queue(원형 큐 디자인) 풀이 문제 문제에서 나오는 원형 큐는 FIFO 정책에 따라 연산을 수행하고 마지막 위치를 첫 번째 위치에 연결하여 원을 만드는 선형 데이터 구조로, 링 버퍼라고도 한다. 원형 큐의 장점 중 하나는 공간을 활용할 수 있다는 것이다. 일반적인 큐에서는 데이터가 가득차면 큐에 공간이 있어도 다음 요소를 삽입할 수가 없다. 그러나, 원형 큐를 사용하면 공간을 사용하여 새로운 값을 저장할 수 있다. 문제에서 구현해야 할 MyCircularQueue 클래스의 메소드는 다음과 같다. __init__(k: int) -> None : 큐 개체의 크기를 k로 초기화 Front() -> int : 큐의 맨 앞의 데이터를 가져오되, 비어있는 상태인 경우 -1을 반환한다. Rear() -> int : 큐의 맨 뒤의 데이터를 가져오되..
Algorithm/LeetCode LeetCode #232 - Implement Queue using Stacks(스택을 이용한 큐 구현) 풀이 문제 2개의 스택만을 사용하여 FIFO 큐를 구현하여야 하는 문제이다. 구현된 큐는 일반 큐의 모든 기능(push, pop, empty)를 지원하여야 하며 구현해야 하는 MyQueue 클래스는 다음과 같다. push(x: int) -> void : x를 큐의 맨 뒤에 넣는다. pop() -> int : 큐의 가장 앞에 있는 요소를 삭제하고 반환한다. peek() -> int : 큐의 맨 앞에 있는 요소를 반환한다. empty() -> boolean : 큐가 비어있으면 true, 그렇지 않으면 false를 반환한다. 이때, 아래 사항을 참고하여야 한다. 스택의 기본 연산(push to top, peek or pop from top, size 및 is empty)만 사용하여야 한다. 언어에 따라서는 스택이 ..
Algorithm/LeetCode LeetCode #049 - Group Anagrams(그룹 애너그램) 문제 풀이 문제 문제의 애너그램은 특정 문자열의 문자를 재배치하여 만든 새로운 문자열이며, 문제에서는 여러 개의 문자열이 배열로 주어질 때 애너그램으로 짝짓고 반환할 것을 요구하였다. 문제를 보자마자 엑셀에서의 '중복 제거'가 떠올랐다. 즉, 특정 대상의 통계를 구하기 위해서는 해당 대상을 중복 제거하여야 한다. 이를 가능케 하는 방법으로 다음과 같이 크게 2가지를 떠올려보았다. 문자열을 구성하는 문자의 ascii 코드의 총 합을 기준으로 중복 제거가 가능하다. 문자열을 구성하는 문자를 정렬하면 중복을 제거할 수 있다. 이 중에서 두 번째 방법이 훨씬 직관적인 코드로 나타낼 수 있다고 생각하여 두 번째 방법으로 시도해보았다. 풀이 딕셔너리를 사용한 해시테이블 생성 딕셔너리의 key는 문자열의 문자를 ..

티스토리툴바