Python
1.[알고리즘] BFS (너비 우선 탐색)
BFS는 너비 우선 탐색이라고도 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘BFS는 큐 자료구조를 이용하며, 구체적 동작 과정은 다음과 같음탐색 시작 노드를 큐에 삽입하고 방문처리큐에서 노드를 꺼낸 후, 해당 노드에 인접 노드 중 방문하지 않은 노드
2.[알고리즘] DFS (깊이 우선 탐색)
DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘DFS는 스택 자료구조(혹은 재귀함수)를 이용하며, 구체적 동작과정은 다음과 같음탐색시작노드를 스택에 삽입하고 방문 처리스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도
3.[알고리즘] 누적 합
위 1차원 배열의 누적 합 결과는 1, 3, 6, 10, 15, 21, 28, 36, 45, 55가 된다.여기서 예를 들어 3번째 항부터 5번째 항까지의 누적 합은 3 + 4 + 5 = 12가 된다. 누적 합 리스트에서 결과를 가져온다면 prefix_sum\[5] -
4.[알고리즘] 중국인의 나머지 정리
중국인의 나머지 정리백준 알고리즘 문제를 풀면서 중국인의 나머지 정리를 이용하는 문제가 여럿 있었다. 그래서 여러 예제를 통해서 어떤 식으로 문제를 풀고 접근해야하는지 알아보기 위해서 공부했다.관련 문항 정리\[백준 6064번 카잉 달력]\[백준 1476번 날짜 계산]
5.[알고리즘] 백트래킹(Backtracking)
백트래킹(Backtracking)이란?주어진 문제의 답을 구하기 위해 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다.백트래킹의 함수 구조는 다음과 같다.\[백준 15649번 N과 M (1)]\[백준 15650번 N과 M (2)]\[백준 1565
6.[알고리즘] 재귀
재귀(Recursion)란?어떠한 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우를 재귀라고 한다.재귀를 사용하는 대표적인 예로 양의 정수의 곱을 구하는 팩토리얼(factorial)이 있다. 간단한 코드를 통해서 재귀에 대해 알아보자.
7.[알고리즘] DP
Python Python Dynamic Programming Implementation question list가장 기본적인 DP문제 리스트(꼭 본인 힘으로 해결해보고 코드 리뷰 진행할 것)평범한 배낭(백준 12865번)가장 긴 증가하는 부분 수열(백준 11053번)L
8.[알고리즘] 힙
최소 힙 작성 Python 코드import heapqheap = \[]heapq.heappush(heap, -3)heapq.heappush(heap, -2)heapq.heappush(heap, -5)print(heap) \`\`\`
9.[알고리즘] 정렬 - 병합 정렬
10.[알고리즘] 시간복잡도
파이썬으로 PS를 공부하다 보면 시간초과(TLE)가 발생하는 일이 많이 발생한다. 항상 코드를 짜면서 '이게 적합할까?' 이런 생각들을 하게 된다.아래 링크는 파이썬 메소드별 시간복잡도가 정리되어있는 사이트이다. https://www.ics.uci.edu/~p
11.[알고리즘] CCW알고리즘
CCW알고리즘이란?CCW(Counter Clock Wise)알고리즘은 2차원 평면에 존재하는 3개의 점 A, B, C가 있을 때 점 3개를 이은 직선의 방향을 알고자 할 때 유용한 기하학 알고리즘이다.나올 수 있는 경우의 수는 3가지이며 시계, 반시계, 일직선 방향이
12.[알고리즘] 분리 집합
서로소 집합(Disjoint Sets)란 공통 원소가 없는 두 집합을 의미한다.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원한다.합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로
13.[알고리즘] 0-1 너비 우선 탐색
0-1 BFS란?BFS는 BFS인데 특수한 환경에서 작동할 수 있는 BFS를 0-1 BFS라고 한다.0-1 BFS는 가중치가 0과 1로만 이루어진 그래프에서 최단 경로를 찾고자 할 때 주로 사용된다.0-1 BFS의 동작 과정deque(덱)의 앞에서 popleft를 통해
14.[알고리즘] 최소 공통 조상(Lowest Common Ancestor)
N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 있다. 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며 루트 노드의 번호는 1번이다.두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력
15.[알고리즘] 최장 증가 부분 수열(LIS) 알고리즘
LIS(Longest Increasing Subsequence)란, 가장 긴 증가하는 부분 수열을 말한다.Q. 리스트 6, 2, 5, 1, 7, 4, 8, 3이라는 배열이 존재한다. 이 배열의 LIS를 구해라.A. 2, 5, 7, 8Code위의 알고리즘의 시간복잡도는
16.[알고리즘] 선형 탐색과 이진 탐색
* 선형 탐색 알고리즘(Linear Search Algorithm) 가장 원시적인 형태의 데이터 탐색 알고리즘 리스트에서 찾으려고 하는 값을 맨 앞부터 끝까지 차례대로 탐색해 찾는 것 검색할 리스트의 길이가 길면 길수록 비효율적이지만 구현 코드 자체는 단순하여 구
17.[자료구조] 자료구조, 얕은 복사(Shallow Copy)와 깊은 복사(Deep Copy)
얕은 복사(Shallow Copy)와 깊은 복사(Deep Copy)id(a) 값과 id(b) 값은 다르게 되었지만 그 내부의 객체 id(a\[0])과 id(b\[0])은 같은 주소를 가리키고 있다.(id값은 다르지만 id가 가리키는 메모리 주소가 같다.)재할당하는 경우
18.[자료구조] python 자료형별 시간복잡도
List functions time complexity|Operation|Example|Big-O|Notes|\|:-----------------:\|:-----------------:\|:-----------------:\|:-----------------:\||In
19.[알고리즘] 정렬 알고리즘
정렬 알고리즘이란?원소들을 번호 순이나 사전 순서와 같이 특정한 기준을 적용해 순서대로 열거하는 알고리즘대표적인 정렬 알고리즘으로는 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있고 다른 정렬로는 카운팅 정렬, 파이썬 메소드에 의한 정렬이 있다.버블
20.[알고리즘] 최단 경로 알고리즘
다익스트라 알고리즘은 한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘이다.플로이드-워셜 알고리즘은 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우에 사용할 수 있는 최단 경로 알고리즘이다.다익
21.[알고리즘] 크루스칼 알고리즘
신장 트리그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 말한다.모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다.가능한 신장 트리 예시를 보면 그래프의 모든 노드를 포함하면서 사이클이 존재하지 않기
22.[알고리즘] 서로소 집합 자료구조
서로소 집합(Disjoint Sets)이란 공통 원소가 존재하지 않는 두 집합을 의미한다.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산을 지원한다.합집합(Union) : 두 개의 원소가 포함된 집합을 하나의
23.[알고리즘] 벨만 포드 알고리즘
벨만 포드(Bellman-Ford) 최단 경로 알고리즘음수 간선이 포함된 상황에서의 최단 경로 문제에 사용되는 알고리즘위의 그래프처럼 모든 간선이 양수라면 다익스트라 알고리즘을 사용하면 된다.하지만 위의 그래프처럼 일부의 음수 간선이 포함된 경우 어떻게 계산할 수 있을
24.[알고리즘] 정렬 - 퀵 정렬
퀵 정렬 역시 분할정복(Divide and Conquer) 기법을 사용한다. 피벗(Pivot)이란 개념의 기준값을 활용해 피벗보다 작은 값은 왼쪽에, 피벗보다 큰 값은 오른쪽에 배치한다.피벗을 어떤 값을 기준으로 하냐에 따라 성능이 달라지니 잘 봐야 한다.★어떤 값을
25.[알고리즘] 냅색(knapsack) 알고리즘
배낭 문제(Knapsack Problem)의 한 종류인 0-1 배낭 문제를 해결하는 동적 프로그래밍 알고리즘
26.[알고리즘] 위상정렬 알고리즘
위상 정렬이란, 사이클이 없는 방향 그래프의 모든 노드를 방향성을 거스르지 않도록(일의 선후관계 존재) 순서대로 나열하는 것을 말하는 정렬이다.위상 정렬에선 진출 차수보다 진입 차수가 더 중요하다. 이 때, 진출 차수란 특정한 노드로부터 뻗어나가는 간선의 개수, 진입