개념

사이클 판별 알고리즘은 앞선 포스팅인 서로소 집합 알고리즘을 이용한 알고리즘입니다. 그림과 같이 노드 1, 2, 3이 있고 각각의 연결이 서로를 가리키게 되어있다고 가정합시다.

이 경우 앞선 서로소 집합 알고리즘의 find_parent를 이용하면 노드1의 부모는 노드 1, 노드 2의 부모는 노드 1, 노드 3의 부모는 노드 1로 모든 노드의 부모가 각각 노드 1 임을 확인할 수 있습니다. 따라서 사이클이 발생을 했다는 것을 알 수 있습니다. 그러므로 사이클 판별 알고리즘의 경우 두 노드를 확인한 후 부모 노드가 다르다면 union_parent 함수를 수행해주고 부모 노드가 같다면 사이클이 존재한다는 것을 출력한 뒤 함수를 종료하면 되는 것입니다. 소스코드는 다음과 같습니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def find_parent(parent, x):
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]
 
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
  
v, e = map(int, input().split())
parent = [0] * (1 + v)
 
for i in range(1, 1 + v):
  parent[i] = i
 
cycle = False
 
for i in range(e):
  a, b = map(int, input().split())
  if find_parent(parent, a) == find_parent(parent, b):
    cycle = True
    break
  else:
    union_parent(parent, a, b)
 
if cycle:
  print("사이클 발생")
else:
  print("사이클 X")
  
 cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

벨만 포드 알고리즘  (0) 2021.03.01
크루스컬 알고리즘 (Python)  (0) 2020.12.31
서로소 집합 알고리즘 (Python)  (0) 2020.12.30
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22
개념

서로소 집합 알고리즘은 말 그대로 어떠한 숫자들의 서로소인지 아닌지의 관계를 나타내는 알고리즘이라고 생각하시면 될 것 같습니다. 먼저 1, 2라는 집합과 3, 4라는 집합이 있다고 가정합시다. 이 두 집합은 교집합이 없기 때문에 서로소 관계라고 할 수 있습니다. 우리가 구현할 서로소 집합 알고리즘의 경우 부모를 확인하는 함수, 합치기 연산을 수행하는 함수로 크게 두 부분으로 나눌 수 있습니다. 단 부모를 확인하는 함수에서 경로 압축 기법을 사용하게 되면 보다 빠른 시간 복잡도로 문제를 해결할 수 있기 때문에 외워주는 것이 좋을 것 같습니다. 

소스코드

본 소스코드는 나동빈님의 이것이 취업을 위한 코딩테스트이다. 를 참조하였습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
def find_parnet(parent, x):
  # 루트 노드가 아니면, 루트 노드를 찾을때까지 재귀적으로 찾기
  if parent[x] != x:
    parent[x] = find_parnet(parent, parent[x])
  return parent[x]
 
# 두 원소가 속한 집합을 합치기
def union_Parent(parent, a, b):
  a = find_parnet(parent, a)
  b = find_parnet(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b
 
v, e = map(int, input().split())
parent = [0] * (v + 1)
 
for i in range(1, v + 1):
  parent[i] = i
 
for i in range(e):
  a, b = map(int, input().split())
  union_Parent(parent, a, b)
 
print("각 원소가 속한 집합: " , end="")
for i in range(1, v + 1):
  print(find_parnet(parent, i), end=" ")
print()
 
print("부모 테이틀: ",end="")
for i in range(1, v + 1):
  print(parent[i], end=" ")
 cs

 

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

크루스컬 알고리즘 (Python)  (0) 2020.12.31
사이클 판별 알고리즘 (Python  (0) 2020.12.31
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
개념

다익스트라 알고리즘은 최단 거리를 구할 때 유용한 알고리즘입니다. 특히 한 지점에서 다른 지점으로 이동할 때 최단거리를 구할 때 유용한 알고리즘입니다. 먼저 그림을 보겠습니다.

나동빈님의 이것이 취업을 위한 코딩테스트이다 다익스트라 알고리즘 그래프를 참조했습니다.

위와 같은 그래프가 있을때 우선 distance 테이블을 생성합니다. 그 후 모든 거리를 INF 즉 무한으로 초기화합니다.

노드번호 1 2 3 4 5 6
거리  INF INF INF INF INF INF

그 후 start 지점을 1로 설정할 경우를 예를 들어서 설명하겠습니다. 1에서 1로 가는 경우 거리는 0이기 때문에 0으로 설정합니다. 그 후 1번 노드에서 갈 수 있는 지점인 2, 3, 4번 노드로 가는 거리가 각각 2, 5, 1 이고 이들은 모두 INF보다 작으므로 INF를 2, 5, 1로 바꿔줍니다. 그러면 다음과 같습니다. 

 

노드번호 1 2 3 4 5 6
거리  0 2 5 1 INF INF

그 후 거리가 가장 작은 노드를 선택합니다. 위의 표에서 거리가 작은 노드는 거리가 1인 노드 4 이므로 4를 시작 지점으로 한 후 4에서 연결된 노드를 찾습니다. 4에서 갈 수 있는 노드는 3, 5가 있고 각각의 거리는 3, 1입니다. 1에서 3까지의 거리는 위의 표에서 5라고 나와있습니다. 그러나 1에서 4를 거쳐서 5를 가는 거리는 (1 + 3)이므로 4입니다. 따라서 4로 바꿔주고 5번으로 가는 거리는 원래 INF에서 (1 + 1) 즉 2가 더 작으므로 2로 교체합니다. 

 

노드번호 1 2 3 4 5 6
거리  0 2 4 1 2 INF

이 과정을 전체 노드를 다 반복을 하게 되면 start인 1번 노드에서 모든 노드로 가는 최소 거리를 알 수 있습니다. 소스코드는 다음과 같습니다. 여기서 갈 수 있는 노드 중에 거리가 가장 작은 노드를 고르는 방법은 heapq를 이용해서 구현합니다. heapq를 이용하면 최악의 경우에도 O(ElogV)로 동작하기 때문에 heapq를 이용합니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)
 
n, m = map(int, input().split())
start = int(input())
graph = [[] for _ in range(1 + n)]
distance = [INF] * (1 + n)
 
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append((b, c))
 
def dijkstra(start):
  q = []
  heapq.heappush(q, (0, start))
  distance[start] = 0
  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      continue
    for i in graph[now]:
      cost = dist + i[1]
      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q, (cost, i[0]))
 
dijkstra(start)
 
for i in range(1, 1 + n):
  if distance[i] == INF:
    print("INF")
  else:
    print(distance[i])
 
 cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

사이클 판별 알고리즘 (Python  (0) 2020.12.31
서로소 집합 알고리즘 (Python)  (0) 2020.12.30
편집거리 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)  (0) 2020.12.19
개념

편집거리 알고리즘이란 두 문자열이 주어졌을 때 문자열을 비교하는 알고리즘입니다. 여기서 비교한다는 것은 삽입, 삭제, 교체 즉 3가지의 액션이 주어졌을 때 두 문자열이 같게 하기 위해 취할 수 있는 액션의 최솟값을 구하는 알고리즘이라는 것입니다. 예를 들어서 str1 = python, str2 = pyytthon 라 가정하고 문제를 해결해보겠습니다. 이 알고리즘은 다이내믹 프로그래밍 즉 dp의 일종이기 때문에 dp 테이블의 형태로 이차원 리스트를 구현하면 쉽게 해결할 수 있습니다. 

다음의 표를 봅시다.

  None p y y t h o n
None 0 1 2 3 4 5 6 7
p 1 0 1          
y 2              
t 3              
h 4              
o 5              
n 6              

먼저 str1을 행으로 str2를 열로 넣고 각 행과 열에 숫자를 넣은 상태입니다. 여기서 만약 p, p를 비교하는 경우 즉 2행 2열의 경우는 두 문자가 같기 때문에 좌측 위의 0이 그대로 2행 2열에 대입됩니다.

그러나 p, y와 같은 두 문자열이 다른 경우 즉 2행 3열의 경우 좌측, 좌측 위, 위 의 3가지 경우 중 최솟값에 1을 더한 값이 대입됩니다. 여기서는 최솟값이 2행 2열 즉 0 이기 때문에 0에 1을 더한 1이 대입됩니다. 그 과정을 전부 다 하면 다음과 같습니다.

  None p y y t h o n
None 0 1 2 3 4 5 6 7
p 1 0 1 2 3 4 5 6
y 2 1 0 1 2 3 4 5
t 3 2 1 1 1 2 3 4
h 4 3 2 2 2 1 2 3
o 5 4 3 3 3 2 1 2
n 6 5 4 4 4 3 2 1

이 표의 최우 측 하단의 값이 두 문자열을 비교한 후 서로 같게 하는 최소의 액션의 수입니다. python에 y뒤에 혹은 y앞에 y를 삽입하는 1번의 과정으로 pyyhton을 만들 수 있기 때문입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
str1 = "sunday"
str2 = "saturday"
 
n = len(str1)
m = len(str2)
dp = [[0] * (1+m) for _ in range(1+n)]
for i in range(1, n+1):
  dp[i][0] = i
for j in range(1, m+1):
  dp[0][j] = j
for i in range(1, n+1):
  for j in range(1, m+1):
    if str1[i-1] == str2[j-1]:
      dp[i][j] = dp[i-1][j-1]
    else:
      dp[i][j] = min(dp[i][j-1], dp[i-1][j-1], dp[i-1][j]) + 1
 
print(dp[n][m])
 cs

 

 

 

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

서로소 집합 알고리즘 (Python)  (0) 2020.12.30
다익스트라 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)  (0) 2020.12.19
이진탐색 (Python)  (0) 2020.12.16
개념

에라토스테네스의 체는 구간에서 여러 개의 수가 소수인지 아닌지를 판단할 때 유용한 알고리즘입니다. 에라토스테네스의 체를 사용하기에 앞서 소수의 성질을 살펴보겠습니다.

1부터 10까지의 숫자가 있을때 즉 다음과 같을 때 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. 소수는 1을 제외한 수들 중 약수가 자기 자신과 1만 존재하는 수입니다. 따라서 2, 3, 5, 7이 소수입니다. 

 

에라토스테네스의 체알고리즘의 과정은 다음과 같습니다.

 

1. 2부터 N까지 자연수를 나열한다.

2. 숫자들 중 아직 처리하지 않은 수를 찾는다.

3. 그 숫자의 배수들을 제거한다. 단 2 배수부터 제거한다. (2나 3이 제거되는 것을 방지)

4. 위의 2, 3,  과정을 반복한다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import math
# 1부터 100까지의 소수를 모두 찾는 에라토스테네스의 체
n = 100
array = [True] * (1 + n)
 
for i in range(2, int(math.sqrt(n) + 1)):
  if array[i] == True: # 아직 처리되지 않은 숫자인 경우
    j = 2
    while i * j <= n:
      array[i * j] = False
      j += 1
 
for i in range(2, n+1):
  if array[i] == True:
    print(i, end=" ")
 cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22
가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)  (0) 2020.12.19
이진탐색 (Python)  (0) 2020.12.16
bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python)  (0) 2020.12.15

https://www.acmicpc.net/problem/18353

 

18353번: 병사 배치하기

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 가장 긴 증가하는 부분 수열  알고리즘을 알고 있다면 쉽게 해결할 수 있는 문제입니다. 해당 알고리즘에 대해서는 포스팅을 해 놓았습니다. 링크는 다음과 같습니다. https://bgspro.tistory.com/33?category=981927

 

가장 긴 증가하는 부분 수열 - Longest Increasing Subsequence (Python)

개념 가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차

bgspro.tistory.com

먼저 문제의 경우 내림차순으로 배치를 하고자 한다고 합니다. 그러나 가장 긴 증가하는 부분 수열의 경우 오름차순에 대해서 하는 경우가 좀 더 일반적입니다. 따라서 입력받은 리스트를 reverse 함수를 이용해서 역순으로 바꾼 후 LIS 알고리즘을 사용하면 됩니다.

문제 해결을 위한 팁

LIS 알고리즘을 사용할 때 이중 for문을 통해 해결하는데 바깥 for문은 1번째 원소부터 n번째 원소까지, 안쪽 for문은 0번째 원소부터 바깥 for문의 인덱스까지 조회하는 방식으로 해결합니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
data = [0]
ans = [0]*(2+n)
for i in range(1, n+1):
  t, p = map(int, input().split())
  data.append((i, t, p))
 
for i in range(1, n+1):
  day, t, p = data[i]
  if day + t <= n+1:
    ans[i] += p
    for j in range(day+t, n+1):
      ans[j] = max(ans[day], ans[j])
 
print(max(ans))
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
개념

가장 긴 증가하는 부분 수열 다시 말하면 LIS라고도 하는 이것은 다이나믹 프로그래밍 기법 중에 하나입니다. 말 그대로 어떤 수열이 주어졌을 때 해당하는 수열에서 오름차순 혹은 내림차순으로 가장 긴 증가하는 부분의 숫자가 몇 개가 존재하는지를 카운트하는 알고리즘입니다. 예시와 함께 알아보겠습니다.

 

array = [10, 20, 10, 30, 20, 50]일때 가장 긴 증가하는 부분의 숫자를 출력하시오 라는 문제가 있다고 가정하면 10, 20, 30, 50 즉 4가 정답입니다. 이중 for문이 있다면 쉽게 해결할 수 있습니다. array의 길이만큼의 리스트 dp를 1로 초기화한 후 이중 for문으로 조회하면서 해당하는 값에 1을 더한 값과 원래 값의 max값을 넣어주면 되는 것입니다.

소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
arr = [10, 20, 10, 30, 20, 50]
n = len(arr)
dp = [1] * n
 
for i in range(1, n):
  for j in range(i):
    if arr[j] < arr[i]:
      dp[i] = max(dp[i], dp[j]+ 1)
 
print(dp)
print(max(dp))
cs

'알고리즘 > 알고리즘 이론' 카테고리의 다른 글

편집거리 알고리즘 (Python)  (0) 2020.12.22
에라토스테네스의 체를 이용한 소수 판별 (Python)  (0) 2020.12.21
이진탐색 (Python)  (0) 2020.12.16
bisect 라이브러리를 이용한 손쉬운 이진탐색 (Python)  (0) 2020.12.15
BFS 너비 우선탐색 (Python)  (0) 2020.12.03

https://www.acmicpc.net/problem/14501

 

14501번: 퇴사

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 전형적인 다이나믹 프로그래밍 문제 중에 하나입니다. 예시를 기준으로 1일부터 7일까지의 T, P 값을 이용하여 문제를 해결하면 됩니다. 예시를 기준으로 설명을 하겠습니다.

 

1일까지 최대한 많은 금액을 받을수 있는 일정은 1일째만 일하는 10원입니다. 

2일까지 최대한 많은 금액을 받을 수 있는 일정은 2일째만 일하는 20원 입니다.

3일까지 최대한 많은 금액을 받을 수 있는 일정은 2일째만 일하는 20원입니다.

4일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째 일하는 30원입니다.

5일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.

6일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.

7일까지 최대한 많은 금액을 받을 수 있는 일정은 1일째, 4일째, 5일째 일하는 45원입니다.

 

따라서 우리는 먼저 0으로 전부 초기화 한 dp라는 리스트를 생성한 후 해당하는 날짜와 해당 날짜에서 T만큼 지난날을 P로 초기화를 해주면 됩니다. 예시는 다음과 같습니다.

 

먼저 전체가 0으로 된 리스트를 생성합니다.

0 0 0 0 0 0 0

 

1일째 일을 하면 4일째부터 일을 할 수 있으므로 1일에 P를 더해주고 4일째부터는 1일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.

10 0 0 10 10 10 10

 

2일째 일을 하면 7일째부터 일을 할 수 있으므로 2일에 P를 더해주고 7일째부터는 2일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.

10 20 0 10 10 10 20

 

3일째 일을 하면 4일째부터 일을 할 수 있으므로 3일에 P를 더해주고 4일째부터는 3일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.

10 20 10 10 10 10 20

 

4일째 일을 하면 5일째부터 일을 할 수 있으므로 4일에 P를 더해주고5일째부터는 4일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.

10 20 10 30 30 30 30

 

5일째 일을 하면 7일째부터 일을 할 수 있으므로 5일에 P를 더해주고7일째부터는 5일째의 dp값과 해당 날짜의 dp값의 max값을 넣어준다.

10 20 10 30 45 30 45

그 뒤로 6일째와 7일째는 일이 끝나는 날이 N을 벗어나므로 고려하지 않는다.

백준이가 얻을 수 있는 최대 수익은 dp리스트의 max값인 45이다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n = int(input())
data = [0]
ans = [0]*(2+n)
for i in range(1, n+1):
  t, p = map(int, input().split())
  data.append((i, t, p))
 
for i in range(1, n+1):
  day, t, p = data[i]
  if day + t <= n+1:
    ans[i] += p
    for j in range(day+t, n+1):
      ans[j] = max(ans[day], ans[j])
 
print(max(ans))
 
 cs

'알고리즘 > 백준' 카테고리의 다른 글

백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
백준 알고리즘 2110: 공유기 설치 (Python)  (0) 2020.12.18
백준 알고리즘 18310: 안테나(Python)  (2) 2020.12.10

+ Recent posts

티스토리툴바