y-log

문제보러가기

🕵️‍♀️ 문제

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

💡 입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

📌 출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

🙋‍♀️ 풀어보자~

A가 B를 신뢰하는 형식이므로 입력을 x, y로 받고 arr[y].append(x)로 해주자.

bfs를 돌릴 때 arr[y]에 연결된 애들이 vistited 된적이 있는지 확인해보고 없으면 방문을 찍고 덱에 첨가해주는 형식으로 작성

from collections import deque

n, m = map(int, input().split())

arr = [[] for _ in range(n+1)]

for _ in range(m):
    x, y = map(int, input().split())
    arr[y].append(x)

def bfs(v):
    q = deque([v])
    visited = [False] * (n + 1)
    visited[v] = True
    count = 1
    while q:
        v = q.popleft()
        for e in arr[v]:
            if not visited[e]:
                q.append(e)
                visited[e] = True
                count += 1
    return count

result = []
max_value = -1

for i in range(1, n+1):
    c = bfs(i)
    if c > max_value:
        result=[i]
        max_value=c
    elif c == max_value:
        result.append(i)
        max_value=c

for e in result:
    print(e, end=" ")

시간 초과 머선일이구,,,

문제보러가기

🕵️‍♀️ 문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

💡 입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

📌 출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

🙋‍♀️ 풀어보자~

우선 배추밭을 0으로 다 채워넣어야 한다.

그리고 그와 같은 크기로 false 인지 true인지를 담아줄 배열을 만든다. ( 왼쪽 상단이 (0, 0)이 되게 )

array=[[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]

그리고 k번씩 돌면서 x, y 에 해당하는 값을 받아준다.

for _ in range(k):
    y, x = map(int,input().split())
    array[x][y] = 1

가로로 m까지 세로로 n까지 for문을 돌면서 array와 visited를 통해 배추는 심어져있지만 방문하지 않은 곳을 찾아 방문해주는 dfs나 bfs를 실행시키면된다.

for i in range(n):
    for j in range(m):
        if array[i][j] and not visited[i][j]:
            dfs(i,j) 나 bfs(i,j)

1. DFS로 풀 경우

재귀 용법을 사용할 것이다. 

파이썬의 재귀 깊이 제한은 1000으로 매우 얕기 때문에, 이 문제를 그냥 푼다면 런타임 에러가 난다.

파이썬으로 재귀를 사용해 풀어야하는 문제라면 setrecursionlimit를 쓰는 것은 선택이 아닌 필수다.

• 상하좌우로 움직일 수 있는 방향을 정해주고 이를 for문으로 돌린다.
• 각 위치의 값이 0보다 크고 최대 길이보다 작은지 1차적으로 확인을 해주고, 이에 해당되지 않는다면 continue를 사용해 다음 위치로 넘겨주게 for문으로 던진다.
• 맞다면 이젠 확인을 해준다. 이곳에 배추가 있고 방문한 적 이 없는가?

# 테스트 케이스 개수를 입력받는다.
# 만약 재귀를 사용해서 풀어야하는 문제라면 setrecursionlimit을 쓰는 것은 선택이 아닌 필수다.
# 파이썬의 기본 재귀 깊이 제한은 1000으로 매우 얕다.
# 따라서 재귀로 문제를 풀경우 이제한에 걸려 에러메세지를 볼수 없다.
# 런타임 에러가 난다.
import sys
sys.setrecursionlimit(100000)

def dfs(x,y):
    visited[x][y] = True
    directions = [ (-1, 0), (1, 0), (0, -1), (0, 1)]
    # 상하 좌우로 움직일 수 있는 방향을 지정해주고 여기서 for문을 돌린다.
    for dx, dy in directions:
        nx, ny = dx + x, dy+y
        if nx < 0 or nx >=n or ny<0 or ny>=m:
            continue
        if array[nx][ny] and not visited[nx][ny]:
            dfs(nx,ny)

for _ in range(int(input())):
    m, n, k = map(int,input().split())
    array=[[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    for _ in range(k):
        y, x = map(int,input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                dfs(i,j)
                result += 1
    print(result)

2. BFS로 풀어보면,,,

BFS는 덱..deque 

dfs와 마찬가지로 움직일 수 있는 상하좌우의 위치를 담아 for문을 돌려줄 것이다. 

from collections import deque

def bfs(x,y):
    q = deque()
    q.append((x,y))
    visited[x][y] = True
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while q:
        x, y = q.popleft()
        for dx, dy in directions:
            nx, ny = x+dx, y+dy
            if nx < 0 or nx >= n or ny < 0 or ny >= m:
                continue
            if array[nx][ny] and not visited[nx][ny]:
                q.append((nx,ny))
                visited[nx][ny]=True


for _ in range(int(input())):
    m, n, k = map(int,input().split())
    array=[[0]*m for _ in range(n)]
    visited = [[False]*m for _ in range(n)]
    for _ in range(k):
        y, x = map(int,input().split())
        array[x][y] = 1
    result = 0
    for i in range(n):
        for j in range(m):
            if array[i][j] and not visited[i][j]:
                bfs(i,j)
                result += 1
    print(result)

문제보러가기

🕵️‍♀️ 문제

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

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

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

💡 입력

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

📌 출력

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

🙋‍♀️ 풀어보자~

com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)

for i in range(int(input())):
  x, y = map(int, input().split())
  adj[x].append(y)
  adj[y].append(x)

def dfs(v):
  visited[v] = True
  for e in adj[v]:
    if not visited[e]:
      dfs(e)
  
dfs(1)

for i in range(len(visited)):
  if visited[i] == True:
    cnt += 1
    
print(cnt-1)

2. BFS로 풀어보면,,,

from collections import deque

com = int(input())
cnt = 0
adj = [[] for _ in range(com+1)]
visited = [False] * (com+1)

for i in range(int(input())):
  x, y = map(int, input().split())
  adj[x].append(y)
  adj[y].append(x)

def bfs(v):
  q = deque([v])
  visited[v] = True
  while q:
    v = q.popleft()
    for e in adj[v]:
      if not visited[e]:
        q.append(e)
        visited[e]= True

  
bfs(1)

for i in range(len(visited)):
  if visited[i] == True:
    cnt += 1

print(cnt-1)

BOJ 14719

🕵️‍♀️ 문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

💡 입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

📌 출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

🙋‍♀️ 풀어보자~

빗물이 고이기 위해서는 기둥이 필요하다. 

이 기둥이 어떻게 생기는지 생각해보자.

위 사진과 같이 max인 4를 기준으로 좌우의 가장 큰 값인 3과 2의 값이 중요함을 알 수 있다.

왼쪽은 3을 기준으로 빗물이 받아지고 오른쪽은 2를 기준으로 빗물이 받아지기 때문~

더 자세하게 보자면..

각 자리를 i로 보고 0부터 7까지 번호를 매겼을 때 2번째 블럭을 보자.

i=2번째 블럭은 2개로 이 블럭을 기준으로 빗물 기둥이 되어줄 좌우의 max 숫자를 살펴보면 3과 4임을 알 수 있다.

여기서 max중 작은 수가 기준이 되기 때문에 3이라는 숫자를 이용해주게 된다.

정리하자면~

• 양쪽에 더 높은 블럭이 존재하면 빗물이 고임
• 반복문을 돌면서 현재의 블럭 기준 left_max와 right_max를 구하고 이 두 값중 작은 수를 구함
  • 구해진 수 - 현재 블럭의 수 가 빗물이 담길 칸수다.
  • 첫 블럭과 마지막 블럭은 볼필요 없다. (그림과 같은 예시를 이용하자면, i=0일 때와 i=7일 때)

# 빗물

# 입력을 받아 준다.
H, W = map(int, input().split())
block = list(map(int, input().split()))
answer = 0

# 맨 앞뒤를 제외한 for문을 돌면서 왼쪽과 오른쪽에서 최댓값을 찾는다.
for i in range(1, W-1):
    left_max = max(block[:i]) # 현재 블럭을 기준으로 왼쪽에서 max 값 찾기
    right_max = max(block[i+1:]) # 현재 블럭을 기준으로 오른쪽에서 max 값 찾기
    m = min(left_max, right_max) #left_max와 right_max 중 작은 값을 변수에 담자.
    
    # 현재 블럭이 지정한 기준값보다 작으면 빗물이 고인다.
    if block[i] < m:
        answer += m - block[i]

print(answer)

BOJ 1149

🕵️‍♀️ 문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

💡 입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

📌 출력

• 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
  
  

🙋‍♀️ 풀어보자~

다이나믹 프로그래밍으로 접근해서 Memoization을 사용하자.

2차원 배열을 이용해서 각 자리마다 RGB의 비용을 담을 수 있게 하자.

just like... -> [ [ 1번 집의 R비용, 1번 집의 G비용, 1번 집의 B비용 ] , [ 2번 집의 R비용, ....

점화식을 떠올리기 위해서 i번째의 집과 그 앞뒤의 i-1번째 집과 i+1번째 집을 생각해보자.

i+1번째 집은 i번째 집의 색에 영향을 받지만 i-1번째 집의 색에는 영향을 받지 않는다.

이 같은 상황을 점화식으로 생각해보자. i와 i+1만 생각해주면된다~

1. i+1번째 집이 R일 때, i-1은은 G나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
2. i+1번째 집이 G일 때, i-1은은 R나 B 중 더 적은 비용을 갖는 것을 선택하면 된다.
3. i+1번째 집이 B일 때, i-1은은 R나 G 중 더 적은 비용을 갖는 것을 선택하면 된다.

# RGB

# n : 집의 수
n = int(input())

# 초기세팅 0으로 다 깔아놓거라
dp = [[0, 0, 0] for _ in range(n)]

for i in range(n):
    # 우선 먼저 입력받음
    cost = list(map(int, input().split()))

    # 첫 입력인 경우, 그냥 cost를 담아주세요.
    if i == 0:
        dp[0] = cost
    else:
        # 점화식 넣어주세효
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + cost[0] # i번째집이 R일경우
        dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + cost[1] # i번째집이 G일경우
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + cost[2] # i번째집이 B일경우

# dp 리스트의 n-1번째에 있는 누적된 RGB 비용 중 가장 최소 값을 출력한다.
print(min(dp[n-1]))

풀이

pypy3으로 출력해야 시간초과가 나지 않는다~!

1. N으로 개수 입력을 받는다.
2. numbers 라는 빈 리스트를 만들어준다.
3. 받아준 N 횟수만큼 for문을 돌리며 숫자를 입력받는다.
4. sort함수를 써서 오름차순 정렬을 해준다.
5. 출력은 '\n'.join(리스트) : \n과 값을 넣어서 하나의 문자열로 합쳐준다.

import sys
input = sys.stdin.readline

N = int(input())
numbers = []

for _ in range(N):
    numbers.append(int(input()))

numbers.sort()
print('\n'.join(map(str, numbers)))