Algorithm
1.[자료구조] 배열과 리스트
메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조인덱스를 사용하여 값에 바로 접근할 수 있다새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다배열의 크기는 선언할 때
2.[알고리즘] 구간 합
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야 한다.합 배열은 기존의 배열을 전처리한 배열이라 생각하면 된다. 이렇게 합 배열을 미리 구해놓으면 기존 배열의 일정 범위의 합을 구하는
3.[알고리즘] 투 포인터
이 문제는 시간 복잡도 분석으로 사용할 알고리즘의 범위부터 줄여야 한다. 우선 문제에 주어진 시간 제한은 2초이다. 그런데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있다. 이런 상황에서는 O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므
4.[자료구조] 스택과 큐
스택 > 스택은 삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조 📖 스택 용어 top: 삽입과 삭제가 일어나는 위치 push: top 위치에 새로운 데이터를 삽입하는 연산 pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek: top
5.[알고리즘] 정렬
자바에서는 sort() 함수를 이용해 쉽게 정렬할 수 있지만 이번에는 정렬을 직접 구현해 문제를 해결해보자.N의 최대 범위가 1,000으로 매우 작기 때문에 O(N²) 시간 복잡도 알고리즘으로 풀 수 있다. 버블 정렬의 시간 복잡도가 O(N²)이므로 버블 정렬 알고리즘
6.[알고리즘] 그리디 알고리즘(Greedy Algorithm)
그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.하지만 코테에서의 대부분 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제된다
7.[알고리즘] 구현 유형 개요
흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까요?풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다.구현 유형의 예시는 다음과 같습니다.알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제실수 연산을 다루고, 특정 소수점 자리까지 출력해야
8.[알고리즘] 그래프 탐색 알고리즘 DFS / BFS
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있다.DFS/BFS는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지Stack<Integer> s = new Stack<
9.[알고리즘] 정렬 알고리즘
⭐ 선택 정렬 > 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복한다. 📝 코드 구현 선택정렬의 시간 복잡도 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 구현 방식에 따라서 사소한 오차는
10.[알고리즘] 이진 탐색 알고리즘
⭐ 이진 탐색 >정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다. 📍 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2n에 비례한다.
11.[알고리즘] 다이나믹 프로그래밍
최단 경로 문제 가장 짧은 경로를 찾는 알고리즘을 의미 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 짖머에서 다른
12.[알고리즘] 최단 경로 알고리즘: Dijkstra
최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미한다.한 지점에서 다른 한 지점까지의 최단 경로한 지점에서 다른 모든 지점까지의 최단 경로모든 지점에서 다른 모든 지점까지의 최단 경로특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산합니다.다익
13.[알고리즘] 최단 경로 알고리즘: Bellman-Ford
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다.시간 C가 양수가 아닌 경우가 있다. C= 0인 경우는
14.[알고리즘] 최소 신장 트리: Kruskal 알고리즘
그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다.최소한의 비용으로 구성되는 신장 트리를 찾아야 할 때 어떻게 해야할까?예를 들어 N개의 도시가 존재하는 상
15.[알고리즘] Union-Find 알고리즘
서로소인 부분집합의 표현그래프/트리의 대표적 알고리즘이다.서로소 집합이란? 공통 원소가 없는 두 집합을 의미한다.서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다.서로소 집합 자료구조는 두 종류의 연산을 지원한다.합집합(Union)두 개의 원소
16.[알고리즘] Union-Find를 활용한 사이클 판별
서로소 집합은 무방향 그래프 내에서의 사이클을 판별할 때 사용할 수 있다.참고로 방향 그래프에서의 사이클 여부는 DFS를 이용하여 판별할 수 있다.각 간선을 하나씩 확인하며 두 노드의 루트 노드를 확인합니다.1) 루트 노드가 서로 다르다면 두 노드에 대하여 합집합(Un
17.[알고리즘] KMP 문자열 매칭 알고리즘
문자열(parent)이 있을 때 그 문자열 안에서 특정한 패턴(pattern)을 찾는 알고리즘문자열(parent) =ABCDEF, 찾을 문자열(pattern) = DEF 인 경우다음과 같은 방식으로 찾을 수 있다.먼저 찾을 문자열인 DE를 가장 앞 부분에 위치시키고 확
18.[알고리즘] 위상 정렬(Topology Sorting)
사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미한다.예시) 선수과목을 고려한 학습 순서 설정위 세 과목을 모두 듣기 위한 적절한 학습 순서는?자료구조 → 알고리즘 → 고급 알고리즘 (O)자료구조 → 고급 알고리즘 → 알고리
19.DFS와 BFS 선택 기준
나는 대체로 DFS를 자주 사용하는 편이다.상대적으로 DFS를 먼저 배우고 자주 사용해서 그런가..그래서 문제마다 DFS, BFS 중 어떤 것을 사용해야 할지 고민한 경험이 많다.코딩 테스트 문제에서 주로 이렇게 3가지 경우로 나뉘는거 같다.DFS or BFS 어떤것이
20.그래프를 저장하는 방법
그래프는 노드와 그 노드들을 연결하는 간선으로 구성된 자료구조다. 그래프는 여러 가지 방법으로 표현될 수 있고, 대표적으로 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), 간선 리스트(Edge List)가 있다.그래프를 2차원 배
21.[알고리즘] 누적합(prefix sum)
누적합에 대해 공부하기 전구간합 개념을 잘 모르겠다면 보고오자!\[Java - Do it!] 구간 합prefixSumx는 1번째부터 x번째까지의 합을 나타낸다.prefixSumx는 (1,1)부터 (x,y)까지의 합이라고 해보자.(인덱스는 1번부터 사용)prefixSum
22.[알고리즘] 최단 경로 알고리즘: Floyd-Warshall
모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산합니다.플로이드 워셜(Floyd-Warshall) 알고리즘은 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행합니다. 하지만, 매 단계마다 방문하지 않은 노드 중에 최단 거리를