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

 

1789번: 수들의 합

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 난이도에 비해 생각을 하기가 조금 어려웠던 문제였습니다. 1부터 하나씩 더해가면서 만든 합이 S를 초과하는 순간 1부터 하니씩 더한 숫자들의 개수 - 1이 자연수 N의 최댓값 입니다.

이를 적용하면 다음과 같습니다. 

1 + 2 + 3 + 4 .... + 17 + 18 + 19 + 20 = 210 

즉 20을 더했을때 S를 초과하므로 20까지의 숫자들의 개수(20개) - 1 즉 19 입니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
 
count = 0
ans = 0
for i in range(1, n):
  ans += i
  count += 1
  if ans > n:
    count -= 1
    break
 
print(count)
 cs

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

백준 알고리즘 1946번: 신입 사원(Python)  (0) 2022.01.06
백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27

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

 

10610번: 30

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 그리디 알고리즘으로 그다지 어렵지 않은 문제였습니다. 30의 배수가 되려면 10의 배수이면서 3의 배수여야 합니다. 따라서 내림차순으로 정렬을 하였을 때 일의 자릿수가 0이면서 3의 배수이어야 합니다. 

문제 해결을 위한 팁

저의 경우 내림차순으로 정렬을 하기 위해 각각의 숫자를 str로 입력받은 후 내림차순으로 정렬한 후 int로 변경하였습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
s = list(map(str, input()))
s.sort(reverse = True)
 
temp = ""
for i in range(len(s)):
  temp += s[i]
 
temp = int(temp)
 
if temp % 10 != 0 or temp % 3 != 0:
  print(-1)
else:
  print(temp)
 cs

 

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

백준 알고리즘 11866번: 요세푸스 문(Python)  (0) 2022.01.06
백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27

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

 

1026번: 보물

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 그리디 알고리즘 문제입니다. 각각의 배열의 원소들을 곱한 후 합을 의미하는 S가 가장 작으려면

a 리스트의 가장 작은 값과 b 리스트의 가장 큰 값을 곱한 후 각각의 배열의 원소들을 곱한 후 합하면 됩니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
 
a.sort()
b.sort(reverse = True)
 
sum = 0
for i in range(n):
  sum += (a[i] * b[i])
 
print(sum)
 cs

 

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

백준 알고리즘 1789번: 수들의 합 (Python)  (0) 2022.01.03
백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25

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

 

1010번: 다리 놓기

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 순서를 중요하게 생각하지 않는 '조합'의 방식으로 해결할 수 있는 문제였습니다. 동시에 팩토리얼 연산을 해야 하므로 Dynamic Programming의 방식 역시 문제 풀이의 한 요소였습니다.

팩토리얼을 우리가 흔히 아는 방식 즉 재귀적으로 구현하게 되면 한번 구한 연산을 지속적으로 반복하기 때문에 필요 없는 수많은 연산을 하게 되어 많은 컴퓨팅 리소스를 잡아먹게 됩니다. 또한 당연하게도 시간제한에 걸리게 됩니다. 따라서 이를 시간 내에 구현할 수 있게 하기 위해 피보나치수열 혹은 팩토리얼의 경우 탑다운 또는 보텀업 방식을 이용하여 해결합니다. 

문제에서 N <= M이라는 조건으로 생각해보면 결국 M개의 사이트 중에서 순서에 상관없이 N개를 뽑는 경우입니다. 가령 N이 2개이고 M이 3개일 시, 3개의 M 중에서 2개를 순서에 상관없이 뽑는 경우입니다. (예를 들면 AB, AC, BA, BC, CA, CB) 이를 염두에 두고 소스코드를 작성하면 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
dp = [0] * 31
dp[0] = 1
dp[1] = 1
 
for i in range(2, 31):
  dp[i] = dp[i-1] * i
 
T = int(input())
for i in range(T):
  n, m = map(int, input().split())
  a = dp[m-n]
  b = dp[m]
  c = dp[n]
 
  print((b//a)//c)
 cs

위 소스코드에서 b//a는 mPn이고 이 결과를 c로 나눠야 mCn입니다.

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

백준 알고리즘 10610번: 30(Python)  (0) 2022.01.03
백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23

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

 

1463번: 1로 만들기

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 전형적인 Dynamic programming 방식으로 풀 수 있는 문제입니다. 풀이 역시 정형화되어있기 때문에 쉽게 해결할 수 있습니다. 

문제에서 정수 X에 사용할 수 있는 연산은 다음과 같이 3가지라고 합니다.

 

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.

2. X가 2로 나누어 떨어지면, 2로 나눈다.

3. 1을 뺀다.

즉 이 문제는 먼저 문제에서 주어진 대로 10^6크기의 dp라는 리스트를 만든 후 INF로 초기화해줍니다. 그 후 dp[0], dp[1]은 0으로 재정의 해줍니다. (1로 만드는 것이므로 1은 이미 1이기 때문에 0번의 연산이 필요하므로) 그 후 반복문으로 차근차근 조회해나가면서 1을 빼는 방법, 2를 나누는 방법, 3을 나누는 방법의 필요한 최솟값을 구해주면 됩니다. 

예시에서 보여준 10의 경우를 살펴보겠습니다. 즉 필요한 식은 다음과 같습니다.

min(dp[i-1]+1, dp[i//2]+1, dp[i//3]+1)

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
INF = int(1e9)
 
dp = [INF] * (1+n)
dp[0] = 0
dp[1] = 0
 
for i in range(2, n+1):
  dp[i] = dp[i-1] + 1
  if i % 2 == 0:
    dp[i] = min(dp[i], dp[i//2] + 1)
  if i % 3 == 0:
    dp[i] = min(dp[i], dp[i//3] + 1)
 
print(dp[n])
 cs

 

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

백준 알고리즘 1026: 보물(Python)  (0) 2022.01.03
백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21

이 포스팅은 나동빈 님의 www.youtube.com/watch?v=Ppimbaxm8d8 벨만포드 알고리즘 강의를 참고하였습니다.

개념

벨만 포드 알고리즘은 다익스트라 알고리즘과 비슷하지만 음의 간선이 있는 경우 사용할 수 있다는 점에서 큰 장점을 지닙니다. 또한 음의 간선 사이클이 존재할 경우 이를 검출할 수도 있는 장점을 지니고 있습니다. 

이러한 장점을 가짐과 동시에 O(ElogV)라는 시간복잡도를 지닌 다익스트라 알고리즘과 달리 O(VE)의 시간 복잡도를 지닌다는 단점도 존재합니다.

과정은 다음과 같습니다.

 

1. 출발 노드를 설정합니다.

2. 최단 거리 테이블을 초기화 합니다.

3. 전체 간선 E를 확인합니다. 

4. 각 간선을 확인하며 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 계산합니다.

5. 위의 3, 4번 과정을 n-1번 반복을 합니다.

6. 만약 n번째에서도 최단 거리 테이블이 갱신된다면 음의 간선 순환 사이클이 존재한다는 것입니다.

소스코드
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 sys
input = sys.stdin.readline
INF = int(1e9)
 
n, m = map(int, input().split())
edges = []
dist = [INF] * (1+n)
 
for i in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
 
def bf(start):
    dist[start] = 0
    for i in range(n):
        for j in range(m):
            cur = edges[j][0]
            next_node = edges[j][1]
            cost = edges[j][2]
            if dist[cur] != INF and dist[next_node] > dist[cur] + cost:
                dist[next_node] = dist[cur] + cost
                if i == n-1:
                    return True
    return False
 
negative_circle = bf(1)
 
if negative_circle:
    print(-1)
else:
    for i in range(2, n+1):
        if dist[i] == INF:
            print(-1)
        else:
            print(dist[i])
 
 cs

 

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

크루스컬 알고리즘 (Python)  (0) 2020.12.31
사이클 판별 알고리즘 (Python  (0) 2020.12.31
서로소 집합 알고리즘 (Python)  (0) 2020.12.30
다익스트라 알고리즘 (Python)  (0) 2020.12.22
편집거리 알고리즘 (Python)  (0) 2020.12.22

www.acmicpc.net/problem/13549

 

13549번: 숨바꼭질 3

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일

www.acmicpc.net

 

문제 해결을 위한 과정

이 문제의 경우 BFS를 이용하면 해결할 수 있는 문제였습니다. 보통 BFS 문제의 경우 이차원 리스트 혹은 이차원 배열에서 특정 지점에서 다른 지점으로 퍼져나가는 형식으로 탐색하는 것인데 특이하게 이 문제의 경우 일차원 리스트상에서 해결해야 하기 때문에 처음에는 생각하기가 조금 어려웠던 문제였습니다.

먼저 문제의 예시를 살펴보도록 하겠습니다.

5의 위치에서 시작하여 17까지 가야합니다. 시간이 걸리지 않는 순간이동의 방식으로 현재 위치 * 2 한 지점으로 이동할 수 있습니다. 또는 시간이 1초 걸려서 현재 위치의 좌측 위치 혹은 우측 위치로 이동할 수 있습니다.

이를 너비 우선이 방식으로 큐에 넣어주고 차례 차례 탐색해 나갑니다.

소스코드
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
n, m = map(int, input().split())
max = 100001
visited = [0] * max
move = [-1, 1]
 
def bfs():
    q = deque()
    q.append(n)
    count = 0
    visited[n] = 1
    if 2*n < max and not visited[2*n]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우 순간이동으로 탐색
        visited[2*n] = 1
        q.append(2*n)
    if visited[m] != 0: # 도착점인 경우 
        print(visited[m] - 1)
        return
    while q:
        pos = q.popleft()
        if visited[m] != 0: # 도착점인 경우
            print(visited[m] - 1)
            return
        if 2*pos < max and not visited[2*pos]: # 범위를 벗어나지 않으면서 방문하지 않은 지역인 경우
            visited[2*pos] = visited[pos] # 순간이동으로 탐색
            q.append(2*pos)
        for i in range(2): # 시간을 1초 소비하며 좌, 우를 탐색하는 경우
           npos = pos + move[i]
           if 0 <= npos < max:
               if not visited[npos]:
                   visited[npos] = visited[pos] + 1
                   q.append(npos)
 
bfs()
 
 cs

 

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

백준 알고리즘 1010번: 다리 놓기 (Python)  (0) 2021.12.27
백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 1504: 특정한 최단 경로(Python)  (0) 2021.02.23
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20

www.acmicpc.net/problem/1504

 

1504번: 특정한 최단 경로

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 그러나 주의할 점이 있었는데 바로 꼭 거쳐야하는 2개의 지점이 있다는것 입니다. 지나가야 하는 지점이 x, y라 할 경우

1 -> x -> y -> N

1 -> y -> x -> N 

이렇게 두가지의 경우가 있으므로 위의 두가지 경우에 대한 다익스트라 알고리즘을 적용하여 거리를 각각 구한 후 더 작은 숫자를 출력하면 됩니다. 또한 문제에서 이동할 수 없는 거리라면 -1을 출력하라는 조건이 있었기 때문에 이를 유의하여 해결합니다.

소스코드
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
37
38
39
40
41
42
43
import heapq
INF = 1001
 
n, m = map(int, input().split())
graph = [[] for _ in range(1 + n)]
 
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
 
def dijkstra(start, pos):
    distance = [INF] * (1 + n)
    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]))
       
    return distance[pos]
x, y = map(int, input().split())
dist1 = dijkstra(1, x)
dist2 = dijkstra(x, y)
dist3 = dijkstra(y, n)
 
dist4 = dijkstra(1, y)
dist5 = dijkstra(y, x)
dist6 = dijkstra(x, n)
 
ans = min(dist1 + dist2 + dist3, dist4 + dist5 + dist6)
if ans >= INF:
    print(-1)
else:
    print(ans)
 
 
cs

 

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

백준 알고리즘 1463번: 1로 만들기 (Python)  (0) 2021.12.27
백준 알고리즘 13549: 숨바꼭질 3(Python)  (0) 2021.02.25
백준 알고리즘 1068: 트리(Python)  (0) 2021.02.21
백준 알고리즘 1074: Z(Python)  (0) 2021.02.20
백준 알고리즘 13459: 구슬 탈출(Python)  (0) 2021.02.19

+ Recent posts

티스토리툴바