11724_연결 요소의 개수 (Python)

0. 출처

• 유형 : 탐색 (silver 2)
• 링크 : 11724번: 연결 요소의 개수

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
6 5
graph = [[], [2,5]. [1,5], [4], [3,6], [2,1], [4]]
visited = [[], [True], [True], [False], [Faase], [True], [False]]

>> 위의 형태로 만들어 줄 것임

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
정점의 개수 n / 간선의 개수 m
6 5
1 2
2 5
5 1
3 4
4 6

- 예제 출력 1 -
2

- 예제 입력 2 -
6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

- 예제 출력 2 -
1

(3) 코드

import sys
from collections import deque


def input():
    return sys.stdin.readline().rstrip()


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

graph = [[] * m for _ in range(n + 1)]
visited = [False for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


# fixme - flag로 노드 덩어리에 대해 탐색을 진행했는지 파악한다.
def iterative_bfs(s):
    q = deque([])
    q.append(s)
    flag = 0

    if visited[s] == False:
        visited[s] = True
        flag = 1

    while q:
        v = q.popleft()
        for w in graph[v]:
            if visited[w] == False:
                q.append(w)
                visited[w] = True

    return flag


# fixme - 노드 덩어리의 갯수를 찾아주기 위함
cnt = 0

for s in range(1, n + 1):
    flag = iterative_bfs(s)
    if flag == 1:
        cnt += 1

print(cnt)

(4) 정리

flag 로 방문하지 않는 노드 덩어리의 탐색 여부를 확인합니다.
flag 가 1인 경우 탐색을 했다는 의미이고 flag 가 0인 경우는 노드 덩어리를 찾지못했다는 의미입니다.

(5) 참고

11659__구간 합 구하기 4 (Python)

0. 출처

• 유형 : 구간 합 (silver 3)
• 링크 : 11659번: 구간 합 구하기 4

1. 기록

• 22/07/01 (금)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
구하고자 하는 구간의 인덱스 숫자를 다음과 같이 바꿔준다.
0 2
1 3
4 4

[a0, a1, a2, a3, a4]
[5, 4, 3, 2, 1]

s0 = a0
s1 = a0 + a1
s2 = a0 + a1 + a2
s3 = a0 + a1 + a2 + a3
s4 = a0 + a1 + a2 + a3 + a4

[s0, s1, s2, s3, s4] 
[5, 9, 12, 14, 15]

위의 배열에서 규칙을 찾으면 쉽게 구할 수 있다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
수의 개수 / n과 합을 구해야 하는 횟수
5 3
5 4 3 2 1
1 3
2 4
5 5


- 예제 출력 1 -
12
9
1

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

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

nums = list(map(int,input().split()))

for i in range(1, len(nums)):
    nums[i] = nums[i] + nums[i-1]

for _ in range(m):
    s, e = map(int, input().split())
    s = s-1
    e = e-1
    if s == 0:
        print(nums[e])
    else:
        print(nums[e]-nums[s-1])

(4) 정리

(5) 참고

11047_[문제이름] (Python)

0. 출처

• 유형 : 그리디 (silver 4)
• 링크 : 11047번: 동전 0

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
동전의 갯수 / 가치의 합
10 4200
1
5
10
50
100
500
1000
5000
10000
50000


- 예제 출력 1 -
6

(3) 코드

import sys
from collections import deque

def input():
    return sys.stdin.readline().rstrip()

n, k = map(int, input().split())
temp = deque([])
answer = 0

for _ in range(n):
    v = int(input())
    if v <= k:
        temp.appendleft(v)

for money in temp:

    a = k // money
    k -= (money * a)
    answer += a
    if n == 0:
        break

print(answer)

(4) 정리

처음부터 k의 값보다 큰 동전의 가치를 지닌것은 temp 에 추가하지 않았다.
또한 가치가 큰 동전부터 나열하는 식으로 추가해서 좀 더 for문을 쉽게 돌릴 수 있도록 하였다.

(5) 참고

9461_파도반 수열 (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9461번: 파도반 수열

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> DP
>> dp[i] = dp[i-2] + dp[i-3]

dp[1] = 1
dp[2] = 1
dp[3] = 1

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(101)]

    # fixme - 2. 초깃값 삽입
    dp[1] = 1
    dp[2] = 1
    dp[3] = 1

    # fixme - 3. 테이블 채우기
    for i in range(4, n+1):
        dp[i] = dp[i] = dp[i-2] + dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

문제를 완전히 이해하지 않아도 숫자 규칙을 찾으면 DP 문제임을 알고 쉽게 풀 수 있는 문제였다.

(5) 참고

[문제번호]_[문제이름] (Python)

0. 출처

• 유형 : DP (silver 3)
• 링크 : 9095번: 1, 2, 3 더하기

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> DP 문제 (tabulation 으로 푼다.)
>> 1. 테이블 정의
dp = [0 for _ in range(11)]

>> 2. 초깃값 삽입
dp[1]+3
dp[2]+2
dp[3]+1


>> 3. 테이블 채우기
dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
3
4
7
10


- 예제 출력 1 -
7
44
274

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def dp_func(n):
    # fixme - 1. 테이블 정의
    dp = [0 for _ in range(11)]     # n은 11보다 작다는 조건이 있음, 테이블 크기를 11만큼 해주자

    # fixme - 2. 초깃값 삽입
    dp[0] = 0
    dp[1] = 1
    dp[2] = 2
    dp[3] = 4
    dp[4] = 7

    # fixme - 3. 테이블 채우기
    for i in range(5, n+1):
        dp[i] = dp[i-1]+dp[i-2]+dp[i-3]

    print(dp[n])

for _ in range(t):
    n = int(input())
    dp_func(n)

(4) 정리

DP 문제 풀면 짜릿하다.

(5) 참고

9375_패션왕 신해빈 (Python)

0. 출처

• 유형 : 해시 (silver 3)
• 링크 : 9375번: 패션왕 신해빈

1. 기록

• 22/06/30 (목)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
{
    'headgear':['hat','turban'],
    'eyewear':['sungalsses']
}

2. 시간복잡도
>>

3. 자료구조
>> 해시

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
테스트 케이스 / 해빈이가 가진 의상의 수
2
3
hat headgear
sunglasses eyewear
turban headgear
3
mask face
sunglasses face
makeup face

- 예제 출력 1 -
5
3

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

t = int(input())

def OOTD(n):
    temp = {}

    for _ in range(n):
        wear, type = input().split()
        if type in temp:
            temp[type].append(wear)
        elif type not in temp:
            temp[type] = [wear]

    answer = 1

    for key in temp:
        answer *= (len(temp[key])+1)

    print(answer-1)

for _ in range(t):
    n = int(input())
    OOTD(n)

(4) 정리

(5) 참고

TEST

20056_마법사 상어와 파이어볼 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 4)
• 링크 : 20056번: 마법사 상어와 파이어볼

1. 기록

• 22/04/24 (일)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
sample

- 예제 출력 1 -
sample

(3) 코드

from copy import deepcopy

n, m, k = map(int, input().split())
graph = [[[] for _ in range(n)] for _ in range(n)]

# graph에 상어가 있는 경우 [m, s, d] 로 저장하기
for _ in range(m):
    r, c, m, s, d = map(int, input().split())
    if m != 0:
        graph[r - 1][c - 1].append([m, s, d])

dirs = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]]

for _ in range(k):
    n_graph = [[[] for _ in range(n)] for _ in range(n)]

    # 1. 모든 파이어볼이 이동한다.
    for x in range(n):
        for y in range(n):
            if graph[x][y] != []:
                for b in range(len(graph[x][y])):
                    nm, ns, nd = graph[x][y][b]
                    nx = x + dirs[nd][0] * ns
                    ny = y + dirs[nd][1] * ns

                    nx = (nx + n) % n
                    ny = (ny + n) % n

                    n_graph[nx][ny].append([nm, ns, nd])

    # 2. 2개 이상의 파이어볼이 있는 칸을 찾아 4개의 파이어볼을 만든다.
    for x2 in range(n):
        for y2 in range(n):
            if len(n_graph[x2][y2]) > 1:
                cm, cs, cd = 0, 0, []
                cnt = len(n_graph[x2][y2])

                for c in range(cnt):
                    cm += n_graph[x2][y2][c][0]
                    cs += n_graph[x2][y2][c][1]
                    cd.append(n_graph[x2][y2][c][2] % 2)
                cm = int(cm / 5)
                cs = int(cs / cnt)
                n_graph[x2][y2] = []

                if cm != 0:  # 질량이 0 인 경우 소멸하는 조건 고려
                    if sum(cd) == 0 or sum(cd) == cnt:  # 합쳐지는 파이어볼 방향이 모두 홀수거나 짝수인 경우
                        for i in range(4):
                            n_graph[x2][y2].append([cm, cs, i * 2])
                    else:
                        for j in range(4):
                            n_graph[x2][y2].append([cm, cs, j * 2 + 1])

    graph = deepcopy(n_graph)

# 남아있는 파이어볼 질량의 합 구하기
sum_m = 0
for x in range(n):
    for y in range(n):
        if graph[x][y] != []:
            for b in range(len(graph[x][y])):
                sum_m += graph[x][y][b][0]
print(sum_m)

(4) 정리

내가 놓친 부분
주어진 파이어볼의 정보를 graph 상에 잘 옮겨 놨으나
파이어 볼 이동을 한개씩을 graph 상에 옮기고 파이어볼을 나누고 옮기고 나누고해서 계속 실패했습니다.
파이어 볼이 이동한 위치, m,s,d 등을 다른 3차원 배열상에 전체를 옮겨놓은 뒤에
파이어 볼을 전체를 4방향으로 나누는 과정을 진행해야 합니다.
따라서 이러한 문제에서 deepcopy 등이 자주 사용됨을 기억하면 좋을 것 같습니다.★

(5) 참고

가장 이해가 잘된 풀이

20057_마법사 상어와 토네이도 (Python)

0. 출처

• 유형 : 시뮬레이션, 삼성 (gold 3)
• 링크 : 20057번: 마법사 상어와 토네이도

1. 기록

• 22/04/23 (토)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 토네이도가 격자의 가운데 부터 시전한다. n 이 홀수여야 함
>> 토네이도의 회전 모양을 코드로 어떻게 표현할 것인가? 규칙성을 찾자
>> n = 5 인 경우
>> 1칸 2번, 2칸 2번, 3칸 2번, 4칸 2번, 5칸 1번 (마지막의 경우 범위를 벗어나면 종료되도록 한다.)

>> 퍼지는 값
>> dx = [-1, 1, -2, 2, 0, -1, 1, -1, 1]
>> dy = [1, 1, 0, 0, -2, 0, 0, -1, -1]

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
5
0 0 0 0 0
0 0 0 0 0
0 10 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 1 -
10

- 예제 입력 2 -
5
0 0 0 0 0
0 0 0 0 0
0 100 0 0 0
0 0 0 0 0
0 0 0 0 0

- 예제 출력 2 -
85

- 예제 입력 3 -
7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 0 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7
1 2 3 4 5 6 7

- 예제 출력 3 -
139

(3) 코드

# 모래 계산하는 함수
def recount(block, dx, dy, direction):
    global ans, s_x, s_y

    # y좌표 계산 & x좌표 갱신
    for _ in range(block):
        s_x += dx
        s_y += dy
        if s_y < 0:  # 범위 밖이면 stop
            break

        # 3. a, out_sand
        total = 0  # a 구하기 위한 변수

        for dx, dy, z in direction:
            nx = s_x + dx
            ny = s_y + dy

            # 원래모래에서 - 퍼진모래 = 이동한 방향에 남은 모래
            if z == 0:
                new_sand = sand[s_x][s_y] - total

            # 퍼지는 모래양에 모래비율을 곱해준다. 
            elif z != 0:
                new_sand = int(sand[s_x][s_y] * z)
                total += new_sand

            if 0 <= nx < N and 0 <= ny < N:   # 인덱스 범위이면 값 갱신
                sand[nx][ny] += new_sand
            elif not(0 <= nx < N and 0 <= ny < N):  # 범위 밖이면 ans 카운트
                ans += new_sand


N = int(input())
sand = [list(map(int, input().split())) for _ in range(N)]

# 2. 방향별 모래 비율 위치
left = [(1, 1, 0.01), (-1, 1, 0.01), (1, 0, 0.07), (-1, 0, 0.07), (1, -1, 0.1),
         (-1, -1, 0.1), (2, 0, 0.02), (-2, 0, 0.02), (0, -2, 0.05), (0, -1, 0)]
right = [(x, -y, z) for x, y, z in left]
down = [(-y, x, z) for x, y, z in left]
up = [(y, x, z) for x, y, z in left]

s_x, s_y = N//2, N//2  # 시작좌표(x좌표)
ans = 0  # out_sand

# 1. 이동하는 칸 수
for block in range(1, N + 1):
    # 움직이는 칸 수가 홀수인 경우
    if block % 2 == 1:
        recount(block, 0, -1, left)
        recount(block, 1, 0, down)

    # 움직이는 칸 수가 짝수인 경우
    elif block % 2 == 0:
        recount(block, 0, 1, right)
        recount(block, -1, 0, up)

print(ans)

(4) 정리

토네이도의 회전방향을 계속 고려해줘야 한다는 점

토네이도 이동방향에 따른 모래가 퍼지는 방향이 다르다는 점

위 두가지가 생각보다 까다로워서 풀이를 찾아봤습니다.

또한 토네이도 이동방향에 따라 모래가 퍼지는 방향을 하드코딩하는 방법 말고는 시간 내에 떠올리지 못했을거 같습니다.

(5) 참고

참고 풀이