포시코딩

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,..

스택이란? LIFO(Last In First Out)의 성격을 가진 자료구조. 데이터를 쌓고나서 데이터를 빼낼 때 마지막으로 넣은 데이터부터 빼내는 자료구조이다. 참고로 반복문의 무한루프 등으로 메모리의 이 스택 영역이 쌓이고 쌓이다가 터지는 현상을 많이 들어본 스택오버플로우(StackOverflow)라고 한다. 사용예시 웹에서의 뒤로가기 버튼 Undo / Redo React의 Stack Navigator 스택의 대표 기능 Peek 스택의 Top(맨 위) 데이터를 보는 것 Push 스택의 Top에 원소를 삽입하는 행위 Pop 스택의 Top에서 원소를 가져오는 행위. Push로 넣었던 원소가 나오게 된다. Peek, Push, Pop 코드 구현 이전 포스팅에서 배웠던 링크드리스트를 통해 스택을 구현해보자 ..

따로 튜터팀께서 직접 라이브 시연으로 재귀 함수를 응용하는걸 보여주셨다. 정수로 이루어진 배열의 요소들을 더하거나 빼서 특정한 숫자를 만드는 문제에 대한 풀이었는데 듣기는 했으나 이해가 어려워 일단 강의 자료를 기록해둔다.. # Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 '더하거나 빼서' 특정한 숫자를 만들려고 한다. # 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. # -1+1+1+1+1 = 3 # +1-1+1+1+1 = 3 # +1+1-1+1+1 = 3 # +1+1+1-1+1 = 3 # +1+1+1+1-1 = 3 # 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘거 target_number이 매개변수로 주어질 때 숫..

삽입 정렬 선택 정렬이 전체에서 최솟값을 '선택'하는 정렬이었다면 삽입 정렬은 전체에서 하나씩 올바른 위치에 '삽입'하는 방식이다. 버블 정렬과 선택 정렬은 현재 데이터의 상태와 상관없이 항상 비교하고 위치를 바꿨지만, 삽입 정렬은 필요할 때만 위치를 변경하므로 더 효율적인 방식이라고 할 수 있다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 이런식으로 비교할 인덱스가 어떤식으로 전개될지 쭉 써보고 그 중에 i 값은 뭐가 될지 그에 따른 j 값은 뭐가 되고 어떻게 구해야할지 생각해보면 for문을 어떻게 짤지 대충 감이 온다. arr = [4, 6, 2, 9, 1] # 1 2 1 3 2 1 4 3 2 1 def insertion_sort(arr): n = len(arr) for..

선택 정렬 선택 정렬은 처음부터 끝까지 하나씩 확인하며 제일 작은 값을 찾아 맨 앞으로 보낸 후 다시 두번째부터 끝까지 하나씩 확인하며 이번에 제일 작은 값을 두번째로 보내는 과정을 반복하는 정렬이다. 이번에도 마찬가지로 구해야하는 인덱스의 값부터 for문을 만들어 찾아보자 arr = [4, 6, 2, 9, 1] # 0 1 2 3 4 1 2 3 4 2 3 4 3 4 def selection_sort(arr): n = len(arr) for i in range(n-1): for j in range(n-i): print(i+j) selection_sort(arr) 버블 정렬과 다른점은 '최솟값'을 찾아 변경한다는 부분이다. 인덱스를 하나씩 돌며 제일 작은 값을 찾아 인덱스만 따로 min_i 변수에 저장한 뒤..

정렬이란? 데이터를 순서대로 나열하는 방법을 의미. 이진 탐색을 가능하게도 하고, 데이터를 조금 더 효율적으로 탐색할 수 있게도 한다. 버블 정렬 버블 정렬은 첫 번째 자료와 두 번째 자료, 두 번째 자료와 세 번째 자료, ... 이런식으로 (n - 1) 번째 자료와 n 번째 자료를 비교하여 교환하면서 자료를 정렬하는 방식이다. ex) 첫 루프에서 두 개씩 비교해서 끝까지 가면 제일 큰 수가 마지막에 위치하게 된다. 이제 마지막 수는 고려하지 않아도 되므로 제외하고 다시 처음부터 마지막-1 번째까지 두 개씩 비교하고 다시 마지막-1 번째도 제외하고.. 를 반복해서 정렬시키는 방식이다. 코드로 구현해보자 input = [4, 6, 2, 9, 1] 위와 같은 숫자로 이루어진 배열이 있을 때 버블 정렬을 통해..