모눈종이에 사각사각

프로그래머스 문제를 풀다가 lower bound를 이용해서 풀면 좋은 문제가 있었다. 따라서 lower bound가 무엇인지 공부하면서 내용을 정리해보고자 한다. lower bound와 upper bound는 이진 탐색 트리를 포스팅한 글에서 적은 bisect 모듈과 같은 기능을 한다. lower bound는 bisect_left, upper bound는 bisect_right라고 보면된다. 🍀 Lower Bound - target 값이 들어갈 수 있는 첫 번 째 인덱스를 반환한다. 구현 코드는 다음과 같다. def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = (left+right) // 2 if nums[..

이번 포스팅에서는 0-1 BFS 알고리즘에 대해 알아보고자 한다. 백준 13549 숨바꼭질3 문제를 풀 때 0-1 BFS 알고리즘이 있다는 사실을 알게 되었다. 0-1 BFS는 가중치가 0과 1로만 주어진 그래프에서 최단 경로를 찾고자 할 때 BFS를 응용하여 푸는 것이다. 가중치가 0과 1만 있을 때는 최단거리를 찾을 경우에 다익스트라가 가장 좋은 선택이 아니다. 다익스트라 알고리즘의 시간 복잡도는 \(O(ElogE)\) 혹은 \(O(ElogV)\)인 반면, 0-1 BFS를 사용하면 \(O(V+E)\)의 상수시간으로 문제를 해결할 수 있다. 🍀 0-1 BFS의 동작 과정 deque를 활용해서 진행한다. 1. deque에서 popleft()로 현재 노드를 꺼낸다. 2. 연결된 인접 노드를 살펴본다. 3...

이번 포스팅에서는 다이나믹 프로그래밍에 대해 다뤄보고자 한다. 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀는 알고리즘 기법이다. 특정 조건이 만족되는 문제에서 다이나믹 프로그래밍을 사용하면, 중복되는 연산을 줄일 수 있다. 특정 조건은 다음과 같다. 1. 큰 문제를 작은 문제로 나눌 수 있다. (최적 부분 구조) 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (중복되는 부분 문제) 다이나믹 프로그래밍을 구현하는 방법은 크게 두 가지가 있다. 첫 번째는 Top-down 방식인 메모이제이션(Memoization) 기법이다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모..

이번 포스팅에서는 최단 경로 알고리즘에 대해 다뤄보고자 한다. 최단경로 알고리즘은 이름에도 나와있듯이 가장 짧은 경로를 찾는 알고리즘이다. '길찾기' 문제라고도 불린다. 최단경로 알고리즘은 대표적으로 세 가지가 있다.(컴공 학부수준) 1. 다익스트라 알고리즘 2. 플로이드 워셜 알고리즘 3. 벨만 포드 알고리즘 1, 2번이 코딩테스트에서 가장 많이 등장하는 유형이라고 한다. 먼저 다익스트라 최단 경로 알고리즘에 대해 알아보고자 한다. 🥝 다익스트라 최단 경로 알고리즘 -> 한 지점에서 다른 모든 지점까지의 최단 경로 - 특정한 노드에서 출발하여 다른 노드로 가는 최단 경로를 구해주는 알고리즘 - 기본적으로 그리디 알고리즘으로 분류 (매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문) 동..

이번 포스팅에서는 이진 탐색 알고리즘에 대해 설명하고자 한다. 이진 탐색에 대해 설명하기 전에 먼저 순차 탐색에 대해 알아보자 🍀 [순차 탐색 Sequential Search] 순차 탐색은 말그대로 앞에서부터 순차적으로 하나씩 확인하며 탐색하는 것이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 따라서 시간복잡도는 \(O(N)\)이다. 🍀 [이진 탐색 Binary Search] 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 것이다. 배열 내부의 데이터가 정렬되어 있을 때만 사용할 수 있으며, 정렬 되어 있을 경우, 빠르게 데이터를 찾을 수 있다는 장점이 있다. 이진 탐색은 변수를 3개 사용한다. 1. 시작점 2. 끝점 3. 중간점 찾으려는 데이터와 중간점 위치에 있는 데..

정렬은 데이터를 특정한 기준에 따라 순서대로 나열하는 것이다. 정렬의 종류에는 여러 가지가 있는데, 그중에서 선택정렬, 삽입정렬, 퀵정렬, 계수정렬에 대해 알아볼 것이다. 정렬을 하면 이진 탐색이 가능해지기 때문에 잘 알아두면 도움이 많이 될 것 같다. 우선 정렬의 종류를 알아보기 전에 정렬 알고리즘의 두 가지 성질을 먼저 알아볼 것이다. 🍁 정렬 알고리즘의 두 가지 성질 1. stable vs unstable - 같은 숫지면 입력된 순서가 정렬 후에도 그대로 유지되도록 하는 게 더 바람직하다! -> stable하다! 2. in-place vs not in-place - 정렬을 하면서 추가로 사용하는 메모리의 양 - in-place는 기존 리스트에서 정렬을 하는 것이고, not in-place는 리스트를..

코딩 테스트에서 많이 출제되는 알고리즘 중 하나인 DFS와 BFS에 대해 알아보고자 한다. 계속 공부하지만 문제를 풀 때마다 헷갈리기에, 이번 포스팅을 계기로 확실하게 개념을 익히는 것이 목표이다. 🍀 DFS(Depth-First Search, 깊이 우선 탐색) DFS는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로를 탐색한다. [스택 자료구조를 이용한 DFS 동작 과정] 탐색 시작 노드를 스택에 삽입 -> 방문 처리 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리 -> 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과..

이번 포스팅에서는 그리디 알고리즘에 대해 알아보고자 한다. 그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법이다. 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 그리디 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야 한다. 🍀 거스름 돈 문제 거스름 돈으로 사용할 돈은 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다. 손님에게 거슬러 줘야 할 돈이 N원일 때, 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다. -> 그리디 알고리즘을 활용해 풀 수 있는 대표적인 문제 🍀 정당성 분석 그리디 알고리즘을..