imhamburger 님의 블로그

래프는 정점(Vertex)과 엣지(Edge)로 이루어진 자료구조로, 관계를 표현하는 데 사용된다.그래프의 정의: V: 정점(Vertex)들의 집합E: 정점을 연결하는 엣지(Edge)들의 집합  아래와 같은 그래프 형태 경로(Path)그래프에서 한 정점에서 다른 정점으로 이동하는 과정을 경로라고 한다.유효한 경로: 한 번 지난 엣지를 다시 사용하지 않고 연결되는 정점의 나열예제:✅ 올바른 경로: 3 -> 2 -> 1 -> 5❌ 잘못된 경로: 3 -> 2 -> 1 -> 2 -> 5 (같은 엣지를 중복 사용) 사이클(Cycle)시작 정점과 끝 정점이 같은 경로를 사이클(Cycle) 이라고 한다.예제: 3 -> 2 -> 5 -> 4 -> 3 그래프의 종류1️⃣ 무방향 그래프 (Undirected Graph)엣지..

이진트리는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 그래서 이진 탐색 트리는 뭐야?이진 탐색 트리는 이진 트리에서 어떠한 규칙에 따라 나열된 트리이다.규칙1: 모든 왼쪽 노드는 부모노드보다 값이 작거나 같다.규칙2: 모든 오른쪽 노드는 부모노드보다 값이 크다.그럼 파이썬으로 구현해보자.#이진 탐색 트리의 노드를 나타내는 클래스class Node: def __init__(self, key): self.key = key self.left = None self.right = Nonekey: 노드의 값left: 왼쪽 자식 노드right: 오른쪽 자식 노드 Insert 함수class BinarySearchTree: def __init__(self): self.r..

자료구조를 영어로 표현하면 Data Structure이다.자료구조는 데이터(Data)를 어떤 구조(Structure)로 효율적으로 저장할지? 관리하는 방법을 의미한다.데이터 삽입, 수정, 삭제, 조회, 정렬, 병합, 순회와 같은 기본적인 연산을 지원한다. 자료구조에는 선형 자료구조와 비선형 자료 구조가 있다.선형 자료구조: 말그래도 일렬로 나열한 자료 구조이다. 배열(Array), 연결 리스트(Linked List), 스택(Stack), 큐(Queue)비선형 자료구조: 순서에 상관없이 계층 혹은 그래프 구조이다. 트리(Tree), 그래프(Graph)자료구조가 나오면 항상 나오는 단어가 있다. 바로 알고리즘.입력 데이터를 받아 원하는 결과를 출력하는 과정들을 알고리즘이라고 한다.더 생각해보면, 입력을 받고..

문제 (출처: 프로그래머스) 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.  제한사항모든 공항은 알파벳 대문자 3글자로 이루어집니다.주어진 공항 수는 3개 이상 10,000개 이하입니다.tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.주어진 항공권은 모두 사용해야 합니다.만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예ticketsreturn[["ICN..

문제 (출처: 프로그래머스) n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.  제한사항노드의 개수 n은 2 이상 20,000 이하입니다.간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예n..

선택 정렬(Selection Sort)데이터가 무작위로 있을 때, 이 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 두번째에 위치한 데이터와 바꾸는 과정을 반복한다.시간복잡도: O(N^2)array = [8,4,6,2,9,1,3,7,5]for i in range(len(array)): for j in range(i+1, len(array)): if array[i] > array[j]: array[i], array[j] = array[j], array[i] #swapprint(array)   삽입 정렬(Insertion Sort) 데이터 집합을 순회하는 과정에서 정렬이 필요한 요소를 뽑아 다시 적절한 곳에 삽입한다.데이터가 정렬되어 있을 때 효..

스택(Stack) 스택은 후입선출(LIFO, Last In First Out) 방식의 자료구조이다.마지막에 삽입된 데이터가 가정 먼저 삭제되는 구조이다. 스택에서 쓸 수있는 메서드에는 push, pop, peek이 있다.push: 데이터를 스택에 추가pop: 스택에서 가장 최근에 추가된 데이터를 제거하고 반환peek: 스택의 가장 상단에 있는 데이터를 반환하지만 제거하지는 X그림으로 이해해보자!  push 처음에 push(1)을 하였다.다음에 push(2)를 하였다.마지막으로 push(3)을 하였다. 그럼, 왼쪽과 같은 그림으로 표현할 수 있다.      pop pop()을 하였더니 마지막으로 push했던 값 3이 제거되고 반환되었다.       peek peek()을 하였더니 값이 제거되지는 않고 가장..

배열(Array) 배열은 연속적인 메모리에서 같은 종류의 아이템들을 저장할 수 있는 자료구조이다.배열에 1, 2, 3, 4, 5라는 숫자를 입력하고 컴퓨터 1개의 메모리공간이 1개의 사각형이라고 했을 때, 아래 그림처럼 표현할 수 있다.  연속된 메모리 블록에 저장되므로 인덱스를 통해 빠르게 접근이 가능한 장점이 있다.  그.런.데 저 5개의 메모리공간에 '6'이라는 숫자를 append 하려고 한다면?배열은 고정된 크기를 가지며, 나중에 크기를 늘릴 수 없다.만약 크기를 늘려야 한다면, 새로운 배열을 만들어 기존 데이터를 복사해야 한다. 아래 그림처럼 말이다. 이렇게되면 4개의 메모리공간이 남게되고, 메모리공간에 관하여 효율적이지 못한 단점도 있다.  따라서, 배열의 크기를 동적으로 관리하기 위해서는 ..

이번엔 백준 대회 or 인턴 문제를 풀어보자. 문제는 다음과 같다. 문제설명백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.입력첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ ..

탐욕법(Greedy) 문제를 더 풀어보자.백준 동전 0 이 가장 대표적인 문제라길래 풀어보았다. 문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)출력첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 예제입력10 4200151050100500100050001000050000 예제출..