benjykim

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 투 포인터 투 포인터 알고리즘: 리스트에 순차적으로 접근해야 할 때 2개의 점의 위치를 기록하면서 처리하는 알고리즘 예를 들어, 한 반에 학생이 40명 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목해야 할 때, 우리는 번호로 한명씩 부르기보다는 '2번부터 7번까지의 학생'이라고 부를 수도 있다. 이처럼 리스트에 담긴 데이터에 순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 특정한 합을 가지는 부분 연속 수열 찾기 이러한 투 포인터 알고리즘을 이용하여 '특정한 합을 가지는 ..

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 에라토스테네스의 체 에라토스테네스의 체: 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표 알고리즘. N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 알고리즘은 다음과 같다. 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않는다) 더 이상 반복할 수 없을 때까지 2번과 3번을 반복한다. 소스코드 예제 - N = 1000 으로 설정 # 시간복잡도: O(NloglogN) import math n = 1000 arr = [True for i in range(n+1)] # 처음엔 모든 수가 소수(True)인 ..

[알고리즘] 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 소수의 판별 소수: 2보다 큰 자연수 중에서 1과 자기 자신을 제외한 자연수로는 나우어떨어지지 않는 자연수 6은 1, 2, 3, 6으로 나누어 떨어지기 때문에 소수가 아니다. 7은 1과 7을 제외하고는 나누어떨어지지 않기 때문에 소수이다. 소수는 2보다 큰 자연수에 대하여 정의되므로, 1은 소수에 해당하지 않는다. 어떠한 수 X가 주어졌을 때 해당 수가 소수인지 아닌지 판별하는 방법 가장 간단한 방법은 X를 2부터 X-1 까지의 모든 수로 나누어보는 것. 만일 2부터 X-1 까지의 모든 자연수로 나누었을 때 나누어떨어지는 수가 하나라도 잇다면 X는 소수가 아니다. 소수 판별 소스코드 예제 - 시간복잡도: O(X) def is_prime_n..

[알고리즘] 백준 - 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이..

[알고리즘] 백준 - 단지번호붙이기 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다. 출력 첫 번째 줄에는 ..

[알고리즘] BFS(너비 우선 탐색) 정리 아래와 같이 그래프가 있을 때 BFS 구현 방법에 대해 작성한다. 그래프 graph = [ [], [2,3,8], # [1]번 노드와 연결된 노드: 2, 3, 8번 노드 [1,7], # [2]번 노드와 연결된 노드: 1, 7번 노드 [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] BFS for graph 큐를 사용하는 BFS - deque사용 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: # 큐에서 원소 하나를 뽑아서 출력 v = queue...

[알고리즘] 위상정렬 위상정렬: 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용 가능한 알고리즘 다시 말하면, 방향 그래프의 모든 노드를 *방향성에 거스르지 않도록 순서대로 나열하는 것 위상 정렬 동작 과정 진입차수가 0인 노드를 큐에 넣는다. 큐가 빌 때까지 다음의 과정을 반복한다. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거 새롭게 진입차수가 0이 된 노드를 큐에 삽입 주의할 점 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다고 판단 다시 말해, 원소가 V(노드의 개수)번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것임 위상 정렬의 답안은 여러 가지가 될 수 있다. 위상 정렬 소스코드 입력 예시 # 노드 및 간선 개수 7 8 # a 노드에서 b로 이동..

[알고리즘] 크루스칼(Kruskal) 알고리즘 신장 트리: 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 최소 신장 트리 알고리즘: 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘 대표적인 최소 신장 트리 알고리즘: 크루스칼 알고리즘 알고리즘 동작 과정 간선 데이터를 비용에 따라 오름차순으로 정렬 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음 모든 간선에 대해 2번의 과정을 반복 크루스칼 알고리즘 소스코드 입력 예시 # 노드 7개, 간선 9개 7 9 # 1번 노드에서 2번 노드로 가는 비용: 29 1 2 29 1 5 ..

[알고리즘] 유니온 파인드(Union-find) 알고리즘 유니온 파인드 알고리즘: 서로소 집합, 상호배타적 집합(Disjoint-Set)알고리즘이라고도 불린다. 여러 노드가 있을 때, 선택한 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘이다. 입력 예시 6 4 1 4 2 3 2 4 5 6 경로 압축 기법을 사용하지 않은 풀이 # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): if parent[x] != x: return find_parent(parent, parent[x]) return x # 두 원소가 속한 집합 합치기 def union_parent(parent, a, b): a = find_parent(parent, a) b = find_parent(pare..

[알고리즘] 플로이드 워셜(Floyd-Warshall) 알고리즘 플로이드 워셜 알고리즘: 모든 지점에서 다른 모든 지점까지의 최단 경로를 구해야 하는 경우 사용할 수 있는 알고리즘 입력 예시 # 노드 개수(n) 4 # 간선 개수(m) 7 # a, b, c: a 노드에서 b 노드로 가는 비용 c 1 2 4 1 4 6 2 1 3 2 3 7 3 1 5 3 4 4 4 3 2 소스코드 INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF] * (n+1) for _ in range(n+1)] # 자기 자신에서 자기 자신으로 가는 비용 0으로 초기화 for a in range(1, n+1): for b in range(1, n+1): if a == b: gr..