'백준 알고리즘' 태그의 글 목록

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

이 포스팅은 나동빈 님의 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])
 
Colored by Color Scripter

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/1475

1475번: 방 번호

첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수 또는 0이다.

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 키 포인트는 9와 6이 서로 뒤집을 수 있다는 것입니다. 그 숫자들을 제외하고는 숫자의 개수만큼 세트의 개수가 증가하기 때문에 고려하기 쉽습니다. 따라서 0부터 9까지 0으로 초기화된 리스트를 선언하고 6, 9는 더 작은 인덱스 번째를 증가시켜주고 그 외의 숫자는 해당 인덱스의 값을 증가시켜주는 방법을 통하면 쉽게 계산할 수 있습니다.

35996가 입력으로 주어진다고 가정하면 3번째 인덱스 5번째 인덱스의 값을 각각 증가시킵니다. 이를 그림으로 표현하면 다음과 같습니다.

0

초기 상태

0

1

0

1

0

3번째와 5번째를 하나씩 증가시킨 후

0

1

0

1

0

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 인덱스를 증가시킴 편의상 낮은 인덱스를 증가시킴

0

1

0

1

0

1

9가 왔으므로 6번째 인덱스와 9번째 인덱스중 더 작은 값을 가지는 9번째 인덱스를 증가시킴

0

1

0

1

2

0

1

6이 왔으므로 6번째 인덱스와 9번째 인덱스 중 더 작은 값을 가지는 6번째 인덱스를 증가시킴

이렇게 각 인덱스를 증가시키는 과정이 끝난 후 리스트에서 최댓값을 출력하면 필요한 세트의 수가 나오는 것을 알 수 있다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13

word = input()
ans = [0] * 10
for i in range(len(word)):
    num = int(word[i])
    if num == 6 or num == 9:
        if ans[6] <= ans[9]:
            ans[6] += 1
        else:
            ans[9] += 1
    else:
        ans[num] += 1
 
print(max(ans))

cs

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

백준 알고리즘 14503: 로봇 청소기(Python) (0)	2021.02.03
백준 알고리즘 10773: 제로(Python) (0)	2021.02.03
백준 알고리즘 7568: 덩치(Python) (0)	2021.02.03
백준 알고리즘 1966: 프린터 큐(Python) (0)	2021.02.02
백준 알고리즘 1316: 그룹 단어 체커(Python) (0)	2021.02.02

방구석프로의 이야기