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

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 잘 못 생각하기가 쉬운 문제였던 것 같습니다. 저도 처음에 그냥 문제를 해결하려 하였다가 틀렸었고 백준 사이트에 질문게시판을 보고 접근방식이 잘못되었다는 것을 알게 된 후 해결할 수 있었던 문제였습니다.

먼저 heap을 이용해야 합니다. 파이썬의 경우 최소 힙 형태로 구현이 되어있기 때문에 보다 쉽게 해결할 수 있었습니다. 예시를 그림과 같이 보겠습니다.

(원래 heap은 트리의 형태로 구현되지만 시인성을 위해 큐의 형태로 그림을 표현하였습니다.)

 

1. 각 원소들을 heapq에 넣어준다.

10 20 40

 

2. heapq에서 원소 두개를 빼준후 더한다.

10 + 20 = 30

30

 

3. 합한 값을 heapq에 넣어준다

30 40

 

4. heapq에서 원소 두개를 빼준 후 더한다.

30 + 40 = 70

None

 

5. 2번에서 구한 30 과 4번에서 더한 70을 더해 100을 만든다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
import heapq
q = []
N = int(input())
for i in range(N):
  heapq.heappush(q, (int(input())))
 
sum = 0
while len(q) > 1:
  temp1 = heapq.heappop(q)
  temp2 = heapq.heappop(q)
  heapq.heappush(q, (temp1+temp2))
  sum += temp1+temp2
print(sum)
 cs

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

백준 알고리즘 2810: 컵홀더 (Python)  (0) 2021.01.19
백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 2437: 저울 (Python)  (0) 2021.01.03
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19

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

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 골드 3 티어 문제로 저는 굉장히 어렵게 풀었던 문제입니다. 그리디 알고리즘으로 해결할 수 있는 문제인데 우선 알아야 하는 것이 있습니다. 바로 1부터 X - 1까지 만들 수 있는 금액이라고 가정을 했을 때 X가 새로 들어온 화폐단위인 a[i]보다 크다면 X원은 만들 수 없다는 것입니다. 이 경우는 저는 암기를 하기로 결정하였습니다. 크루스칼 알고리즘도 그리디이긴 하지만 암기가 필요한 부분입니다. 따라서 해당하는 경우도 암기를 바탕으로 해결합시다.

문제 해결을 위한 팁

팁까지는 아니지만 꼭 짚고 넘어가야할 조건이 있습니다. 바로 리스트가 정렬이 된 상태이어야만 한다는 것입니다.

소스코드

 

1
2
3
4
5
6
7
8
9
10
11
n = int(input())
data = list(map(int, input().split()))
data.sort()
 
target = 1
for x in data:
  if target < x:
    break
  target += x
 
print(target)
 cs

 

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

백준 알고리즘 13305: 주유소(Python)  (0) 2021.01.19
백준 알고리즘 1715: 카드 정렬하기 (Python)  (0) 2021.01.11
백준 알고리즘 18353: 병사 배치하기(Python)  (0) 2020.12.21
백준 알고리즘 14501: 퇴사 (Python)  (1) 2020.12.19
백준 알고리즘 1932: 정수 삼각(Python)  (0) 2020.12.18
개념

크루스컬 알고리즘은 대표적인 최소 신장 트리 알고리즘입니다. 최소 신장 트리란 그래프가 주어져 있을 때 모든 노드들을 포함하고 있으며 사이클이 존재하지 않는 무방향 그래프를 의미합니다. 즉 모든 노드가 연결이 되어있어야 한다는 점과 사이클이 존재하지 않는다는 조건의 교집합이라고 할 수 있습니다. 다음 그림을 보겠습니다. (그림은 나동빈 님의 이것이 취업을 위한 코딩 테스트이다. 를 참고하였습니다.) 

위 그림의 경우 모든 노드들은 연결이 되어있고 사이클이 존재하지 않으므로 신장 트리 입니다. 간선의 개수는 노드의 개수 -1 인 것을 확인할 수 있습니다. 크루스컬 알고리즘은 가능한 신장 트리 중 가장 최소의 비용으로 신장 트리를 연결하는 알고리즘입니다. 과정은 다음과 같습니다.

1. 모든 간선 정보를 따로 리스트에 저장한다. 

2. 리스트에 저장된 간선 정보를 cost가 작은순으로 정렬한 후 사이클의 존재 유무를 파악한다.

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
34
35
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
 
result = 0
edges = []
 
for i in range(e):
  a, b, cost = map(int, input().split())
  edges.append((cost, a, b))
 
edges.sort()
 
for edge in edges:
  cost, a, b = edge
  if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b)
    result += cost
 
print(result)
 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 리스트를 갱신하는 식으로 구현합니다. 플로이드 와샬 알고리즘의 경우 구현이 다익스트라에 비해 쉽다는 단점이 있지만 O(ElogV)의 시간 복잡도를 가지는 다익스트라 알고리즘과 달리 O(N^3)의 시간 복잡도를 가지기 때문에 사용할 수 있는 조건이 매우 한정적입니다. 따라서 문제에서 주어진 N의 범위를 잘 확인한 후 어떤 알고리즘을 사용할지 결정을 해야 합니다.  그럼 그림을 통해 알아봅시다.

나동빈님의 이것이 취업을 위한 코딩테스트이다 그림을 참고하였습니다.

먼저 이차원 리스트를 만든 후 모든 원소에 대해서 무한으로 초기화를 합니다. 그 후 자기 자신의 노드로 가는 최단 경로는 0 이기 때문에 0을 대입해 줍니다. 또한 각각의 노드에서 이동할 수 있는 노드들에 거리를 대입해 줍니다. 그러면 다음과 같은 표가 만들어 집니다. 

  1 2 3 4
1 0 4 INF 6
2 3 0 7 INF
3 5 INF 0 4
4 INF INF 2 0

 

그 후 거쳐가는 노드들을 고려해 줍니다. 예를 들어 1번 노드에서 3번 노드로 가는 경우를 봅시다. 위의 표에서 해당 하는 칸은 즉 1행 3열은 INF로 초기화가 되어있습니다. 그러나 1번 노드에서 4번 노드를 거친 후 3번 노드로 가면 8 이라는 경로가 나오게 됩니다. 따라서 이런 식으로 어떠한 노드에서 다른 노드로 갈 때 거쳐가는 노드를 확인한 후 최솟값으로 대입을 해주면 다음과 같습니다. 

  1 2 3 4
1 0 4 8 6
2 3 0 7 9
3 5 9 0 4
4 7 11 2 0
소스코드

 

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
INF = int(1e9)
 
n = 4
m = 7
graph = [[INF] * (1+n) for _ in range(1+n)]
 
for i in range(1, 1 + n):
  for j in range(1, 1 + n):
    if i == j:
      graph[i][j] = 0
 
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a][b] = c
 
for k in range(1, 1 + n):
  for a in range(1, 1 + n):
    for b in range(1, 1 + n):
      graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
 
for i in range(1, 1 + n):
  for j in range(1, 1 + n):
    if graph[a][b] == INF:
      print("INF", end=" ") 
    else:
      print(graph[i][j], end=" ")
  print()
 cs
개념

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

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

위와 같은 그래프가 있을때 우선 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

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

+ Recent posts

티스토리툴바