AngelPlayer`s Diary

[알고리즘] 이항 계수, 파스칼의 삼각형

문제를 풀기 위한 개념 정리 이항 정리 각 항의 계수 값을 구하는 정리를 의미 이항 계수 다항식을 전개했을 때 각 항의 계수를 의미 $(a+b)^{n}$를 전개 했을 때 나오는 임의의 항 $Sx^{n-a}y^{n-b}$ 에서 $S$가 계수 이항 계수 구하기 이항 계수를 구하는 방법은 1) 경우의 수(조합)을 이용한 방법 2) 파스칼의 정리(삼각형)을 이용한 방법 등이 있음 조합을 이용한 풀이 조합을 이용한 풀이 $_{n}C_{r}$는 $_{n-1}C_{r-1} + _{n-1}C_{r}$로 분해할 수 있음 -> 중복이 발생함 -> 12!을 넘어가면 오버플로우가 일어날 수 있음 - 연산 횟수 10! == 360만 11! == 4000만 12! == 1억 이상 - 조합 개념 https://angelplayer..
개인 공부/알고리즘 2023. 4. 7. 16:36

[알고리즘] 이분(이진)탐색

이분 탐색 배열 등 자료를 두 부분으로 쪼개어 탐색하는 방법 특정 값 또는 자료가 존재하는지를 탐색할 때 사용함 이분 탐색을 위한 배열은 정렬되어 있어야 함 - 로직 1) 탐색 배열의 내 중간 인덱스( (시작 인덱스 + 끝 인덱스) / 2 )를 구함 2) 배열[중간 인덱스]에 위치한 값과 찾으려는 값 비교 3) 비교 결과를 통해 반복 여부 결정 3-1) 배열 값과 같으면 중간 인덱스 반환 3-2) 배열 값이 작으면 "중간 인덱스 + 1"를 시작 인덱스로 지정 3-3) 배열 값이 크면 "중간 인덱스 - 1"를 끝 인덱스로 지정 4) 인덱스 범위가 하나가 될 때까지 1) 2) 3)을 반복 -> 만약 인덱스 범위가 1인데 값이 다르다면 해당 값은 존재하지 않는 값 코드 public class 이분탐색_기본 {..
개인 공부/알고리즘 2023. 3. 11. 09:00

[알고리즘] 최소 신장 트리 (크루스칼, 프림 알고리즘)

최소 신장 트리 (MST) ※ 일반적으로 그래프의 모든 정점이 연결되어 있다고 가정 - 신장 트리 : 모든 정점이 연결되는 트리 - 최소 신장 트리 : 신장 트리 중 사용된 간선들의 가중치가 가장 작은 간선으로만 연결된 트리 - V : 정점 - E : 간선 - 최소 신장 트리의 조건 무방향 가중치 합이 최소 간선의 개수는 $V-1$개 사이클이 없어야 함 - 활용 도시간 비용을 최소화 하는 문제 등에서 사용함 최소 신장 트리를 만드는 방법은 크루스칼과 프림 알고리즘이 있음 크루스칼 알고리즘 (Kruskal Algorithm) - 특징 간선 리스트를 사용 간선을 가중치 기준으로 정렬이 먼저 이뤄저야 함 (간선이 적으면 유리) 순환 여부는 서로소를 통하여 검사함 (매 간선 선택마다 정점의 대표를 확인) 그리디..
개인 공부/알고리즘 2023. 3. 1. 15:00

[알고리즘] 서로소 집합

서로소 서로소 집합 서로 중복된 원소가 없는 집합을 의미 == 교집합이 없는 집합 집합에 속한 특정 멤버(대표자)를 통해 집합을 구분 대표자는 어떤 데이터가 되든 상관이 없음 하나의 집합에는 오로지 하나의 대표자만 가질 수 있음 서로소 집합 연산 1) init : 초기화 2) union : 두 개의 집합을 하나의 집합으로 결합 3) find : 집합 내의 대표자를 찾음 서로소의 최적화 - Rank 사용 기본 서로소 함수에서는 부모를 찾을 때 find의 재귀가 여러 번 발생함 -> 두 서로소를 결합할 때 더 낮은 트리를 더 높은 트리의 자식으로 결합하면 효율성을 높일 수 있음 (데이터에 따라서 사용하지 않을 때 더 빠른 경우가 있음) - Path 사용 find함수의 재귀가 발생하여 부모의 결과를 찾으면, ..
개인 공부/알고리즘 2023. 2. 28. 08:11

[알고리즘] DFS

DFS 개념 DFS : 깊이 우선 탐색 (==장자 우선 탐색) BFS : 너비 우선 탐색 완전 탐색 기법 중 하나 스택(재귀)를 사용함 재귀는 부를 때마다 함수를 시스템 스택에 쌓기 때문에 결국 스택을 사용한 것과 동일한 효과를 가져옴 시작지점에서부터 끝점까지 이동하면서 모든 경우의 수를 탐색 -> 저렴한 비용을 뽑는 문제에서 사용함 앞선 BFS 정리 자료에서 보셨겠지만, DFS는 BFS와 서로 상반되는 개념입니다. DFS는 탐색 시 같은 level에 위치한 노드들을 먼저 탐색하는 BFS와 달리, 한쪽 방향으로 깊이 탐색한 후, 거슬러 올라가면서 나머지를 탐색하는 알고리즘입니다. 그래서 이를 첫번째 자식을 가장 먼저 생각하는 장자 우선 탐색이라고 생각하셔도 좋을 것 같습니다. BFS : 2 -> 7 ->..
개인 공부/알고리즘 2023. 2. 24. 15:07

[알고리즘] BFS (너비 우선 탐색)

BFS 개념 BFS : 너비 우선 탐색 DFS : 깊이 우선 탐색 그래프를 탐색하는 기법 BFS 구현을 위해서는 Queue를 사용 BFS는 너비 우선 탐색 기법으로 깊이 우선 탐색인 DFS와 상반되는 개념입니다. DFS와 BFS는 모두 그래프를 탐색하는 기법입니다. 가령 위와 같은 트리가 존재한다면, BFS는 위에 위치한 노드부터 순차적(Level)으로 탐색을 진행합니다. BFS : 2 -> 7 -> 5 -> 2 -> 6 -> 9 -> 5 -> 11 -> 4 DFS : 2 -> 7 -> 2 -> 6 -> 5 -> 11 -> 5 -> 9 -> 4 너비 탐색을 수행은 위에 작성된 것 처럼 상위 Level에 위치한 노드 (Lv 0 : 0 | Lv 1 : 7, 5 | ...)들이 먼저 탐색되는 것을 볼 수 있습..
개인 공부/알고리즘 2023. 2. 15. 08:45

[알고리즘] 재귀

재귀는 알고리즘이 아님! -> 재귀는 for문과 같은 단순한 프로그래밍 작성 방법 재귀는 크게, 선형 재귀와 비선형 재귀로 나뉨 선형 재귀는 한 번 호출에 자신을 한 번 부름 -> Linear한 결과를 도출할 수 있음 비선형 재귀는 한 번의 호출에 자신을 여러 번 부름 재귀 기본 recursive() { // basis part if () { return }; // 재귀(가지)의 끝을 알림, 종료 조건 // inductive part recursive(); // 재귀 호출 } -> 함수 내에서 자기 자신을 한 번 호출하므로 선형 재귀라고 할 수 있음 비선형 재귀 횟수 구하기 - 출력 횟수 : 갈래(한 번 호출마다 자신을 부르는 횟수) ^ 반복 횟수 - 예제 코드 public class Recursive ..
개인 공부/알고리즘 2023. 2. 13. 10:16

[알고리즘] 순열, 조합, 부분 집합

개념 정리 순열 (P : Permutation) 순서가 있음 : 금고의 각 자리 비밀번호는 순서가 있다! keyword : 서로 다른, 나열하다 A와 B, B와 A는 서로 다른 것이다. (비밀번호 486과 468은 서로 다른 비밀번호이다.) 수학 공식 : $_nP_r = \frac{n!}{(n-r)!}$ $_4P_2 = \frac{4!}{(4-2)!} = \frac{4 * 3 * 2 * 1}{2* 1}=12$ 조합 (C : Combination) 순서가 없음 : 콤비네이션 피자는 여러 재료의 조합으로 된 피자이다! (재료의 순서가 없음) keyword : 동시에 꺼내다, 선택하다 A와 B, B와 A는 같은 것으로 취급함 수학 공식 : $_nC_r = \frac{_nP_r}{r!}=\frac{n!}{(n-..
개인 공부/알고리즘 2023. 2. 12. 12:28

[알고리즘] 구간 합 (부분 합)

구간 합 시간 복잡도를 더 줄이기 위해 사용하는 특수 알고리즘 S[i] = A[1] + .. + A[i] 합 배열 만드는 방법 합 배열 S[]를 만들기 위해서, 첫 번째 배열의 값은 0으로 만들고, 이후 값들은 이전 요소까지의 합 ( S[i -1] ) + 현재 요소 ( A[i] )를 더합니다. S[0] = A[0] S[i] = S[i-1] + A[i] i에서 j까지 구간 합 구하는 공식 3 ~ 4까지의 합은 3+4입니다. 이때, S[4]는 1+2+3+4이기 때문에 S[2] (1+2)을 뺀다면 동일한 결과를 얻을 수 있을 것입니다. 즉 i부터 j번째까지 합 구하는 방법은 S[j] - S[i -1] 이라고 볼 수 있습니다. 이렇게 구간 합을 사용한다면 시간 복잡도를 효율적으로 변경할 수 있습니다. 코드 //..
개인 공부/알고리즘 2023. 2. 10. 11:03

[알고리즘] 최대공약수(GCD), 최소공배수 구하기 (유클리드 호제법)

유클리드 호제법 유클리드 호제법 두 개의 수가 주어졌을 때 최대 공약수를 구하는 알고리즘 이를 이용하여 최소 공배수도 구할 수 있음 약수? 어떠한 수를 나누어 떨어지게 하는 수 최대공약수(GCD)? 두 자연수의 공통된 약수 중 가장 큰 수 최소공배수? 두 자연수가 공통으로 표현할 수 있는 가장 작은 배수 최대공약수를 구하는 방법 1. 소인수 분해를 통한 소인수를 곱하기 -> 값이 크면 오래 걸림 2. 유클리드 호제법 숫자 N, M이 존재(N > M)할 때, L = N % M 이 때, N와 M의 최대 공약수는 M와 L의 최대 공약수와 같음 -> 이를 반복하여 L == 0이 될 때의 M 최소공배수 구하는 방법 숫자 M * 숫자 N / 최대공약수 N * M / G N개의 숫자에 대한 최대공약수, 최소공배수 구..
개인 공부/알고리즘 2023. 2. 1. 11:11

[알고리즘] 소수 (Prime)

소수 구하기 - 숫자 N의 소수 판정 방법 1 ~ $\sqrt{N}$까지 N을 나누어 떨어지게 하는 수가 있는지를 확인 - 에라토스테네스의 체 사용하기 각 수는 임의의 값 n * n 제곱하여 나오는 n보다 큰 값을 ( i * i 5의 경우 5*2 / 5*3 / 5*4 / 5*5 / ... 로 진행되며, -> 이때 2, 3, 4(2,2)는 앞선 값으로 인해서 소수가 아니라고 처리되기 때문에 10,000까지의 소수의 개수 : 1,229개 소수 구하는 코드 (Java) private static boolean isPrime(int num) { if..
개인 공부/알고리즘 2023. 1. 27. 11:25

[알고리즘] 2차원 배열의 회전

다음과 같은 N*N 크기의 2차원 배열을 시계방향(오른쪽)으로 90도 회전한다면 아래 그림과 같습니다. 혹시 위 사진에서 규칙성을 찾으셨나요? 해당 배열을 인덱스로 본다면 좀 더 쉽게 규칙성을 찾을 수 있습니다. 행의 규칙성 원본 배열과 회전 후 배열을 인덱스로 표현한다면 위와 같습니다. 잘 살펴보면 각각 기존의 열번호가 행번호로 적용되는 모습을 볼 수 있습니다. 행렬을 한 번 더 회전시킨다면 규칙성이 적용된다는 것을 더 쉽게 이해할 수 있는데요. 모든 요소들의 공통적인 열번호였던 4가 각각 행번호로 적용된 것을 확인할 수 있습니다. -> 회전된 행의 인덱스 == 기존의 열 인덱스 열의 규칙성 열은 행보다는 조금(?) 어렵습니다. 회전한 행이 기존의 열을 사용하였듯이, 회전한 열도 기존의 행을 사용합니다..
개인 공부/알고리즘 2023. 1. 10. 16:19

[코딩테스트] 최단 경로 알고리즘

최단 경로 알고리즘 가장 짧은 경로를 찾는 알고리즘 한 지점에서 다른 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 노드 각 지점의 연결은 간선으로 표현 다익스트라 최단 경로 알고리즘 한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 계산 음의 계산이 없을 때 동작 매 상황에서 가장 비용이 적은 노드를 선택하고 처리하는 과정 반복 -> 그리디 알고리즘으로 분류됨 -> 다익스트라 알고리즘은 한 단계마다 하나의 노드에 대한 최단 거리를 확실히 찾음 - 로직 출발 노드 설정 최단 거리 테이블 초기화 (시작점 0) 방문하지 않은 노드 중 가장 짧은 노드 선택 선택된 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 ..
개인 공부/알고리즘 2022. 11. 23. 12:55

[코딩테스트] 다이나믹 프로그래밍

다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 향상 시키는 방법 계산된 결과를 메모리 영역에 저장하여 다시 계산하지 않도록 함 최적 부분 구조와 중복 부분 문제가 만족할 때 사용 가능함 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결 할 수 있는 경우 중복 부분 문제 : 동일한 작은 문제를 반복적으로 해결해야 하는 경우 점화식 : 인접한 항들 사이의 관계식 메모이제이션 한 번 계산한 결과를 메모리 공간에 메모하는 기법 같은 문제를 다시 호출하면 메모한 결과를 가져옴 캐시이라고도 함 결과 저장용 리스트를 DP 테이블이라고 부름 탑다운 : 위에서 아래로 내려감, 큰 문제 해결을 위해 작은 문제들을 재귀적으로 호출하여 작은 문제를 먼저 해결..
개인 공부/알고리즘 2022. 11. 22. 14:07

[코딩테스트] 이진 탐색 알고리즘

이진 탐색 순차 탐색 : 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인 이진 탐색 : 탐색 범위를 절반씩 좁혀가며 탐색 정렬되어 있는 리스트에서만 탐색 가능함 시작점, 끝점, 중간점 등을 이용해 탐색해야 함 -> 시작점과 끝점이 같아질 때까지 반복함! 중간점을 기준으로 하여 찾고자 하는 값이 어디에 있는지 확인 중간점과 찾고자 하는 값이 동일하면 종료 - 이진 탐색 재귀로 구현 def binary_search(array, target, start, end): if start > end: # 탐색할 데이터가 없다면 return None mid = (start + end) // 2 # 중간점 명시 if array[mid] == target: # 중간점 == 찾고자 하는 값이면 return mid ..
개인 공부/알고리즘 2022. 11. 21. 11:55

[코딩테스트] 정렬 알고리즘

정렬 알고리즘 데이터를 특정한 기준에 따라 순서대로 나열 데이터 개수 적을 때 데이터 범위가 한정되어 있을 때 데이터가 일부 정렬되어 있을 때 선택 정렬 이중 for문을 통하여 구현 시간 복잡도 : O(N^2) - 로직 처리 되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞 데이터와 바꿈 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] 삽입 정렬 처리되지 않은 데..
개인 공부/알고리즘 2022. 11. 20. 18:03

[코딩테스트] DFS/BFS 알고리즘

DFS/BFS 탐색 알고리즘 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정 stack : LIFO (후입선출) -> python에서는 리스트와 append(), pop()을 통해 쉽게 stack의 삽입/삭제 연산을 구현 가능 queue : FIFO (선입선출) -> python에서 큐 규현을 위한 라이브러리 사용 from collections import deque queue = deque() # 큐 구현 queue.append(5) # 오른쪽에 값 추가 queue.append(4) queue.append(3) queue.popleft() # 왼쪽에 값 제거 -> 5 제거 queue.reverse() # 역순으로 바꾸기 재귀함수 : 자기 자신을 다시 호출하는 함수 DFS 구현 시 자주 사용되는..
개인 공부/알고리즘 2022. 11. 19. 12:46

[코딩테스트] 구현 알고리즘

구현 알고리즘 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 풀이를 떠올리기 쉽지만 소스코드로 옮기기 어려운 문제 코드가 길어지는 문제, 특정 소수점까지 출력하는 문제, 파싱 문제 등 완전 탐색, 시뮬레이션 등을 포함 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 하나씩 차례대로 직접 수행 예제) 상하좌우 NxN 크기의 정사각형 공간에서 (1,1)에서 시작하여 L, R, U, D를 통해 이동할 때 최종 목적지의 좌표 구하기 정사각형 공간을 벗어나면 무시 -> 명령에 따라서 개체를 이동시키기 때문에 시뮬레이션 문제로 분류 방향을 설정하여 이동하는 문제 -> x의 이동 방향, y의 이동 방향, 이동 타입 등을 명시하는 리스트를 각각 생성 이동방향을 명..
개인 공부/알고리즘 2022. 11. 18. 10:44

[코딩테스트] 그리디 알고리즘

그리디 알고리즘 현재 상황에서 당장 좋은 것만 고르는 방법 -> 현재의 선택이 나중에 미칠 영향은 고려하지 않음 -> 문제에서 요구하는 최적의 해를 구할 수 있는지 검토하는 과정이 필요함 그리디 알고리즘의 유형은 매우 다양하기 때문에 암기가 어려움 여러 유형을 파악하고 훈련하는 것이 중요함 그리디 알고리즘은 기준에 따라서 좋은 것을 선택하는 알고리즘 (크기에 따른 순서 등) 예제) 거스름돈 문제 거슬러 줘야 할 최소한의 동전 개수 구하기 -> 가장 큰 화폐 단위부터 돈을 거슬러 줘야 함 정당성 검토 : 거스름돈 문제를 그리디로 해결할 수 있는 이유는 동전의 큰 단위가 작은 단위의 배수이기 때문임 -> 다른 단위의 동전을 종합해 다른 해가 나올 수 없음 만약 거스름돈 종류가 500, 400, 100 등이 ..
개인 공부/알고리즘 2022. 11. 17. 11:46

[코딩테스트] 코딩 테스트 개념 & 파이썬 주요 기능 사용법

알고리즘 해결 과정 1. 지문 읽기 및 컴퓨터적 사고 2. 요구사항 분석 3. 문제 해결을 위한 아이디어 찾기 4. 소스코드 설계 및 코딩 시간 제한에 따른 알고리즘 설계 - 파이썬 기본 라이브러리 시간 복잡도 https://wiki.python.org/moin/TimeComplexity TimeComplexity - Python Wiki This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have sli..
개인 공부/알고리즘 2022. 11. 16. 16:35
◀ 1 ▶

티스토리툴바