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

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

문제 해결을 과정

이 문제의 경우 기존에 비슷한 문제를 포스팅 한게 있어서 그것으로 대체 하도록 하겠습니다.

https://bgspro.tistory.com/33?category=981927 

 

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

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

bgspro.tistory.com

 

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

백준 알고리즘 1912번: 연속합(Python)  (0) 2022.01.25
백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
 

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

 

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

문제 해결을 위한 과정

이 문제를 해결하는데 있어서 가장 중요한 것은 마지막 계단을 밟아야 한다는 것이며 첫번째 계단을 밟지 않아도 된다는 것 입니다. 문제의 규칙에 따르면 다음과 같습니다.

  1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
  2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.

먼저 계단이 한개일때 최대 점수는 다음과 같습니다.

첫 번째 계단이자 마지막 계단을 밟는 경우 -> 10점

 

계단이 두개일때 최대 점수는 다음과 같습니다.

첫 번째 계단과 마지막 계단을 밟는 경우 ->10 + 20점

 

계단이 세개일때 최대 점수는 다음과 같습니다.

두번째 계단과 마지막 계단을 밟는 경우 -> 20 + 15점

 

계단이 네개일때 최대 점수는 다음과 같습니다.

첫번째 계단과 두번째 계단 및 네번째 계단을 밟는 경우 -> 10 + 20 + 25점

 

다만 세번째 부터 다음과 같은 규칙이 적용되는것을 알 수 있습니다. (단, 마지막 계단이 n번째 일때)

최대의 점수 = max(n번째 계단 + n-2번째 까지의 최대 점수, n번째 계단 + n-1번째 계단 n-3번째 까지의 최대 점수)

이를 소스코드로 표현하면 다음과 같습니다.

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

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

백준 알고리즘 1149번: RGB거리(Python)  (0) 2022.01.24
백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15

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

 

1003번: 피보나치 함수

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 0을 호출하는 횟수, 1을 호출하는 횟수에 관한 것입니다. dp는 우선 n에 따른 결괏값을 나열한 뒤 규칙성을 파악하는 것이 가장 중요합니다. 따라서 n에 따른 규칙성을 파악해 보겠습니다. N의 값에 따른 0이 출력되는 횟수, 1이 출력되는 수를 표로 정리하면 다음과 같습니다.

4를 예시로 들어보면 다음의 그림과 같습니다.

위의 그림과 표에서 볼 수 있듯 fibonacci(4) 는 0을 2회 출력, 1을 3회 출력하는 것을 확인할 수 있다.

위의 표를 잘 살펴 보면 N >= 2일 때의 0, 1의 출력 횟수는 각각 N-1, N-2의 0, 1의 출력 횟수의 합인 것을 알 수 있다.

즉 이러한 규칙성을 가지고 문제를 해결하면 다음과 같다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
tc = int(input())
data = []
for i in range(tc):
  data.append(int(input()))
 
zeroCount = [1, 0]
oneCount = [0, 1]
 
for i in range(2, 41):
  zeroCount.append(zeroCount[i-1] + zeroCount[i-2])
  oneCount.append(oneCount[i-1] + oneCount[i-2])
 
for i in range(tc):
  print(zeroCount[data[i]], oneCount[data[i]])
 cs

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

백준 알고리즘 11053번: 가장 긴 증가하는 부분 수열(Python)  (0) 2022.01.20
백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15

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

 

7569번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100,

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 3차원을 고려해야 한다는 점에서 조금 특이한 문제였습니다. 다만 3차원 리스트라는 점을 제외하면 이전에 풀었던 토마토 문제(https://www.acmicpc.net/problem/7576)와 비슷한 문제 이므로 어렵지 않게 해결할 수 있습니다. 

즉 상자의 위, 아래를 고려해야 하므로 dx, dy 뿐만 아니라 높이를 의미하는 dz 역시 존재해야 합니다. 따라서 for문을 6개로 구분하여 for i in range(6):으로 해결해야 합니다.

문제 해결을 위한 팁

3차원 리스트의 선언은 다음과 같이 선언할 수 있습니다.

graph = [[[0] * m for _ in range(n)]for _ in range(h)]

이렇게 하면 n행 m열의 그래프가 h만큼의 높이를 가지게 됩니다. 

접근하는 방법은 다음과 같습니다. 0번째 층의 1행 2열을 접근하려면 graph [0][1][2]로 접근할 수 있고

1번째 층의 2행 3열에 접근하려면 graph[1][2][3]으로 접근할 수 있습니다. 이 3차원 리스트에 지식을 가지고 접근하면 쉽게 해결할 수 있습니다.

소스코드
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
44
45
46
47
48
49
50
51
from collections import deque
 
def bfs(graph, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y, z = tomato.popleft()
      for i in range(6):
        nx = x + dx[i]
        ny = y + dy[i]
        nz = z + dz[i]
        if nx < 0 or ny < 0 or nz < 0 or nx >= n or ny >= m or nz >= h:
          continue
        if graph[nz][nx][ny] == 0:
          graph[nz][nx][ny] = 1
          tomato.append((nx, ny, nz))
    count += 1
  return count
 
m, n, h = map(int, input().split())
graph = [[[0] * m for _ in range(n)] for _ in range(h)]
tomato = deque()
 
for k in range(h):
  for i in range(n):
    inputData = list(map(int, input().split()))
    for j in range(m):
      graph[k][i][j] = inputData[j]
      if graph[k][i][j] == 1:
        tomato.append((i, j, k))
 
dx = [-1, 1, 0, 0, 0, 0]
dy = [0, 0, -1, 1, 0, 0]
dz = [0, 0, 0, 0, -1, 1]
 
day = bfs(graph, tomato)
numOfZero = 0
 
for k in range(h):
  for i in range(n):
    for j in range(m):
      if graph[k][i][j] == 0: 
        numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 
      
 
 cs

 

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

백준 알고리즘 2579번: 계단 오르기(Python)  (0) 2022.01.19
백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14

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

 

10026번: 적록색약

적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록)

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 적록색약을 가진 분들과 적록색약이 아닌 분들이 보는 것이 다르다는 것을 이용한 문제입니다.

그것을 제외하고는 일반적인 bfs 문제와 같습니다. 예시를 들면 다음과 같습니다.

위의 그림이 있을 때 적록색약이 아닌 분들은 R, G, B로 3가지 구역, 적록색약인 분들은 RG, B로 2가지 구역으로 보는 것입니다. 따라서 이 점에 유의하며 bfs를 구현하면 됩니다.

문제 해결을 위한 팁

저의 경우는 그래프를 2개로 하여 기존에 입력받은 그래프를 복사하여 사용하였습니다. 이를 copy를 이용하였는데 copy의 경우 shallow copy, deep copy가 존재합니다. shallow copy의 경우 원본 혹은 복사본을 수정할 경우 기존의 그래프 역시 수정이 되므로 deep copy를 사용하여야 합니다. 따라서 import copy, 원본 = copy.deepcopy(복사본)를 사용합니다.

소스코드
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
from collections import deque
import copy
 
def bfs(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if graph[nx][ny] == target:
        graph[nx][ny] = 'a'
        q.append((nx, ny))
 
def bfs2(graph, i, j):
  q = deque()
  q.append((i, j))
  target = graph[i][j]
  graph[i][j] = 'a'
  while q:
    x, y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= n:
        continue
      if target == 'R' or target == 'G':
        if graph[nx][ny] == 'R' or graph[nx][ny] == 'G':
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      else:
        if graph[nx][ny] == target:
          graph[nx][ny] = 'a'
          q.append((nx, ny))
      
        
 
n = int(input())
graph = [['a'] * n for _ in range(n)]
for i in range(n):
  inputData = list(input()) 
  for j in range(n):
    graph[i][j] = inputData[j]
 
graph2 = copy.deepcopy(graph)
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
count = 0
for i in range(n):
  for j in range(n):
    if graph[i][j] != 'a':
      bfs(graph, i, j)
      count += 1
 
print(count, end=" ")
 
count = 0
for i in range(n):
  for j in range(n):
    if graph2[i][j] != 'a':
      bfs2(graph2, i, j)
      count += 1
 
print(count)
 cs

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

백준 알고리즘 1003번: 피보나치 함수(Python)  (0) 2022.01.19
백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14

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

 

4963번: 섬의 개수

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도

www.acmicpc.net

문제 해결을 위한 과정

이 문제의 경우 일반적인 상, 하, 좌, 우 네가지 방향을 탐색하는 bfs 문제에서 조금 벗어난 대각선까지 포함하는 8가지 방향을 탐색해야 하는 문제 입니다. 

일반적인 네가지 방향의 경우와 달리 여덟가지 방향을 그림으로 표현하면 다음과 같습니다.

따라서 dx, dy 리스트를 다음과 같이 만들고 for i in range(8)로 반복하면 됩니다.

 

dx = [-1, -1, 0, 1, 1, 1, 0, -1]

dy = [0, 1, 1, 1, 0, -1, -1, -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
from collections import deque
 
def bfs(graph, visited, i, j):
  q = deque()
  q.append((i, j))
  visited[i][j] = 1
  while q:
    x, y = q.popleft()
    for i in range(8):
      nx = x + dx[i]
      ny = y + dy[i]
      if nx < 0 or ny < 0 or nx >= n or ny >= m:
        continue
      if graph[nx][ny] == 1 and visited[nx][ny] == 0:
        visited[nx][ny] = 1
        q.append((nx, ny))
      
dx = [-1, -1, 0, 1, 1, 1, 0, -1]
dy = [0, 1, 1, 1, 0, -1, -1, -1]  
while True:
  m, n = map(int, input().split())
  if m == 0 and n == 0:
    break
  graph = []
  for _ in range(n):
    graph.append(list(map(int, input().split())))
  visited = [[0] * m for _ in range(n)]
 
  count = 0
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 1 and visited[i][j] == 0:
        bfs(graph, visited, i, j) 
        count += 1
  print(count)
 cs

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

백준 알고리즘 7569번: 토마토(Python)  (0) 2022.01.15
백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12

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

 

1697번: 숨바꼭질

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

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 전형적인 bfs의 형태는 아니지만 자주 등장하는 형태입니다. 따라서 이러한 유형을 bfs로 푸는 것에 익숙해져야 합니다. 수빈이가 이동할 수 있는 곳인 (현재 위치 -1, 현재 위치 +1, 현재 위치 * 2)를 bfs의 형태로 탐색을 하여 해결합니다. 다만 주의해야 할 점은 리스트의 범위입니다. 이러한 문제의 경우 인덱스 에러가 쉽게 발생할 수 있으므로 범위에 신경을 써서 문제를 해결해주셔야 합니다. 소스코드는 다음과 같습니다.

소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from collections import deque
 
def bfs(n, k):
  q = deque()
  q.append(n)
  visited[n] = 1
  while q:
    v = q.popleft()
    for i in [v-1, v+1, 2*v]:
      if 0 <= i < 100001 and visited[i] == 0:
        visited[i] = visited[v] + 1
        q.append(i)
      if i == k:
        return visited[i] - 1
 
n, k = map(int, input().split())
visited = [0] * 100001
 
print(bfs(n, k))
 cs

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

백준 알고리즘 10026번: 적록색약(Python)  (0) 2022.01.15
백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 7576번: 토마토(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10

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

 

7576번: 토마토

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토

www.acmicpc.net

문제 해결을 위한 과정

이 문제는 단순한 BFS에서 아주 조금 응용을 하면 쉽게 해결할 수 있는 문제였습니다. 그래프를 입력받을 때 토마토가 들어있는 좌표를 따로 tomato라는 deque를 만들어 저장한다면 쉽게 해결할 수 있었습니다. 그 후로는 일반적인 bfs문제를 풀 때처럼 bfs를 적용합니다. 다만 전체 상자 안에 토마토가 익으려면 며칠이 걸리는지를 물어보는 문제였기 때문에 while 문 안에 for _ in range(len(tomato))를 두어서 이 해당하는 for문을 벗어날 때만 하나씩 count를 증가시켜주면 됩니다. for문을 추가해주는 이유는 한 번에 즉 하루에 bfs로 탐색할 수 있는 양이 tomato라는 deque에 추가되기 때문에 이 deque의 전체가 비면 하루가 지난 것 이기 때문입니다. 추가적으로 bfs로 탐색 후 전체 그래프에서 0 즉 익지 않은 토마토가 하나라도 존재하면 -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
from collections import deque
 
def bfs(grpah, tomato):
  count = 0
  while tomato:
    for _ in range(len(tomato)):
      x, y = tomato.popleft()
      for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
          continue
        if graph[nx][ny] == 0:
          graph[nx][ny] = 1
          tomato.append((nx, ny))
    count += 1
  return count
 
m, n = map(int, input().split())
graph = []
tomato = deque()
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
  graph.append(list(map(int, input().split())))
  for j in range(m):
    if graph[i][j] == 1:
      tomato.append((i, j))
 
day = bfs(graph, tomato)
 
numOfZero = 0
for i in range(n):
  for j in range(m):
    if graph[i][j] == 0:
      numOfZero += 1
 
if numOfZero == 0:
  print(day-1)
else:
  print(-1)
 cs

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

백준 알고리즘 4963번: 섬의 개수(Python)  (0) 2022.01.15
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.14
백준 알고리즘 18870번: 좌표 압축(Python)  (0) 2022.01.12
백준 알고리즘 11723번: 집합(Python)  (0) 2022.01.10
백준 알고리즘 14499번: 주사위 굴리기(Python)  (0) 2022.01.10

+ Recent posts

티스토리툴바