배극곰의 IT식량창고

문제링크

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

문제설명

4
1 3

1 3 2 4

문제풀이

이해하는데 한참 걸린 문제다.

코드

import sys
from math import factorial

input = sys.stdin.readline
N = int(input())
  
# 자리별로 만들수 있는 순열의 경우의수 저장(팩토리얼 형태임).
Fac = [factorial(i) for i in range(N-1, -1, -1)]
visited = [False] * 21  # 숫자 사용 여부 저장
inputArr = list(map(int,(input().split())))

if inputArr[0] == 1:
    K = inputArr[1] - 1
    numbers = list(range(1, N+1)) #1부터 N까지 배열 생성
    answer = []

    for i in range(N):
        index = K // Fac[i] # K를 자리의 경우의 수로 나눈 몫(정수)
                            # 몫이 0이면 그자리에 그 수를 써도 된다는 얘기
        answer.append(numbers[index])
        numbers.pop(index)
        K %= Fac[i]
    print(*answer)


else:
    numSeq = inputArr[1:]
    K = 1

    for i in range(N):
        dNum = numSeq[i] - 1
        for j in range(i):
            if numSeq[j] < numSeq[i]:
                dNum -= 1
        K += dNum * Fac[i]
    print(K)

문제링크

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

문제설명

7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

45

문제풀이

코드

N = int(input())

T = [0] * (N+1)
P = [0] * (N+1)
D = [0] * (N+2)

for i in range(1, N+1):
    T[i], P[i] = map(int, input().split())

for i in range(N, 0, -1):
    if i+T[i] > N+1:
        D[i] = D[i+1]
    else:
        D[i] = max(D[i+1], D[i+T[i]] + P[i])

print(D[1])

문제링크

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

문제설명

3
4
7
10

7
44
274

문제풀이

코드

T = int(input())

tmp = []

for _ in range(T):
    tmp.append(int(input()))

cache = [0,1,2,4]

for i in range(4,max(tmp)+1): #4부터 N까지 저장된 최댓값까지
    cache.append(cache[i-1]+cache[i-2]+cache[i-3])

for n in tmp:
    print(cache[n])

문제링크

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

5 5
1 3
1 4
4 5
4 3
3 2

3

문제풀이

핵심

- 친구 관계는 서로 맺는 것이므로 양방향 즉, 무향 그래프이다.

- 단계를 나타내므로 가중치는 1이라 생각하자

1. 인접행렬 생성 및 초기화(자기자신이면 0으로, 나머지는 무한대로 초기화)

2. 입력값으로 주어진 친구관계 정보를 인접행렬에 저장.

3. 플로이드-워셜 수행하며 모든 중간경로 탐색.

4. 2차원 배열의 각 행의 총합(케빈 베이컨 수) 저장

5. 케빈베이컨 수를 비교하여 값이 최소인 인덱스를 추출 (여러개라면, 더 작은 번호 출력)

코드

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
matrix = [[float('inf') for _ in range(N+1)]  for _ in range(N+1)]
kev = []
answer = []

# A와 B가 같은 비용은 없다 했으므로 자기 자신으로 가는 비용은 0
for a in range(N+1):
    for b in range(N+1):
        if a == b:
            matrix[a][b] = 0
        if a == 0 or b == 0:
            matrix[a][b] = 0

# 입력값 받아서 해당 행렬 원소 1로 만들기.
for _ in range(M):
    n1, n2 = map(int, input().split())
    matrix[n1][n2] = 1
    matrix[n2][n1] = 1

def floydWarshall():
    for k in range(1, N+1):
        for i in range(1, N+1):
            for j in range(1, N+1):
                matrix[i][j] = min(matrix[i][j], matrix[i][k]+matrix[k][j])
                        

def main():
    #플로이드 워셜 수행
    floydWarshall()

    # 그래프의 행에 속한 원소들의 합을 kev리스트에 삽입.
    for row in matrix:
        kev.append(sum(row))    

    # 최솟값 구할 것이므로 0번째 인덱스는 다시 무한대 수로 수정.
    kev[0] = float('inf')
    minValue = min(kev)

    # 케빈베이컨 수가 가장 적은 사람을 고르는 로직
    for index, value in enumerate(kev):
        if value == minValue:
            answer.append(index)

    print(min(answer))


if __name__ == "__main__":
    main()

문제링크

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

문제설명

5 4
3 1
3 2
4 3
5 3

1 2​

문제풀이

5초로 시간제한이 긴 문제였지만, 파이썬으로 구현하니 15초가 걸렸지만 성공이다. (처음엔 시간초과인줄 안..)

BFS로 풀었다.

일반적인 BFS 방식에서 조금 더 변화를 주면 되는 문제였다.

가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터는?

=> 가장 신뢰높은 컴퓨터라는 얘기가 된다.

즉, 각 컴퓨터에 신뢰도 점수를 부여해 신뢰도가 최댓값인 노드를 찾으면 되는 일이다.

1. 입력값 받아 그래프를 나타내는 이차원배열 생성

2. 모든 컴퓨터를 기점으로 BFS를 진행하며(예제입력값으로 하면 컴퓨터 5대이므로 총 5번)  

   + 탐색을 수행하면서 신뢰도 증가 

3. 모든 BFS 마친후, 신뢰도 리스트 탐색하며 최댓값과 일치하는 인덱스 오름차순 출력

코드

from collections import deque
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
relyList = [0] * (N+1)  # 신뢰도 점수 쌓는 리스트
                        # 전역변수로 둔다. 모든 노드 BFS 각각 하면서 정보 업데이트 할것이므로
answer = []

for _ in range(M):
    n1, n2 = map(int, input().split())
    arr[n1].append(n2)

def BFS(node, graph):
    visited = [False] * (N+1)
    queue = deque()
    queue.append(node)
    visited[node] = True

    while queue:
        cur = queue.popleft()
        for v in graph[cur]:
            if not visited[v]:
                queue.append(v)
                visited[v] = True
                relyList[v] += 1  #특정 노드가 참조한 노드는 신뢰한다는 의미이므로 신뢰도 +1
for i in range(1, N+1):
    BFS(i, arr)

maxValue = max(relyList)

# 신뢰도 리스트 객체 반복하며 max값과 일치하는 인덱스 모두 정답 배열에 삽입
for index, value in enumerate(relyList):
    if value == maxValue:
        answer.append(index)

answer.sort()
print(*answer)

문제링크

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

문제설명

9 3
1 2 3 4 5 6 7 8 9

17

문제풀이

코드

# 이분탐색
# "뭔가 기준점이 있어야하고 그 기준점은 조건에 따라 달라질수가있다." => 이분탐색이겠구나

# 나머지는 일반적인 이분탐색 풀이와 같습니다. 
# 하지만 약간 난이도 있는 이분탐색 문제의 특징처럼 단순히 start와 end 만으로 mid를 찾는 방식이 아니라 주어진 조건을 고려하면서 mid값을 찾아나갔습니다.
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
arr = list(map(int, input().split()))

# ★일반적인 이분탐색과 달리, 정렬 사용하면 안된다. => 문제조건: 순서 보장해야하므로.

start, end = max(arr), sum(arr)

while start <= end:
    mid = (start + end) // 2
    cnt, sum = 0, 0

    # 블루레이에 강의 넣기
    for i in range(N):
        # 지정한 bluRay크기(mid값).벗어난다면 1개 완성.
        if sum + arr[i] > mid: 
            cnt += 1 # bluray 1개 만들어지고 해당 인덱스 원소는 sum에서 제외
            sum = 0 
        sum += arr[i] 
        
        # sum이 0이 아니면 마지막 블루레이 필요
    if sum != 0:
        cnt += 1

    if cnt > M:  # mid값 크기의 blu로 모든 레슨 저장 불가능.
        start = mid + 1    
    else:        # mid값 크기 bluRay로 모든 레슨 저장 가능.
        end = mid - 1


print(start)

문제링크

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

문제설명

55-50+40

-35

코드

arr = input().split("-")
sum = 0
# input값이 100-40+50+74-30+29-45+43+11 이라면
# arr = [100, 40+50+74, 30+29, 45+43+11]

# 0번째 인덱스에 존재하는 문자열도 +가 들어있을 수 있는 문자열임.
# 따라서 +기점으로 분리하여 각 숫자의 총합 구한다.
for item in arr[0].split("+"):
    sum += int(item)

# arr의 1번째 인덱스부터 마지막 원소까지 반복.
# 각 인덱스의 문자열을 +기준으로 split시킨 배열 순회.
# 그리고 sum에서 그 값들을 전부 뺀다. => 최솟값.
for str in arr[1:]:
    for item in str.split("+"):
        sum -= int(item)

print(sum)

문제링크

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

문제설명

4 4 2 1
1 2
1 3
2 3
2 4

4

코드

from collections import deque
import sys

input = sys.stdin.readline
N, M, K, X = map(int, input().split())

arr = [[] for _ in range(N+1)]
visited = [-1] * (N+1)
answer = []

for _ in range(M):
    s, e = map(int, input().split())
    arr[s].append(e)

def BFS(node, graph, visited):
    #탐색시작
    queue = deque()
    queue.append(node)
    visited[node] += 1  # visited리스트에 거리정보 저장.(+1씩 하며)
    
    # queue에 데이터가 있는동안
    while queue:
      cur = queue.popleft()
      for v in graph[cur]:
          if visited[v] == -1:
              visited[v] = visited[cur] + 1
              queue.append(v)
    
    return visited

# BFS 실행
visited = BFS(X, arr, visited)

# visited배열 순회하며 최단거리가 K인 도시 찾기
for i in range(1, N+1):
    if visited[i] == K:
        answer.append(i)

answer.sort()

# 최단거리가 K인 도시가 하나도 없다면 -1출력
if not answer:
    print(-1)
else:
    for item in answer:
        print(item, end='\n')

문제링크

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

문제설명

문제

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

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

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

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

4

문제풀이

BFS로 쉽게 풀 수 있다.

구하고자 하는 건 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수이므로,

1번에서 BFS 시작하여 연결된 모든 노드 수를 구하면 됨.

(그리고 1번은 제외해야하므로 1을 빼주면 끝.)

코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
E = int(input())
graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

for _ in range(E):
    s, e = map(int, input().split())
    graph[s].append(e)
    graph[e].append(s)

#연결된 모든 노드 수 구하면 됨.

def BFS(graph, start):
    queue = deque()
    queue.append(start)
    cnt = 0

    while queue:
        cur = queue.popleft()

        # 방문하지 않은 노드라면
        if not visited[cur]:
            # 방문!
            visited[cur] = True
            cnt += 1
            for node in graph[cur]:
                queue.append(node)

    answer = cnt - 1
    print(answer)

BFS(graph, 1)

문제링크

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

문제설명

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

4

문제풀이

처음에 시도했던 방법은 시작시간을 우선적으로 정렬해보려고 했다.

하지만 핵심은,

시작시간이 아닌 종료시간을 기준으로 우선적으로 정렬하고 종료시간이 같은 강의가 여러개 있다면 그 후 시작시간을 기준으로 정렬하는 것이 핵심. 

그 후 배열을 반복 순회하면서

이전 강의시간의 종료시간보다 이후에 시작하는 강의가 있으면 해당 강의를 포함시킴. (정렬된 상태이므로)

그리고 prev값 갱신

코드

import sys

input = sys.stdin.readline
N = int(input())
arr = [[0, 0] for _ in range(N)]
answer = 0

for i in range(N):
    arr[i][0], arr[i][1] = map(int, input().split())

arr.sort(key=lambda x: (x[1], x[0]))

prev = arr[0][1]
answer = 1
for i in range(1, N):
    # 이전 강의시간의 종료시간보다 나중에 시작한다면
    if arr[i][0] >= prev:
        prev = arr[i][1]
        answer += 1
print(answer)