MONG 기술블로그

이진 탐색 ( Binary Search )이란 정렬된 배열에서 타겟을 빠르게 찾는 검색 알고리즘이다. 제약 조건 : 정렬된 상태의 배열에서 사용가능 장점 : 시간복잡도가 O(logN) 으로 매우 빠른 성능 보유 시간복잡도를 수치로 변경하여 설명해보면 다음과 같다. 크기 1억개인 배열에서 특정 값을 찾는 경우. ( 정렬된 경우 ) 순차 탐색 : 최악의 경우 1억번 탐색 필요 이진 탐색 : log100000000 번 탐색 필요. 대략 26번만의 탐색으로 특정 값을 찾을 수 있음 이를 Python 코드로 직접 구현하여 탐색 횟수를 비교해보자. import random # 1 - 천만 nums = [i for i in range(1, 10000001)] # 유니크한 백만개의 수를 1-천만 범위에서 리스트로 추출..

그래프 관련 주요 용어와 그래프의 대표 순회 알고리즘인 DFS. BFS에 대해서 간단히 정리해보자. 그래프 순회 알고리즘 DFS 깊이 우선 탐색 ( Depth First Search ) 스택 혹은 재귀로 구현하며 대부분의 그래프 순회 문제에서 사용한다. BFS 너비 우선 탐색 ( Breadth First Search ) 큐를 이용하여 구현하며, 특정 Vertex로부터의 최단 거리를 구하는 문제에서 사용한다. 그래프 표현 방법 인접 행렬 혹은 인접 리스트를 이용하여 표현하며 하기 코드는 인접 리스트를 Python 딕셔너리를 통해 표현한 예시이다. graph = { 1: [2,3,4], 2: [5], 3: [4,5,6] } 그래프 순회 알고리즘 구현 각 구현에서 방문 확인 & 추가를 하는 위치가 알고리즘상 ..

인프라 엔지니어로써 실무적으로 프로그래밍을 사용하는 빈도가 매우 적지만 IT 업무에 종사하는 사람으로써 언제든지 꺼내들 수 있는 프로그래밍 언어 하나쯤은 가지고 있어야 한다고 생각한다. 또한 단순히 프로그래밍 언어를 작성한다기보다 내가 원하는 로직을 구현할 줄 알아야 한다고 생각하기에 알고리즘 공부도 꾸준히 해야한다 우선 정복할 대상은 프로그래머스 고득점 Kit 이다. 간단하게 구현한 내용을 정리하여 나중에 필요한 로직이 있을 때 꺼내 쓸 수 있도록 블로깅해놓자. 사용언어 : Python3 첫 도전과제 : 프로그래머스 코딩테스트 고득점 Kit 코딩테스트 고득점 Kit 문제 풀이 현황 - 해시 ( 4/4 ) - 스택/큐 ( 4/4 ) - 힙(Heap) ( 3/3 ) - 정렬 ( 3/3 ) - 완전탐색 ( ..