포시코딩

유추한 방법 e1 = [1, 4], e2 = [3, 8] 두 좌표를 지나가는 일차함수에 대해 기울기를 구하는 과정을 직접 적어봤다. 4 = 1a + b# e2[1] = e1[0] * a + b 8 = 3a + b# e2[1] = e2[0] * a + b b = 4 - 1a# b = e1[1] - (e1[0] * a) b = 8 - 3a# b = e2[1] - (e2[0] * a) 4 - 1a = 8 - 3a# e1[1] - (e1[0] * a) = e2[1] - (e2[0] * a) (3 - 1)a = 8 - 4# (e2[0] - e1[0]) * a = e2[1] - e1[1] a = 4/2 = 2# a = (e2[1] - e1[1]) / (e2[0] - e1[0]) e1, e2 말고 더 알아보기 쉽게 ..

유클리느 호제법이란? https://velog.io/@yerin4847/W1-유클리드-호제법 유클리드 호제법(Euclidean-algorithm) 유클리드 호제법에 대해 알아보자. velog.io 개념은 정리가 너무 잘 되어있어 링크째로 남긴다. 최대공약수(GCD, Greatest Common Divisor) 코드 위 포스팅 예제는 C언어로 작성되었기 때문에 파이썬으로 나타내봤다. 반복문 # 반복분 def gcd(a, b): while b: temp = a % b a = b b = temp return a 재귀함수 # 재귀함수 def gcd(a, b): return (gcd(b, a % b) if b else a) 최소공배수(LCM, Least Common Multiple) 두 수 a, b에 대해 위 방..

예제를 통해 이중 for문의 시간복잡도를 구해보자 algorithm sum(A, n): sum = 0# 1번 for i=0 to n-1 do# n번 for j=i to n-1 do# 아래에서 설명 sum += A[i] * A[j]# 3번 return sum 각 for문의 돌아간 횟수 i j 0 n 1 n-1 2 n-2 ... ... n-1 n-(n-1)=1 식으로 나타내기 for j=i to n-1 do # 여기서 i가 n-1이라면 j=도 n-1이 되고 to n-1 즉, n-1이 n-1이 될 때 까지니까 한 번 돌게 된다. # 규칙을 부여해서 찾는다면 n-(i의 시작 수)가 되니 n-(n-1)이 되어 n-n+1 즉, 1이 되는 방법도 있다. 결국 이중 for문의 횟수는 위 표의 j 밑에 있는 값들을 모두..

동적 계획법이란? 동적 계획법은 여러 개의 하위 문제를 풀고 그 결과를 기록하고 이용해서 문제를 해결하는 알고리즘이다. 왜 써야할까? 동적 계획법을 왜 써야하는지에 대해 말하기전에 먼저 피보나치 수 구하는 법에 대해 알아보자. 피보나치 수열 * 피보나치 수: 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열. ex) 1, 1, 2, 3, 5, 8, ... n번째 피보나치 수를 Fibo(n)으로 표현한다면 일단 Fibo(1)과 Fibo(2)는 1이다. Fibo(3)부터는 이전 값과 이전 이전 값의 합이 된다. Fibo(3) = Fibo(1) + Fibo(2) = 1 + 1 + 2 그러면 Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fib..

BFS란? 한 노드를 시작으로 인접한 모든 노드들을 우선 방문하는 방법. 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 BFS를 적용한다. BFS 구현 방법 1. 큐 BFS는 현재 인접한 노드들을 먼저 방문해야 한다. 이걸 다시 말하면 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고 가장 처음에 넣은 노드를 꺼내서 탐색하면 된다. -> 처음에 넣은 노드를 꺼낸다. -> 큐를 쓰면 되겠구나 큐를 사용한다는 점 말고는 DFS에서 스택을 사용하는 방법과 매우 유사하다. 코드로 직접 살펴보자 graph = { 1: [2, 3, 4], 2: [1, 5], 3: [1, 6, 7], 4: [1, 8], 5: [2, 9], 6: [3, 10], 7: [3], 8: [4], 9:..

DFS란? 자료의 검색, 트리나 그래프를 탐색하는 방법으로 사용되며 한 노드를 시작으로 인접한 다른 노드를 통해 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS의 특징 DFS는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구한다. 따라서 공간을 적게쓰지만 최단 경로를 탐색하기가 쉽지 않다. DFS 구현 방법 1. 재귀함수 DFS는 갈 수 있는 만큼 계속해서 탐색하다가 갈 수 없게 되면 다른 방향으로 다시 탐색하는 구조이다. 노드를 방문하고 깊이 우선으로 인접한 노드를 방문 또 그 노드를 방문해서 깊이 우선으로 인접한 노드 방문 만약 끝에 도달했다면 리턴 -> 반복.. 반복하다가 갈 수 없게 되면 탈출 -> 재귀 함수를 쓰면 되겠구나 코드로 직접 살펴보자 graph = {..

그래프란? 연결되어있는 원소간의 관계를 표현한 자료구조 비선형 구조는 표현에 초점이 맞춰져있고 선형 구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있는 반면, 그래프 자료구조는 연결 관계에 초점이 맞춰져 있다. 그래프 용어 노드(Node): 연결 관계를 가진 각 데이터를 의미. 정점(Vertax)이라고도 한다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) 그래프의 종류 유방향 그래프(Directed Graph): 방향이 있는 간선을 갖는다. 간선은 단방향 관계를 나타내며, 각 간선은 한 방향으로만 진행할 수 있다. 무방향 그래프(Undirected Graph): 방향이 없는 간선을 갖는다. 무방향 그래프의 표현방법 1...

소개 트리: 계층 구조의 데이터를 쉽게 표현 가능 힙: 최솟값과 최댓값을 쉽게 뽑을 수 있다. ex) Min Heap, Max Heap 트리(Tree) 스택(Stack), 큐(Queue)는 선형 구조인 반면, (선형 구조란 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미) 트리는 비선형 구조. 선형 구조와는 다르게 데이터가 계층적 혹은 망으로 구성되어 있다. 형태뿐만 아니라 용도에서도 차이점이 있는데, 선형 구조는 자료를 저장하고 꺼낼 때 좋고 비선형 구조는 표현에 초점이 맞춰져 있다. 트리를 다루는 용어 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 ..

해시란? 해시, 해시 테이블, 해쉬 등으로 불리는 이 자료구조는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료구조이다. 해시 테이블의 특징 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 '키'와 '데이터'를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트하고 싶을 때 사용한다. 한줄로 요약하자면 데이터의 검색과 저장이 아주 빠르게 진행된다. ex) 파이썬의 딕셔너리 * 여기서 이 파이썬의 딕셔너리가 내부적으로는 배열을 사용하는데 어떤식으로 사용되는지 알아보자 'fast'와 'slow'의 값인 '빠른'과 '느린'이 배열 어딘가에 있다고 치자. 그 인덱스를 몇번에 넣어야 하는지, 몇번에서..

큐(Queue)란? FIFO(First In First Out)의 성격을 가진 자료구조. 처음으로 들어간 데이터가 처음으로 빠져 나오는 어찌보면 당연하고 합리적인 자료구조이다. 실생활에서도 많이 접할 수 있는 자료구조 중 하나이다. 사용예시 서버 접속 대기열 큐 롤에서 야 큐 돌려~ 하는것도 이 큐가 맞음 인쇄 대기열 큐 인쇄 하나가 오류로 안되면 그 뒤에 나와야할 인쇄물도 모조리 안나오는 경험이 있을 것이다. 이 때도 큐를 쓴다. 큐의 대표 기능 Peek(픽) 큐의 Top(맨 앞) 데이터를 보는 것 Enqueue(삽입) 큐에 원소를 삽입하는 행위. 원소는 Rear(맨 뒤)에 들어간다. Dequeue(뽑기) 큐에서 원소를 뽑아오는 행위. FIFO 자료구조라 Front에 위치한 원소를 뽑아온다. Peek,..