| 자료구조 & 알고리즘
-
💡파이썬 Disjoint-Set(Union-Find) 이론 및 예제| 자료구조 & 알고리즘/알고리즘 2023. 11. 29. 01:49
알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조와 알고리즘을 만나게 됩니다. 그 중에서도 Disjoint-Set(서로소 집합)을 활용한 Union-Find는 중상난이도 문제에서 자주 출제되는 유형 중 하나입니다. 이번 글에서는 Disjoint-Set, Union-Find의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다. Disjoint-Set(Union-Find)이란? 단순히 disjoint-set은 서로 다른 두 집합(서로소 집합)을 뜻함 서로 다른 집합을 모아 하나의 집합으로 만드는 Union-find 알고리즘에 사용됨 사용되는 case 그래프에서 서로 다른 정점을 연결하는 최소 신장 트리를 구하는 문제 서로 다른 집합을 합치는 문제 등 수행 연산 Union: 두 개의 집합을 하나로 합치..
-
💡파이썬 큐(Queue) 이론 및 예제| 자료구조 & 알고리즘/자료구조 2023. 11. 10. 15:32
알고리즘 코딩 테스트를 준비하다 보면 다양한 자료구조를 만나게 됩니다. 그 중에서도 큐(Queue)는 스택과 함께 가장 기본적인 자료구조 중 하나입니다. 이번 글에서는 큐의 개념과 파이썬으로 구현하는 방법에 대해 알아보겠습니다. 큐(Queue)란? 알고리즘 코딩테스트에서 가장 자주 활용되는, 데이터를 저장하는 자료구조 중 하나 (BFS문제에서 자주 활용) 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식 입력과 출력이 각각 다른 방향에서 한쪽으로만 일어남 큐의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 enQueue, deQueue 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경 안써도 됩니다. 파이썬 메모..
-
💡파이썬 스택(Stack) 이론 및 예제| 자료구조 & 알고리즘/자료구조 2023. 11. 9. 00:36
스택(Stack)이란? 스택은 흔히 두 가지 의미로 사용됩니다. 자료구조로써의 스택, 프로세스 메모리 구조로써의 스택 메모리입니다. 본 포스트에서는 자료구조로써의 스택에 대한 내용을 다루고 있으니, 스택 메모리에 대해 궁금하신 분은 저의 이전 포스팅을 참고해주세요. (무려 2년 3개월 전 포스팅... 시간 참 빨라요) 알고리즘 코딩테스트에서 가장 자주 활용되는 자료구조 중 하나 (DFS문제에서 자주 활용) 가장 나중에 들어온 데이터를 가장 먼저 처리하는 후입선출(LIFO, Last In First Out) 방식 입출력이 한쪽에서만 일어남 스택의 크기가 제한되어 있음 - 데이터의 크기만큼 크기가 결정됨. 따라서 C에서는 push, pop 할때마다 메모리 재할당(realloc)이 필요하지만 파이썬에서는 신경..
-
💡파이썬 기본 입/출력| 자료구조 & 알고리즘/알고리즘 2023. 10. 21. 12:16
입력 # 방법1 import sys a = int(sys.stdin.readline()) # 한 개의 정수를 입력받을 때. 개행 같이 입력되나 int 형변환 시 처리되어 사라짐 a, b, c = map(int, sys.stdin.readline().split()) # 여러 개의 정수를 입력받을 때 # 방법2 a = int(input()) # 한 개의 정수를 입력받을 때 => 느리므로 지양할 것. 마지막 개행은 안 받아짐. 출력 # 방법1 import sys sys.stdout.write("asd\n") # 개행 직접 처리해주어야 함 # 방법2 print("asd") # 느려서 지양, 자동개행. 마지막 개행 안하려면 print("asd", end='')
-
💡코딩테스트 준비를 위한 효과적인 알고리즘 공부 방법| 자료구조 & 알고리즘/알고리즘 2023. 10. 21. 10:44
코딩 테스트는 개발자 진로를 희망하는 학생, 취준생, 직장인들이 부딪히는 난관입니다. 저 또한 비전공자로 취준을 시작해서, 수많은 코딩테스트를 치러 왔고, 마침내 최종합격하여 개발자로서 일하고 있습니다. 제 경험을 바탕으로 "코딩테스트 준비를 위한 효과적인 알고리즘 공부 방법"을 정리해볼까 합니다. 언어 선택 프로그래밍 언어는 아주 다양합니다. C, C++, Java, Python, JavaScript, Kotlin, Go, C#, Rust, Dart, Swift, Objective-C, 엄랭(ㅋㅋ), 등등...코딩테스트를 학습하려면 먼저 어떤 언어로 코딩할건지 정해야겠죠. 저는 취준할 때 조금 미련하게 했습니다. C, Python, Kotlin, Go, Java 다섯 가지 언어로 코딩테스트를 대비했습니..
-
💡 [CS지식] Garbage Collection에 대하여| 자료구조 & 알고리즘/Computer Science 2021. 10. 26. 09:44
Garbage Collection Java에선 개발자가 프로그램 코드로 메모리를 명시적으로 해제하지 않아요 JVM(Java Virtual Machine)이 구성된 JRE(Java Runtime Environment)가 제공되며, 그 구성 요소 중 하나인 Garbage Collection(이하 GC)이 자동으로 사용하지 않는 객체를 메모리에서 삭제하는 작업을 수행해요 기본적으로 JVM의 메모리는 총 5가지 영역(class, stack, heap, native method, PC)으로 나뉘는데, GC는 힙 메모리만 다뤄요 Generational Garbage Collection Java application에서는 가비지 컬렉션을 통해 더이상 사용되지 않는 오브젝트들을 제거해요. 가비지 컬렉션에서 '더이상 사..
-
💡 [자료구조] Tree에 관하여| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:37
Tree 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조 계층적 관계 (Hierarchical Relationship)을 표현하는 자료구조 Tree 관련 용어 Node (노드) : 트리를 구성하고 있는 각각의 요소 Edge (간선) : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Root Node (루트 노드) : 트리 구조에서 최상위에 있는 노드 Leaf Node (Terminal Node, 단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드 Internal Node (내부 노드, 비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드도 포함 Sibling Node (Brother Node, 형제 노드) : 동일한 부모를 가지는 노드 Path (경로) : 한 노드에서 다른 한 노..
-
💡 [자료구조] Stack and Queue| 자료구조 & 알고리즘/자료구조 2021. 10. 26. 09:28
Stack 후입선출(LIFO) 자료구조 함수가 호출되면 스택 영역 메모리에 함수가 올라가요 삽입과 삭제가 한 방향에서만 일어나요 DFS에서 많이 쓰여요 (재귀적 호출) Queue 선입선출(FIFO) 자료구조 작업을 순서대로 실행시키기 위해 대기열을 구현할때 많이 사용돼요 삽입과 삭제가 양 방향 각각에서 일어나요 BFS에서 많이 쓰여요 (재귀적 호출) 다양한 형태의 Queue가 존재하는데, 특히 Deque의 경우는 삽입과 삭제가 양 방향에서 모두 일어날 수 있어요