[백준] 2178번 미로 탐색
2021-04-09
Algorithm / Python

[백준] 2178번 미로 탐색

출처: [백준] 2178번 미로 탐색

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 192 MB 88211 34772 22181 38.133%

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

1
2
3
4
5
4 6
101111
101010
101011
111011

예제 출력 1

1
15

예제 입력 2

1
2
3
4
5
4 6
110110
110110
111111
111101

예제 출력 2

1
9

예제 입력 3

1
2
3
2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3

1
38

예제 입력 4

1
2
3
4
5
6
7
8
7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4

1
13

힌트

출처

알고리즘 분류

시간 제한

풀이

소스코드

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
import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())
# matrix 배열
matrix = [list(map(int, input().rstrip())) for _ in range(N)]

# 이동할 네 방향 정의 (상,하,좌,우)
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# BFS 소스코드 구현
def bfs(x, y):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque()
    queue.append((x, y))  # 시작점 (0,0)
    # 큐가 빌 때까지 반복하기
    while queue:
        x, y = queue.popleft()
        # 현재 위치에서 4가지 방향으로의 위치 확인
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 미로 탐색 공간 내에서만
            if 0 <= nx < N and 0 <= ny < M:
                # 벽이 아닌경우
                if matrix[nx][ny] == 1:
                    queue.append((nx, ny))
                    matrix[nx][ny] = matrix[x][y] + 1
    # 가장 오른쪽 아래까지의 최단 거리 반환
    return matrix[N - 1][M - 1]


print(bfs(0, 0))

[백준] 2606번 바이러스
2021-04-08
Algorithm / Python

[백준] 2606번 바이러스

출처: [백준] 2606번 바이러스

문제

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.

예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.

img

어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

출력

1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.

예제 입력 1

1
2
3
4
5
6
7
8
7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1

1
4

힌트

출처

알고리즘 분류

풀이

소스코드_BFS

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
import sys
from collections import deque

input = sys.stdin.readline

computers = int(input())
edges = int(input())

networks = {}
for i in range(computers):
    networks[i + 1] = set()

for i in range(edges):
    a, b = map(int, input().split())
    networks[a].add(b)
    networks[b].add(a)


def bfs(network, start):
    queue = [start]
    while queue:
        for i in network[queue.pop()]:
            if i not in visited:
                visited.append(i)
                queue.append(i)


visited = []
bfs(networks, 1)
print(len(visited) - 1)

소스코드_DFS(List)

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
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline


def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


computers, edges = int(input()), int(input())

networks = [[] for _ in range(computers + 1)]
visited = [False] * (computers + 1)

for i in range(edges):
    a, b = map(int, input().split())
    networks[a].append(b)
    networks[b].append(a)

dfs(networks, 1, visited)
print(visited.count(True) - 1)

소스코드_DFS(Dict)

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
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

computers = int(input())
edges = int(input())

networks = {}
for i in range(computers):
    networks[i + 1] = set()

for i in range(edges):
    a, b = map(int, input().split())
    networks[a].add(b)
    networks[b].add(a)


def dfs(graph, v, visited):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)


visited = [False] * (computers + 1)
dfs(networks, 1, visited)
print(visited.count(True) - 1)

[코드잇] 강남역 침수
2021-04-08
Algorithm / Python

[코드잇] 강남역 침수

출처: [코드잇] 강남역 침수

풀이

소스코드

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
def trapping_rain(buildings):
    max_height = max(buildings)
    start_point = False
    current_height = 0
    total = 0

    for i in range(len(buildings) - 1):  # 마지막은 스킵
        if start_point == 0 and buildings[i] > 0:
            start_point = 1
            current_height = buildings[i]
        else:
            if buildings[i] == max_height:
                continue

            if buildings[i] < current_height:
                total += current_height - buildings[i]
            else:
                current_height = buildings[i]

    return total


# 테스트
print(trapping_rain([3, 0, 0, 2, 0, 4]))
print(trapping_rain([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]))

[백준] 3009번 네 번째 점
2021-04-06
Algorithm / Python

[백준] 3009번 네 번째 점

출처: [백준] 3009번 네 번째 점

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 16000 11461 10418 73.335%

문제

세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째 점을 찾는 프로그램을 작성하시오.

입력

세 점의 좌표가 한 줄에 하나씩 주어진다. 좌표는 1보다 크거나 같고, 1000보다 작거나 같은 정수이다.

출력

직사각형의 네 번째 점의 좌표를 출력한다.

예제 입력 1

1
2
3
30 20
10 10
10 20

예제 출력 1

1
30 10

힌트

출처

알고리즘 분류

링크

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import sys

input = sys.stdin.readline

x_list = []
y_list = []

for _ in range(3):
    x, y = map(int, input().split())
    x_list.append(x)
    y_list.append(y)

for i in range(3):
    if x_list.count(x_list[i]) == 1:
        x = x_list[i]
    if y_list.count(y_list[i]) == 1:
        y = y_list[i]

print(x, y)

[백준] 4153번 직각삼각형
2021-04-06
Algorithm / Python

[백준] 4153번 직각삼각형

출처: [백준] 4153번 직각삼각형

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 23581 12574 11416 53.629%

문제

과거 이집트인들은 각 변들의 길이가 3, 4, 5인 삼각형이 직각 삼각형인것을 알아냈다. 주어진 세변의 길이로 삼각형이 직각인지 아닌지 구분하시오.

img

입력

입력은 여러개의 테스트케이스로 주어지며 마지막줄에는 0 0 0이 입력된다. 각 테스트케이스는 모두 30,000보다 작은 양의 정수로 주어지며, 각 입력은 변의 길이를 의미한다.

출력

각 입력에 대해 직각 삼각형이 맞다면 “right”, 아니라면 “wrong”을 출력한다.

예제 입력 1

1
2
3
4
6 8 10
25 52 60
5 12 13
0 0 0

예제 출력 1

1
2
3
right
wrong
right

힌트

출처

알고리즘 분류

풀이

소스코드 1

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

input = sys.stdin.readline

while True:
    edge_list = list(map(int, input().split()))
    edge_list.sort()
    if edge_list[0] == 0:
        break
    if edge_list[0] ** 2 + edge_list[1] ** 2 == edge_list[2] ** 2:
        print('right')
    else:
        print("wrong")

소스코드 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys

input = sys.stdin.readline

while True:
    edge_list = list(map(int, input().split()))
    long_edge=max(edge_list)
    if long_edge == 0:
        break
    edge_list.remove(long_edge)
    if edge_list[0] ** 2 + edge_list[1] ** 2 == long_edge ** 2:
        print('right')
    else:
        print("wrong")

[백준] 9471번 피사노 주기
2021-04-05
Algorithm / Python

[백준] 9471번 피사노 주기

출처: [백준] 9471번 피사노 주기

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 853 602 504 75.224%

문제

1960년, IBM의 직원 Donald Wall은 피보나치 수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다.

예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다.

n 1 2 3 4 5 6 7 8 9 10
F(n) 1 1 2 3 5 8 13 21 34 55
F(n) mod 11 1 1 2 3 5 8 2 10 1 0

나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10임을 알 수 있다.

Wall은 아래와 같은 여러 가지 성질도 증명했다.

  • m > 2인 경우에 k(m)은 짝수이다.
  • 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다.
  • k(m) ≤ m2 - 1
  • k(2n) = 3×2(n-1)
  • k(5n) = 4×5n
  • k(2×5n) = 6n
  • n > 2라면, k(10n) = 15×10(n-1)

m이 주어졌을 때, k(m)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000)

출력

각 테스트 케이스마다 테스트 케이스 번호를 출력하고 k(M)을 출력한다.

예제 입력 1

1
2
3
4
5
6
5
1 4
2 5
3 11
4 123456
5 987654

예제 출력 1

1
2
3
4
5
1 6
2 20
3 10
4 15456
5 332808

힌트

출처

알고리즘 분류

링크

풀이

소스코드

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
import sys

input = sys.stdin.readline

N = int(input())


def fibo(n):
    if len(fibo_list) > n:
        return fibo_list[n]
    else:
        fibo_list[n] = (fibo(n - 1) + fibo(n - 2)) % mod
        return fibo_list[n]


def cycle():
    x = 1
    while True:
        if fibo_list[x] == 0 and fibo_list[x - 1] == 1:
            return x
        x += 1
        fibo(x)


for _ in range(N):
    fibo_list = dict()
    fibo_list[0] = 0
    fibo_list[1] = 1
    fibo_list[2] = 1
    idx, mod = map(int, input().split())

    print(idx, cycle())

[백준] 1003번 피보나치 함수
2021-04-05
Algorithm / Python

[백준] 1003번 피보나치 함수

출처: [백준] 1003번 피보나치 함수

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.25 초 (추가 시간 없음) 128 MB 115259 30059 23610 30.125%

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

1
int` `fibonacci(``int` `n) {``  ``if` `(n == 0) {``    ``printf``(``"0"``);``    ``return` `0;``  ``} ``else` `if` `(n == 1) {``    ``printf``(``"1"``);``    ``return` `1;``  ``} ``else` `{``    ``return` `fibonacci(n‐1) + fibonacci(n‐2);``  ``}``}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

  • fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
  • fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
  • 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
  • fibonacci(0)은 0을 출력하고, 0을 리턴한다.
  • fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
  • 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
  • fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

예제 입력 1

1
2
3
4
3
0
1
3

예제 출력 1

1
2
3
1 0
0 1
1 2

힌트

출처

알고리즘 분류

풀이

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys

input = sys.stdin.readline
t = int(input())

cnt0 = [1, 0]
cnt1 = [0, 1]

for i in range(2, 41):
    cnt0.append(cnt0[i - 1] + cnt0[i - 2])
    cnt1.append(cnt1[i - 1] + cnt1[i - 2])

for _ in range(t):
    n = int(input())
    print(f"{cnt0[n]} {cnt1[n]}")

[백준] 11444번 피보나치 수6
2021-04-04
Algorithm / Python

[백준] 11444번 피보나치 수6

출처: [백준] 11444번 피보나치 수6

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 3363 1774 1450 57.494%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

예제 입력 1

1
1000

예제 출력 1

1
517691607

힌트

출처

알고리즘 분류

풀이

소스코드

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
import sys

input = sys.stdin.readline

N = int(input())
mod = 1000000007
fibo = {}


def fibo_dp(n):
    if n <= 1:
        return n
    elif fibo.get(n):
        return fibo[n]
    else:
        if n % 2 == 1:  # 홀수
            m = (n + 1) // 2
            temp1 = fibo_dp(m)
            temp2 = fibo_dp(m - 1)
            fibo[n] = temp1 ** 2 + temp2 ** 2
            fibo[n] %= mod
            return fibo[n]
        else:  # 짝수
            m = n // 2
            temp1 = fibo_dp(m - 1)
            temp2 = fibo_dp(m)
            fibo[n] = (2 * temp1 + temp2) * temp2
            fibo[n] %= mod
            return fibo[n]


print(fibo_dp(N))


[백준] 10870번 피보나치 수5
2021-04-04
Algorithm / Python

[백준] 10870번 피보나치 수5

출처: [백준] 10870번 피보나치 수5

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 32430 20856 18483 65.290%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (재귀를 이용한 다이나믹 프로그래밍)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys

input = sys.stdin.readline

n = int(input())

fibo_memo = [-1] * 99


def fibo_dynamic(n):
    if 0 < n <= 2:
        return 1
    elif n == 0:
        return 0
    if fibo_memo[n] != -1:
        return fibo_memo[n]
    fibo_memo[n] = fibo_dynamic(n - 1) + fibo_dynamic(n - 2)
    return fibo_memo[n]


print(fibo_dynamic(n))

[백준] 10826번 피보나치 수4
2021-04-04
Algorithm / Python

[백준] 10826번 피보나치 수4

출처: [백준] 10826번 피보나치 수4

시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 8506 2779 2352 39.437%

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 10,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입력 1

1
10

예제 출력 1

1
55

힌트

출처

알고리즘 분류

비슷한 문제

풀이

소스코드 1 (반복문을 이용한 다이나믹 프로그래밍)

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

input = sys.stdin.readline
fibo = [-1] * 10001
fibo[0] = 0
fibo[1] = 1

N = int(input())

for i in range(2, N + 1):
    fibo[i] = fibo[i - 1] + fibo[i - 2]

print(fibo[N])
팔로우

카테고리

최근 글

태그

알고리즘190
Python182
백준172
IT뉴스92
IT Issues92
구현65
자료구조55
네이버39
카카오30
스택26
JS24
Javascript24
자바스크립트24
큐22
문자열20
수학16
Programming16
애플15
그래프 탐색15
해시15
핀테크14
너비 우선 탐색14
BFS14
프로그래머스14
Spring Boot14
Java14
그래프13
DFS13
구글12
그리디12
×