15666_N과 M(12)(Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15666번: N과 M(12)

1. 기록

• 22/04/03 (일)

2. 풀이

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

1. 아이디어
>> 주어진 수에 '중복된 숫자가 있을 때' 중복조합을 구하는 문제
>> set 이용 중복된 수를 제거하고 중복조합을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>
'''

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

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 7
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = set(nums)
nums = list(nums)
nums = sorted(nums)

stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_dfs(i)
        stack.pop()

iterative_dfs(0)

(4) 정리

(5) 참고

15665_N과 M(11) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15665번: N과 M(11)

1. 기록

• 22/04/03 (일)

2. 풀이

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

1. 아이디어
>> 주어진 수 중에 중복된 숫자가 있을 때 중복순열을 구하는 문제
>> 주어진 수에서 중복된 숫자를 제거하고(set 이용) 그냥 중복순열을 구한다.

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 1
1 7
1 9
7 1
7 7
7 9
9 1
9 7
9 9

(3) 코드

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

set_nums = set(nums)
list_nums = list(set_nums)
nums = sorted(list_nums)

stack = []

def iterative_bfs():
    if len(stack) == m:
        print(*stack)
        return

    for i in range(0, len(nums)):
        stack.append(nums[i])
        iterative_bfs()
        stack.pop()

iterative_bfs()

(4) 정리

(5) 참고

15664_N과 M(10) (Python)

0. 출처

• 유형 : 백트래킹 (silver 2)
• 링크 : 15664번: N과 M(10)

1. 기록

• 22/04/03 (일)

2. 풀이

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

1. 아이디어
>> 주어진 수 중에서 중복된 수가 있을 때 조합을 구하는 문제

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 9
9 9

(3) 코드

n, m = map(int, input().split())
nums = list(map(int, input().split()))
nums = sorted(nums)

visited = [False] * n
stack = []

def iterative_dfs(start):
    if len(stack) == m:
        print(*stack)
        return

    overlap_check = 0
    for i in range(start, n):
        if not visited[i] and overlap_check != nums[i]:
            visited[i] = True
            overlap_check = nums[i]
            stack.append(nums[i])
            iterative_dfs(i)
            stack.pop()
            visited[i] = False

iterative_dfs(0)

(4) 정리

(5) 참고

참고 풀이

# 아래와 같이 bool타입이 들어있는 리스트에
visited = [False] * n

vistied = False 와 같이 잘못작성해서 발생한 에러입니다.

visited[i] = True
visited[i] = False 등으로 작성해줘야 합니다.

15663_N과 M(9) (Python)

0. 출처

• 유형 : 백트래킹 (sliver 2)
• 링크 : 15663번: N과 M(9)

1. 기록

• 22/04/03 (일)

2. 풀이

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

1. 아이디어
>> 주어진 수 중에서 '중복된 숫자가 있을 때' 순열을 만드는 문제

2. 시간복잡도
>>

3. 자료구조
>>

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

- 예제 입력 1 -
3 1
4 4 2

- 예제 출력 1 -
2
4

- 예제 입력 2 -
4 2
9 7 9 1

- 예제 출력 2 -
1 7
1 9
7 1
7 9
9 1
9 7
9 9

(3) 코드

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

nums.sort()
visited = [False] * n
stack = []

def solve(depth, n, m):
    if depth == m:
        print(' '.join(map(str, stack)))
        return
    overlap = 0
    for i in range(n):
        if not visited[i] and overlap != nums[i]:
            visited[i] = True
            stack.append(nums[i])
            overlap = nums[i]
            solve(depth+1, n, m)
            visited[i] = False
            stack.pop()

solve(0, n, m)

(4) 정리

기존 n과 m 문제를 푼 방식에서 조금 다양한 장치를 더 추가해야 된다.
visited 로 방문해야 될 숫자를 구별하고
overlap 변수로 중복된 수열을 출력하는 것을 방지한다.

# overlap 변수가 없는 경우

# 입력
4 2
9 7 9 1

# 출력
1 7
1 9
1 9
7 1
7 9
7 9
9 1
9 7
9 9
9 1
9 7
9 9

중복된 숫자 9를 구별하지 못한다.

(5) 참고

참고 풀이1
참고 풀이2

15657_N과 M(8) (Python)

0. 출처

• 유형 : 백트래킹 (silver 3)
• 링크 : 15657번: N과 M(8)

1. 기록

• 22/04/03 (일)

2. 풀이

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

1. 아이디어
>> 주어진 수로 중복 조합만들기

2. 시간복잡도
>>

3. 자료구조
>>

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

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

- 예제 출력 1 -
2
4
5

- 예제 입력 2 -
4 2
9 8 7 1

- 예제 출력 2 -
1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

(3) 코드

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

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

stack = []

def iterative_bfs(start):
    if len(stack) == m:
        print(' '.join(map(str, stack)))
        return

    for i in range(start, len(nums)):
        stack.append(nums[i])
        iterative_bfs(i)
        stack.pop()

iterative_bfs(0)

(4) 정리

(5) 참고

파이썬의 pprint

0. 파이썬의 pprint란?

pprint 모듈은 임의의 파이썬 데이터 구조를 인터프리터의 입력으로 사용할 수 있는 형태로 '예쁘게 인쇄'할 수 있는 기능을 제공합니다.
글을 작성하는 이유는 특정 데이터 구조의 길이가 pprint의 기준 이상이 되지 않으면 출력이 print() 와 동일하게 됩니다.
이 경우 마치 pprint가 동작하지 않는 것 처럼 보여 왜 동작하지 않나 하여 직접 디버깅을 해보며 기준을 찾아보았고
또한 pprint는 코딩테스트에서 이차원배열이 사용되는경우가 많아 디버깅시 많이 이용하는 모듈이라 이번 기회에 찾아보게 되었습니다.

1. 예시

(예시1)

# 입력
arr1 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]

#출력
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]

이쁘게 출력 안해주는 모습

(예시2)

# 입력
arr2 = [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16], [17,18,19,20]]

#출력
[[1, 2, 3, 4],
 [5, 6, 7, 8],
 [9, 10, 11, 12],
 [13, 14, 15, 16],
 [17, 18, 19, 20]]

이쁘게 출력 해주는 모습

(예시3)

# 입력
arr3 = [[1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20]]

# 출력
[[1,2,3,4,5,6,7,8,9,10],[11,12,13,14,15,16,17,18,19,20]]

이쁘게 출력 안해주는 모습

(예시4)

# 입력
arr4 = [[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]]

# 출력
[[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]]

이쁘게 출력 해주는 모습

위와 같이 '특정 기준'을 넘어야 이쁘게 출력해줌을 알 수 있습니다.
option으로 해당 기준을 변경할 수 있는 것인지 찾아봤지만 아직찾지못했습니다.
정확한 default 기준이 무엇인지는 찾아봐야 알 것 같습니다.

2. 참고

공식 문서
참고 자료

17144_미세먼지 안녕! (Python)

0. 출처

• 유형 : 구현, 시뮬레이션 (gold 4)
• 링크 : 17144번: 미세먼지 안녕!

1. 기록

• 22/04/02 (토)

2. 풀이

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

1. 아이디어
>> r(행), c(열), t(시간) 입력받고
>> 미세먼지 graph 입력받고
>> 미세먼지 확산 A(r,c)/5
>> 위쪽 공기청정기 위치와 아래쪽 공기청정기 위치를 알아내야 한다.★★
>> 반시계 방향과 시계방향도 코드로 작성해줘야 한다.★★

2. 시간복잡도

3. 자료구조

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

- 예제 입력 1 -
7 8 1
0 0 0 0 0 0 0 9
0 0 0 0 3 0 0 8
-1 0 5 0 0 0 22 0
-1 8 0 0 0 0 0 0
0 0 0 0 0 10 43 0
0 0 5 0 15 0 0 0
0 0 40 0 0 0 20 0

- 예제 출력 1 -
188

(3) 코드

import sys

r, c, t = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(r)]

up = -1
down = -1
# 공기 청정기 위치 찾기
for i in range(r):
    if arr[i][0] == -1:
        up = i
        down = i + 1
        break

# 미세먼지 확산
def spread():
    dx = [-1, 0, 0, 1]
    dy = [0, -1, 1, 0]

    tmp_arr = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            if arr[i][j] != 0 and arr[i][j] != -1:
                tmp = 0
                for k in range(4):
                    nx = dx[k] + i
                    ny = dy[k] + j
                    if 0 <= nx < r and 0 <= ny < c and arr[nx][ny] != -1:
                        tmp_arr[nx][ny] += arr[i][j] // 5
                        tmp += arr[i][j] // 5
                arr[i][j] -= tmp

    for i in range(r):
        for j in range(c):
            arr[i][j] += tmp_arr[i][j]

# 위쪽 공기청정기 작동
def air_up():
    dx = [0, -1, 0, 1]
    dy = [1, 0, -1, 0]
    direct = 0
    temp = 0
    x, y = up, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == up and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], temp = temp, arr[x][y]
        x = nx
        y = ny

# 아래쪽 공기청정기 작동
def air_down():
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    direct = 0
    temp = 0
    x, y = down, 1
    while True:
        nx = x + dx[direct]
        ny = y + dy[direct]
        if x == down and y == 0:
            break
        if nx < 0 or nx >= r or ny < 0 or ny >= c:
            direct += 1
            continue
        arr[x][y], temp = temp, arr[x][y]
        x = nx
        y = ny


for _ in range(t):
    spread()
    air_up()
    air_down()

answer = 0
for i in range(r):
    for j in range(c):
        if arr[i][j] > 0:
            answer += arr[i][j]

print(answer)

(4) 정리

arr[x][y], temp = temp, arr[x][y]

위와 같은 코드로

1. 현재 칸에 있는 값을 temp 변수에 집어넣고
2. 현재 칸 arr[x][y] 에 이전에 있던 칸의 값(temp)을 대입하는 식으로 값의 이동을 구현함을 배웠습니다.

(5) 참고

두 변수의 값 바꾸기 - swap
참고 풀이

입양 시각 구하기(1) (SQL)

0. 출처

• 유형 : SQL, GROUP BY (lv 2)
• 링크 : 입양 시각 구하기(1)

1. 기록

• 22/04/01 (금)

2. 풀이

(1) 아이디어

sample

(2) 코드

SELECT HOUR(DATETIME) AS 'HOUR', COUNT(HOUR(DATETIME)) AS 'COUNT' 
FROM ANIMAL_OUTS 
WHERE HOUR(DATETIME) >= 9 AND HOUR(DATETIME) <= 19 
GROUP BY HOUR(DATETIME) 
ORDER BY HOUR(DATETIME)

(3) 정리

(4) 참고

참고 자료

동명 동물 수 찾기 (SQL)

0. 출처

• 유형 : SQL, GROUP BY (lv 2)
• 링크 : 동명 동물 수 찾기

1. 기록

• 22/04/01 (금)

2. 풀이

(1) 아이디어

sample

(2) 코드

SELECT NAME, COUNT(NAME) AS 'COUNT' 
FROM ANIMAL_INS 
GROUP BY NAME 
HAVING COUNT(NAME) > 1 
ORDER BY NAME

(3) 정리

(4) 참고

참고 자료