반응형

문제 풀이

1. dictionary 자료구조를 활용하여 각 나무의 등장 횟수를 세어줍니다.

2. 이 때, defaultdict를 사용하면, 해당 나무가 이미 등장한 적이 있는지 검사하는 코드를 작성할 필요가 없습니다.

3. format 함수를 이용하여 각 나무의 점유율을 소수점 넷째 자리까지 출력합니다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import sys
from collections import defaultdict
 
readline = sys.stdin.readline
 
def main():
    dic = defaultdict(int)
    tot = 0
    try:
        while 1:
            word = readline().rstrip()
            if not word:
                break
            dic[word] += 1
            tot += 1
    except EOFError:
        exit()
 
    for t in sorted(dic.keys()):
        print(t,format(dic[t]/tot*100,'.4f'))
if __name__=='__main__':
    main()
 cs

 

 

문제링크

 

4358번: 생태학

프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어

www.acmicpc.net

 

반응형

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

백준 20299 3대 측정  (0) 2020.12.04
백준 11057 오르막 수 Python  (0) 2020.12.03
백준 1520 내리막 길  (0) 2020.10.20
백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
반응형

문제 풀이

dp와 dfs를 함께 사용해야하는 문제이다.

1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.

2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.

  2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.

  2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.

  2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.

 

Python Code

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(10000)
# 0: 상, 1: 좌, 2: 하, 3: 우
a = [0,-1,0,1]
b = [-1,0,1,0]
def dfs(x,y):
    if dp[y][x] == -1 : 
        dp[y][x] = 0
    if x<0 or x>n-1 or y<0 or y>m-1: return 0
    for i in range(4):
        nx = x + a[i]
        ny = y + b[i]
        if (0 <= nx <= n-1 and 0 <= ny <= m-1) and maps[ny][nx] > maps[y][x] :
            if dp[ny][nx] > 0:
                dp[y][x] += dp[ny][nx]
            # 방문한 적 없으면 dfs
            elif dp[ny][nx] == -1 :
                dp[y][x] += dfs(nx,ny)
    return dp[y][x]
        
if __name__ == '__main__':
    m,n = map(int,sys.stdin.readline().split())
    maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
 
    dp = [[-1] * n for _ in range(m)]
    dp[0][0] = 1
    dfs(n-1,m-1) 
    print(dp[-1][-1])
 
 cs

Line 9 : 지도를 벗어나면 0을 반환한다.

Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).

 

문제 링크

 

1520번: 내리막 길

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으�

www.acmicpc.net

 

반응형

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

백준 11057 오르막 수 Python  (0) 2020.12.03
백준 4358 생태학  (0) 2020.10.21
백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
반응형

문제 풀이

1. 공백을 기준으로 단어를 잘라 단어의 개수를 출력하는 문제이다.

2. 앞 뒤에 공백이 있는 경우가 있으므로 strip() 함수로 앞뒤 공백을 제거해준다.

3. ' ' 가 입력으로 들어오는 경우를 고려해주어야한다.

Python Code

1
2
temp = input().strip()
print(len(temp.split(' ')) if len(temp) > 0 else 0)
 cs

문제 링크

 

1152번: 단어의 개수

첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 �

www.acmicpc.net

 

반응형

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

백준 4358 생태학  (0) 2020.10.21
백준 1520 내리막 길  (0) 2020.10.20
백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
반응형

문제 풀이

1. 주어진 시간이 hh:mm 일 때, mm에서 45를 빼준다.

2. 1의 값이 0보다 작은 경우 mm에 60을 더해준 후, hh에서 1을 빼준다.

3. 2 이후 hh가 -1이라면 23으로 바꿔준다.

 

* 다른 풀이로는 hh를 분으로 바꿔준 후, 45를 빼서 다시 시간과 분으로 바꿔주는 방법이 있다..

(hh * 60 + mm - 45 후 60으로 나눈 몫이 시간, 나머지가 분)

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
 
def solve(hh,mm):
  mm -= 45
  if mm < 0 :
    mm += 60
    hh -= 1
    if hh >= 0:
      return hh,mm
    else :
      return 23,mm
  else :
    return hh,mm
 
if __name__=='__main__':
  hh,mm = map(int,sys.stdin.readline().split())
  nh, nm = solve(hh,mm)
  print(nh,nm)
 cs

문제 링크

 

2884번: 알람 시계

문제 상근이는 매일 아침 알람을 듣고 일어난다. 알람을 듣고 바로 일어나면 다행이겠지만, 항상 조금만 더 자려는 마음 때문에 매일 학교를 지각하고 있다. 상근이는 모든 방법을 동원해보았지만, 조금만 더 자려는 마음은 그 어떤 것도 없앨 수가 없었다. 이런 상근이를 불쌍하게 보던, 창영이는 자신이 사용하는 방법을 추천해 주었다. 바로 "45분 일찍 알람 설정하기"이다. 이 방법은 단순하다. 원래 설정되어 있는 알람을 45분 앞서는 시간으로 바꾸는 것이다.

www.acmicpc.net

 

반응형

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

백준 1520 내리막 길  (0) 2020.10.20
백준 1152 단어의 개수  (0) 2020.08.31
백준 9465 스티커  (0) 2020.04.18
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 1002 터렛  (0) 2020.04.09
반응형

문제 풀이

a0 a1 a2 a3 a4
b0 b1 b2 b3 b4

 스티커가 위와 같이 있다고 할 때, r번 행의 c번 열 스티커를 붙였을 때의 최댓값을 dp[r][c]라 하면, dp의 점화식은 아래와 같이 쓸 수 있다.

 r=0 인 경우 : dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]

 r=1 인 경우 : dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]

 

 위의 그림에서 a3를 붙였을 경우를 예로 들면, 스티커를 앞에서부터 붙인다면 a1, b1, b2를 붙인 다음에 a3를 붙이는 경우가 가능하다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
def solution(s):
  dp = [[s[i][0]] + [0]*(len(s[0])-1) for i in range(2)]
  dp[0][1] = dp[1][0]+s[0][1]
  dp[1][1] = dp[0][0]+s[1][1]
  for i in range(2,len(s[0])):
    dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]
    dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]
  print(max(dp[0][-1],dp[1][-1]))
 
if __name__=="__main__":
  n = int(input())
  for _ in range(n):
    size = int(input())
    s = []
    for i in range(2):
      s.append(list(map(int,sys.stdin.readline().split())))
    solution(s)
 cs

Line 3 ~ 5 : Line 6의 for문으로 dp를 처리하는 과정에서 dp[r][i-2] 연산이 들어가므로 첫 번째, 두 번째 열(c=0,1)을 미리 처리해야 한다.

문제 링크

 

9465번: 스티커

문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점

www.acmicpc.net

 

반응형

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

백준 1152 단어의 개수  (0) 2020.08.31
백준 2884 알람 시계  (0) 2020.05.08
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 1002 터렛  (0) 2020.04.09
백준 11048 이동하기  (0) 2020.03.30
반응형

벨만 포드 알고리즘 학습을 위해 풀어본 문제이다.

문제풀이

 벨만 포드 알고리즘 문제로, 벨만 포드 알고리즘의 자세한 내용은 여기를 참고.

 간단히 요약하자면, 노드 수를 n이라 하면, 모든 노드에 대한 relaxation을 n-1번 진행한다. 아래의 코드를 보면 총 3중 for문으로 구성되는데, 첫 번째 for문이 relaxation을 n-1번 진행할 때의 n-1이고, 두 번째 for문이 relaxation을 수행하는 노드이고, 마지막 for문이 relaxation을 수행하기 위한 두 번째 for문의 변수 노드의 이웃 탐사가 된다.

 여기서 머리 아픈 문제는 음의 루프가 존재해서 루프를 돌수록 시간이 무한히 과거로 가는 것인데, n-1번의 모든 노드에 대한 relaxation이 모두 이루어지면 더이상 relaxation이 이루어지지 않는다는 점을 활용하여, relaxation을 한번 더 수행하여 relaxation이 일어난다면 음의 루프가 있다고 판정한다.

Python Code

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
import sys
def bf(n,edge):
  INF = 999999999
  dist = [0,0] + [INF for _ in range(n-1)]
  
  for count in range(1,n+1):
    for a in range(1,n+1):
      if dist[a] != INF :
        for b,c in edge[a].items():
          if dist[b] > dist[a]+c :
            dist[b] = dist[a]+c
            if count == n:
              print(-1)
              return
  for a in range(2,n+1):
    print(dist[a] if dist[a] != INF else -1)
 
 
if __name__=="__main__":
  n,m = map(int,sys.stdin.readline().split())
  edge = {}
  for a in range(1,n+1):
    edge[a]={}
  for _ in range(m):
    a,b,c = map(int,sys.stdin.readline().split())
    edge[a][b]= min(c,edge[a][b]) if b in edge[a] else c
  bf(n,edge)
 cs

 

Line 4 : 1번노드에서 i번 노드까지 걸리는 시간으로, n개의 노드가 1부터 n이므로 0을 사용하지 않기 위해 0번째와 1번째를 0으로 하고 뒤부터는 INF로 초기화한다.

Line 6 : n-1 +1 번 모든 노드에 대한 relaxation을 수행한다고 했는데, relaxation이 몇 회차인지를 나타내는 첫 번째 for문이 된다.

Line 7 : relaxation을 수행하는 노드로 두번째 for문이 된다.

Line 8 : relaxation을 수행하는 노드가 아직 접근할 수 없는 노드이면 relaxation을 수행하지 않는다.

Line 9 : Line 7의 노드의 이웃들을 탐사하는 마지막 for문이 된다.

Line 12 : 음의 루프를 탐사하기 위한 조건으로, n번째에는 relaxation이 일어나면 안 된다.

Line 21 : 링크들이 담겨있는 딕셔너리로, key는 노드 번호이고, value는 (key가 도착 노드, value가 걸리는 시간)인 딕셔너리이다.

 

문제 링크

 

11657번: 타임머신

첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. 

www.acmicpc.net

 

반응형

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

백준 2884 알람 시계  (0) 2020.05.08
백준 9465 스티커  (0) 2020.04.18
백준 1002 터렛  (0) 2020.04.09
백준 11048 이동하기  (0) 2020.03.30
백준 10610 30  (0) 2020.03.28
반응형

문제풀이

 원의 접점의 개수를 구하는 문제이다.

 두 원의 반지름 r1, r2 중 작은 것을 r, 큰 것을 R, 중심 사이의 거리를 dist라 할 때, 접점의 개수는 다음과 같다.

 접점이 한 개인 경우 : 내접(dist + r == R) 또는 외접(dist == r + R)

 없는 경우 : 두 점 사이의 거리가 반지름의 합보다 큰 경우(dist > r+R), 또는 큰 원 안에 작은 원이 들어가 있는 경우(dist + r < R)

 두 개인 경우 : 나머지

Python Code

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, math
def solution(x1,y1,r1,x2,y2,r2):
  if x1 == x2 and y1 == y2 :
    if r1 == r2:
      return -1
    else :
      return 0
  
  dist = math.sqrt((x1-x2)**2 + (y1-y2)**2)
  r = min(r1,r2)
  R = max(r1,r2)
  s = r + R
 
  #떨어져서 또는 큰원 안에 작은 원
  if dist > s or (dist + r < R): return 0
 
  #내접, 내접
  elif dist + r == R or dist == s: return 1
 
  else : return 2
 
if __name__=="__main__":
  n = int(sys.stdin.readline())
  for _ in range(n):
    x1,y1,r1,x2,y2,r2 = map(int,sys.stdin.readline().split())
    print(solution(x1,y1,r1,x2,y2,r2))
 cs

문제 링크

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

 

반응형

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

백준 9465 스티커  (0) 2020.04.18
백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 11048 이동하기  (0) 2020.03.30
백준 10610 30  (0) 2020.03.28
백준 2436 공약수  (0) 2020.03.24
반응형

문제풀이

(r, c)까지 왔을 때 가질 수 있는 사탕의 최댓값을 dp[r][c]이라 하면, 점화식은 다음과 같이 쓸 수 있다.

dp[r][c] = max(dp[r][c-1], dp[r-1][c]

즉, (r,c) 까지 오는 방법은 같은 행의 왼쪽 열에서 오거나, 이전 행의 같은 열에서 오는 두가지 방법이 있다. 

따라서 모든 r을 0부터 n까지 반복한 후, dp[n][m]을 반환하면 된다.

 

Python Code

1
2
3
4
5
6
7
8
9
10
11
import sys
n,m = map(int,sys.stdin.readline().split())
dp = list(map(int,sys.stdin.readline().split()))
for j in range(1,m):
    dp[j] = dp[j-1]+dp[j]
for i in range(1,n):
    maze = list(map(int,sys.stdin.readline().split()))
    dp[0]+=maze[0]
    for j in range(1,m):
        dp[j] = max(dp[j-1]+maze[j],dp[j]+maze[j])
print(dp[-1])
 cs

Line 4 : 첫번째 행에 대한 연산이다.

Line 6 : 두번째 행 이후에 대한 연산이다.

 

비효율적이었던 풀이

 풀이 설명을 보면 dp가 n*m 인 행렬이지만, 위의 코드는 길이가 m인 배열이다. 처음에는 maze 행렬을 모두 받아서 가진 상황에서 풀이를 했는데, 시간이 다른 풀이들에 비해 오래걸렸다. 좀 더 효율적으로 수정한 코드가 위의 코드이며, maze를 한줄씩 받으며 즉시 처리하는 식으로 바꿨더니 시간이 1632ms에서 720ms로 절반이상 줄었다. 메모리 역시 절반 이상 줄일 수 있었다.

 아래는 첫 풀이이다. 위의 코드와는 달리 bfs를 이용하여 0,0 부터 m,n까지 dp 행렬을 채워나갔으며, 위에서 말했듯, maze를 모두 받고 시작했고, dp는 모든 요소가 0인 m*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
import collections
import sys
 
def summation(maze):
    ans = 0
    for m in maze:
        ans += sum(m)
    return ans 
 
n,m = map(int,sys.stdin.readline().split())
maze = []
for i in range(n):
    maze.append(list(map(int,sys.stdin.readline().split())))
 
 
if n < 2 or m < 2:
    print(summation(maze))
else:
    dp = [[0 for i in range(m)] for j in range(n)]
    dp[0][0]=maze[0][0]
    q = collections.deque()
    q.append([1,0])
    q.append([0,1])
    while q:
        row,col = q.popleft()
        if col == 0 : dp[row][col]=dp[row-1][col]+maze[row][col]
        elif row == 0 : dp[row][col]=dp[row][col-1]+maze[row][col]
        else : dp[row][col] = max(dp[row-1][col]+maze[row][col], dp[row][col-1]+maze[row][col])
 
        if row == n and col == m : break
        if col == 0 and row < n-1 :
            q.append([row+1,col])
        if col < m-1 :
            q.append([row,col+1])
    print(dp[-1][-1])
 cs

 

 

문제 링크

 

11048번: 이동하기

준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으

www.acmicpc.net

 

반응형

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

백준 11657 타임머신 / 벨만 포드 알고리즘  (0) 2020.04.11
백준 1002 터렛  (0) 2020.04.09
백준 10610 30  (0) 2020.03.28
백준 2436 공약수  (0) 2020.03.24
백준 2559 수열  (0) 2020.03.23

+ Recent posts

티스토리툴바