sjmin

1. BFS(Breadth-First Search) 너비 우선탐색이라고 부르며, 가까운 노드부터 탐색하는 알고리즘이다. 선입선출 방식인 큐 자료구조를 이용하고, 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진행하게 된다. BFS 동작 과정 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. cf) 방문처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문처리를 함으로써 각 노드를 한 번씩만 처리할 수 있다. 위 그래..

1. DFS(Depth-First Search) 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 2. 그래프(Graph) 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다. 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드간 간선으로 연결되어 있다면 '두 노드는 인접하다(Adjacent)'라고 표현한다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 인접 리스트(Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식 인접 행렬(Adjacency Matrix) 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이..

탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 데이터를 표현하고, 관리하고, 처리하기 위한 구조 스택(Stack)과 큐(Queue)를 구성하는 핵심 함수 삽입(Push) : 데이터를 삽입한다. 삭제(Pop) : 데이터를 삭제한다. 실제로는 스택(Stack)과 큐(Queue)를 사용할 때, 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야 한다. 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생한다. 즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생한다. 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행해 데이터가 전혀 없는 상태이다. 1. 스택(..

1. 구현 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 2. 파이썬에서 리스트 크기 대체로 코딩 테스트에서는 128~512MB로 메모리를 제한하는데, 이럴 때는 메모리 제한을 염두해두고 코딩을 해야 한다. 아래는 우리가 흔히 사용하는 int 자료형의 데이터 개수이다. 데이터의 개수(리스트의 길이) 메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40KB 파이썬은 다른 언어에 비해 구현상의 복잡도는 낮지만, 데이터 처리량이 많을 때는 꼭 메모리 제한을 고려하자. 만약, 크기가 1,000 이상인 리스트가 있다면, 메모리 용량 제한..

1. 그리디 어떤 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘(현재 상황에서 지금 당장 좋은 것만 고르는 방법) 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즈이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 대체로 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 정렬 알고리즘과 짝을 이룬다. 거스름돈 문제로 예를 들면, '가장 큰 화폐 단위부터' 돈을 거슬러 주는 것' 처럼 간단한 아이디어를 떠올려 문제를 해결할 수 있다. n = 1260 count = 0 # 큰 단위의 화폐부터 차례대로 확인 coin_types = [500, 100, 50, 10] for coin in coin_types: count ..

1. 순열(Permutation) 서로 다른 n개에서 r개를 선택하여 일렬로 나열하는 것 import itertools data = [1, 2] for x in itertools.permutations(data, 2): print(list(x)) # [1, 2] # [2, 1] 2. 조합(Combination) 서로 다른 n개에서 순서에 상관없이 서로 다른 r개를 선택하는 것 import itertools data = [1, 2, 3] for x in itertools.combinations(data, 2): print(list(x), end=' ') # [1, 2] [1, 3] [2, 3] https://developersj.tistory.com/106 백준 1759번 : 암호 만들기 https://w..

1. 구간 합 연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값 각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합(Prefix Sum)을 미리 구해 놓으면 된다. (접두사 합 : 리스트 맨 앞부터 특정 위치까지의 합을 구해놓은 것을 의미) 예를 들어 5개의 데이터 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기서 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 구간 합 계산 문제는 여러 개의 쿼리(Query)로 구성되는 문제 형태로 출제되는 경우가 많다. M개의 쿼리가 존재한다고 가정해보면, 각 쿼리는 Right, Left로 구성되며, 이는 [Left, Right]의 구간을 ..

1. 투 포인터 리스트에 순차적으로 접근해야 할 때 2개의 점 위치를 기록하면서 처리하는 알고리즘 예를 들어, 한 반에 40명의 학생이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목할 때, 번호로 한명씩 부르기보다는 '2번부터 7번까지의 학생'이라고 부를 수 있다. 이처럼 순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기 문제를 풀어보자. 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 '특정한 합'을 갖는 수열의 개수를 출력하는 문제이다. 특정한 부분합을 M이라고 할때 풀이 순서는..

1. 소수(Prime Number) 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수 ex) 2, 7... # 소수 판별 함수 def is_prime_number(x): for i in range(2, x): # 2부터 (x - 1)까지의 모든 수를 확인하며 if x % i == 0: # x가 해당 수로 나누어 떨어진다면 return False # 소수가 아님 return True # 소수임 print(is_prime_number(4)) print(is_prime_number(7)) # False # True 위 코드의 시간복잡도는 O(X)이며, 비효율적이다. 예를들어, 1,000,000이라는 수가 소수인지 확인해야 할 때는 1,000,000을 2부터 999,999..

cf) 표준 라이브러리 : 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리 라이브러리 종류 내장 함수 print(), input() 과 같은 기본 입출력 기능부터 sorted() 와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리 itertools 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리, 순열과 조합 라이브러리 제공 heapq 힙(Heap) 기능을 제공하는 라이브러리, 우선순위 큐 기능을 구현하기 위해 사용 bisect 이진 탐색(Binary Search) 기능을 제공하는 라이브러리 collections 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리 math 필수적인 수학적 기능을 제공하..