Algorithm
1.[알고리즘] 1. 완전탐색 (Brute Force Search)
완전탐색 (Brute Force)
2.[알고리즘] 2. 탐욕적 기법 (Greedy Algorithm)
눈 앞의 가장 큰 이익만을 좇는 방법이다.성질이 동일하게 보존되므로 아까 했던 전략을 계속 취해도 정답을 얻을 수 있다.문제를 딱 보고 그리디인지 알기가 쉽지 않다.👉 풀이 : 가장 큰 금액의 동전을 사용할 수 있는 최대개수를 무조건 다 사용하는 것!왜 이게 성립할까
3.[알고리즘] 3. 분할정복 (Divide and Conquer)
말 그대로 두 단계 분할과 정복으로 나눠서 해결하는 것을 말한다.
4.[알고리즘] 4-1. 동적계획법 DP (Dynamic Programming)
프로그래밍이라는 단어는 컴퓨터 언어로 코딩하는 것이 아니라 계획하는 것을 의미하는 바가 크다. 문제를 특수한 형태로 변형시켜 쉽게 풀려는 어떤 과정이다.다이나믹이라는 단어는 이 기법과 아무런 상관이 없대...ㅋㅋㅋㅋ 만든 사람이 그냥 "이름이 멋있어 보여서 붙였다"고.
5.[알고리즘] 5-1. 깊이우선탐색 (DFS)
그래프의 가장 기본적인 정의 정점(vertex)과 간선(edge)의 집합(정점은 노드(node)라고도 흔히들 부름.)간선은 두 정점을 이어주는 역할을 하며, 자기자신을 이을 수도 있고, 간선에 방향이 있기도 하고 없기도 하며, 가중치가 있기도 하고 없기도 하는 등 아주
6.[알고리즘] 5-2. 너비우선탐색(BFS)
DFS는 한 우물만 계속 파다가 끝을 보고 나서야 다른 곳으로 옮기는 데 반해, BFS는 모든 곳을 똑같이 조금씩 판다.BFS가 이루어지는 방식처음엔 0번 정점0번 정점과 인접한 정점 모두 방문!바로 전 단계에서 방문한 1, 2번 정점들로부터 인접한 3, 5, 6, 8
7.[알고리즘] 6. 백트래킹(Backtracking)
완전 탐색의 한 종류... 가능한 모든 조합을 다 시도하는 것부분수열의 합요 문제를 예시로 설명해볼게에0부터 N-1번째 원소까지 순서대로 방문할건데방문마다 이번 원소를 포함시키거나 안시키거나 2가지 선택지를 탐색한다.그렇게 탐색하면서 현재 합이 S가 될 때마다 전역변수
8.[알고리즘] 7. 이분 탐색 (Binary Search)
이분탐색은 앞서 분할 정복 파트에서 쓰였죠?근데 이 이분 탐색 자체가 문제풀이의 키가 되는 경우도 많아요.바로 parametric search의 방법으로 이분 탐색을 이용하는 거다\~~이게 뭐냐면? 문제의 답을 구하지 않고 그냥 아무거나 툭툭 던져보며 답을 찾아가는 거
9.[알고리즘] 8. 구간합 배열(Prefix Sum)
크기가 N인 배열 A가 있을 때, 이것의 prefix sum은 N칸 혹은 N+1칸으로 이루어진 배열이다. 이번엔 N+1칸으로 이루어진 배열로 설명해보겠당!이 경우, S0 = 0 이겠죠?S\[i + 1] = S\[i] + A\[i]로 채워나갈 수 있다.예시로 알아보자
10.[알고리즘] 9. 비트마스킹(Bit Masking)
알고리즘이라기엔... 음 비트를 활용한 테크닉이라고 봐야함! 비트 단위로 값을 보존하는 것.
11.[알고리즘] 10. 투 포인터, 슬라이딩 윈도우
성향이 비슷한 둘을 묶어 설명하겠다!1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가며 원하는 것을 얻는 형태이다.백준 - 2003 수들의 합문제 - N칸의 1차원 배열이 있다. 이 배열의 부분 배열 중 그 원소 합이 M이 되
12.[알고리즘] 에라토스테네스의 체
임의의 수 N까지의 소수를 구하고자 할 때 2부터 N의 제곱근까지 돌며 i의 모든 배수들을 소수에서 제외시키는 방식이다.크기가 N+1인 배열을 하나 준비한다. (arri = i)i = 2 ~ sqrt(N)까지 돌며 i의 배수들을 모두 0으로 바꿔준다. (primeNum
13.[자료구조] 11-1. 트리
나무를 뜻하는 그 트리. 나무를 뒤집어놓은 거 처럼 생겨서 그랬대트리는 그래프의 하위집합인데,①연결 그래프이다. (컴포넌트가 하나)②방향을 무시하였을 때, 싸이클이 존재하지 않는다.\-> ex 이건 ①을 충족하지 못하므로 트리가 아님. {A, B}, {C, D, E}로
14.[자료구조] 이진 탐색 트리 (Binary Search Tree)
🔵
15.[자료구조] 유니온 파인드(union-find)
다른 말로 disjoint-set구조라고도 한다.union연산과 find연산 기본적으로 단 2개만을 지원하는 자료구조이며disjoint한 집합들을 표현하는 자료구조다.이게 표현하려는 집합들은 어떤 두 집합 사이에도 교집합의 원소가 하나도 없고, 모든 집합의 합집합은