그냥 코딩하는 사람의 블로그

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

풀이 과정

1. 사용 가능한 로마 숫자가 1, 5, 10, 50이며, N개의 숫자를 모두 사용했을 때 서로 다른 수의 개수를 출력
2. 따라서, 너비우선 탐색을 통해 만들 수 있는 서로 다른 수를 모두 구해준다.
   1. 중복이 있을 수 있으므로 SET 자료구조를 사용한다.
   2. 큐에 있는 각 숫자들을 하나씩 빼면서 1, 5, 10, 50을 더한 값을 중복 제거를 위해 임시로 set에 넣어준다.
   3. 큐가 비게 되면, set에 있는 값들을 큐에 넣어준다.
   4. 2-3 과정을 N번 반복해준 다음 최종적으로 set에 저장된 값의 개수를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
n = int(input())
numbers = [1, 5, 10, 50]

def solve():
    queue = deque([0])
    step = 0
    middle = set()
    answer = set()
    while True:
        x = queue.popleft()
        for num in numbers:
            middle.add(x+num)
        if not queue:
            step += 1
            if step == n:
                answer = middle
                break
            else:
                queue = deque(middle)
                middle = set()

    return len(answer)
    
print(solve())

https://programmers.co.kr/learn/courses/30/lessons/87390

풀이 과정

1. n의 범위가 10의 7승까지이므로 실제로 해보는건 불가능하다.
2. left와 right가 현재 몇행 몇열에 있는지 구한다.
   • 행의 경우 // 연산으로, 열의 경우 % 연산으로 구한다.
3. 문제를 보면, i행의 경우 i열까진 값이 i이고 i+1열부터는 값이 열과 같다.(i+1)
4. 따라서, left의 행,열에서 시작해서 right의 행,열까지 순서대로 이동하면서 값을 넣어주면 된다.
   1. left의 행일때는 left의 열~N열까지 단, left의 행과 right의 행이 같은 경우는 left의 열 ~ right의 열까지
   2. left의 행 + 1 ~ right의 행 - 1 구간에서는 (1~N열)
   3. right의 행에서는 1~right의 열까지
   4. 값을 넣어줄 때는 i행에서 i열까지는 i를 넣어주고, 이후에는 열에 맞추어서 넣어주면 된다.

소스 코드

def solution(n, left, right):
    answer = []
    sr, sc = (left // n)+1, (left % n)+1
    er, ec = (right // n)+1, (right % n)+1
    if sr == er:
        for j in range(sc, ec+1):
            if j <= sr:
                answer.append(sr)
            else:
                answer.append(j)
        return answer
    else:
        for j in range(sc, n+1):
            if j <= sr:
                answer.append(sr)
            else:
                answer.append(j)
                
    for i in range(sr+1, er):
        for j in range(1, n+1):
            if j <= i:
                answer.append(i)
            else:
                answer.append(j)
    
    for j in range(1, ec+1):
        if j <= er:
            answer.append(er)
        else:
            answer.append(j)
            

    return answer

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

풀이 과정

1. & 연산의 경우 두 비트가 모두 1일때만 1, 아닐때는 0으로 설정한다는 점을 이용
2. 따라서, 우선 비트의 개수를 저장해 둘 배열을 만들어 둔다.
   1. array[0] : 0번째 자리에서 비트 1의 개수, ..
3. 각각의 수를 모두 2진수로 바꾼 다음 각 자리를 검사하면서 비트가 1인 경우, 배열의 해당 자리 값을 1 증가시킨다.
4. &연산의 결과가 0이 되지 않으려면, 연산을 하는 값들의 비트중 하나라도 모두 1이 나와야 한다. 따라서 1이 가장 많이 나온 자리를 찾아주어야 하므로, 배열의 최댓값을 구한다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
sequence = list(map(int, input().split()))
bit_count = [0] * 32

def calc_bit(a):
    temp = a
    n = 0
    while temp > 0:
        bit_count[n] += (temp % 2)
        temp = temp // 2
        n += 1

for item in sequence:
    calc_bit(item)

print(max(bit_count))

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

풀이 과정

1. 주어진 문제 (100+1+ | 01)+로 DFA를 구성한다.
   1. 100+1+에서 마지막에 0이 나온 경우, 100+1+로 이동할지 01로 이동할지 알수 없음.
   2. 따라서, 100+1+에서 1과 0을 추가로 만들어 주어서 1->0->0->1->1->0으로 구성
   3. 네번째 1에서 0이 나온 경우는 01로 이동, 여섯번째 0에서 0이 나온 경우는 세번째 0으로 이동하도록 DFA 구성
2. 각각의 테스트 케이스에 대하여 오토마타를 타고 넘어가본다. 이 때, 실패하는 케이스에 대해서는 바로 NO를 출력시켜 주고 다음 테스트 케이스를 진행한다.
3. 최종적으로 종료상태에 들어간 경우에만 YES를 출력해주고, 종료상태에 들어가지 않은 경우 NO를 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

n = int(input())
total_case = list()
for _ in range(n):
    s = input()
    automata = 'S'
    for ch in s:
        if automata == 'S':
            if ch == '1':
                automata = 1
            else:
                automata = 2
                
        elif automata == 1:
            if ch == '1':
                print('NO')
                break
            else:
                automata = 3
                
        elif automata == 2:
            if ch == '1':
                automata = 7
            else:
                print('NO')
                break
            
        elif automata == 3:
            if ch == '0':
                automata = 4
            else:
                print('NO')
                break
            
        elif automata == 4:
            if ch == '0':
                continue
            else:
                automata = 5
                
        elif automata == 5:
            if ch == '0':
                automata = 2
            else:
                automata = 6
                
        elif automata == 6:
            if ch == '0':
                automata = 8
            else:
                continue
            
        elif automata == 7:
            if ch == '0':
                automata = 2
            else:
                automata = 1
                
        elif automata == 8:
            if ch == '0':
                automata = 4
            else:
                automata = 7
    else:
        if automata == 7 or automata == 5 or automata == 6:
            print('YES')
        else:
            print('NO')

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

풀이 과정

1. 전체적인 과정은 Recursion으로 진행한다.
2. 현재 위치에 넴모를 넣을수 있으면 넣어보고, 넣을수 없으면 넣지 않고 다음 위치로 이동한다.
3. 이 때, 넴모를 넣었는지 넣지 않았는지 확인하기 위한 격자판을 미리 만들어두고 넴모를 넣었을때 1, 넣지 않았을때 0으로 설정한다.
4. 현재 위치 기준으로 왼쪽, 왼쪽위, 위에 넴모가 있는지 확인하고, 넴모가 모두 있으면 현재 위치엔 넣을수 없으므로 넣지 않고, 넴모가 한군데라도 없다면 현재 위치에 넣을 수 있으므로 넣는다.
5. 넴모를 넣을때마다 정답을 하나씩 증가시켜서 마지막에 전체 경우의 수를 출력시켜 준다.

쉬운 문제인거 같은데 뭔가 많이 헤맸던것 같다.. 넴모의 위치를 처음에는 Set으로 했었는데.. 계속해서 시간초과에 걸려서 행렬로 바꾸었음, 그래도 시간초과에 걸려서 원래 현재 위치 기준으로 삽입할 수 있는지 체크하는걸 함수로 구현하였었는데, 함수에서 일반 비교식으로 바꾸니 시간 초과가 걸리지 않음.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N, M = map(int, input().split())

block_set = set()
matrix = [[0] * (M+1) for _ in range(N+1)]

def solve(i, j):
    answer = 0
    if j > M:
        i, j = i+1, 1
    if i > N:
        return 0
    
    if matrix[i-1][j] == 0 or matrix[i][j-1] == 0 or matrix[i-1][j-1] == 0:
        matrix[i][j] = 1
        answer += (1 + solve(i, j+1))
        matrix[i][j] = 0
    answer += solve(i, j+1)

    return answer

print(solve(1, 1) + 1)

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

풀이 과정

1. 전반적인 과정은 BFS로 진행
   1. 루트 노드(1)부터 시작한다.
   2. 현재 노드에서 연결된 자식 노드 수만큼 물을 나누어서 배분시켜 준다.
   3. 나누어준 자식 노드로 이동하여서 다음 자식노드에게 물을 나누어준다.
   4. 2-3 과정을 반복한다.
2. 이 때, 자식노드가 존재하여 자식노드에게 물을 나누어준 경우에는 비교를 위해 값을 0으로 설정한다. 소숫점 비교는 잘 되지 않음.
3. BFS가 종료되면, 물의 양의 합계 / 물의 양이 0이 아닌 노드의 갯수 를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()
N, W = map(int, input().split())
t = [[] for _ in range(N+1)]
v = [0] * (N+1)
v[1] = W

for _ in range(N-1):
    a, b = map(int, input().split())
    t[a].append(b)
    t[b].append(a)

visited = set()
visited.add(1)
queue = deque([1])

while queue:
    node = queue.popleft()
    count = 0
    for nx in t[node]:
        if nx not in visited:
            count += 1

    if count == 0:
        continue

    each_value = v[node] / count
    for nx in t[node]:
        if nx not in visited:
            v[nx] = each_value
            visited.add(nx)
            queue.append(nx)
    v[node] = 0

count = 0
for i in range(1, N+1):
    if v[i] != 0:
        count += 1

print(sum(v) / count)

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

풀이 과정

1. 루트 노드가 무조건 1번인건 아니기 때문에 루트 노드의 번호를 구한다.
   1. 1번부터 N번까지 노드를 Set에 저장시켜 둔 다음, 입력되는 노드의 오른쪽 자식이거나 왼쪽 자식인 경우, Set에서 빼준다.
   2. Set에 노드가 한개 남게 되면, 그게 루트 노드이다. 
2. 각각의 노드가 위치하는 열을 구한다. 
   
   1. 그 전에, 각각의 노드의 자식 노드 수를 구해준다.
   2. 현재 노드의 위치는 범위가 (left, right)일 때, left + 왼쪽 자식 노드 수 + 1이라고 볼 수 있다.
   3. 현재 노드의 위치를 구해준 다음, 왼쪽 자식 노드에 대해서는 (left, 현재 노드의 위치 - 1), 오른쪽 자식 노드에 대해서는 (현재 노드의 위치+1, right) 범위만큼 recursion으로 진행한다.
3. 열을 구해준다면, 이제 루트 노드에서 시작해서 BFS를 진행한다.
   1. 각각의 레벨에 열 정보들을 모두 저장시켜 둔다.
4. 저장해둔 레벨별 열 정보들을 오름차순으로 정렬시켜 준다.
   1. 맨 마지막 인덱스가 최댓값, 맨 앞 인덱스가 최솟값이므로 최댓값 - 최솟값을 구해준다.
   2. 최댓값-최솟값이 현재 정답보다 크다면, 현재 정답과 인덱스를 저장시켜 둔다.

소스 코드

import sys
from collections import deque


input = lambda: sys.stdin.readline().rstrip()
N = int(input())
left_child = [-1] * (N+1)
right_child = [-1] * (N+1)
p = set([i for i in range(1, N+1)])

for i in range(N):
    a, b, c = map(int, input().split())
    left_child[a] = b
    right_child[a] = c
    if b in p:
        p.remove(b)
    if c in p:
        p.remove(c)

root_node = list(p)[0]
child_count = [-1] * (N+1)
pos = [0] * (N+1)

def get_chk_child(p):
    count = 0
    if left_child[p] != -1:
        count += get_chk_child(left_child[p])
    if right_child[p] != -1:
        count += get_chk_child(right_child[p])
    child_count[p] = count + 1
    return count + 1

def allow_number(p, left, right):
    pos[p] = left

    if left == right:
        pos[p] = left
        return
    
    if left_child[p] != -1:
        pos[p] = left+child_count[left_child[p]]

    if left_child[p] != -1:
        allow_number(left_child[p], left, pos[p]-1)

    if right_child[p] != -1:
        allow_number(right_child[p], pos[p]+1, right)

get_chk_child(root_node)
allow_number(root_node, 1, N)
step = [[] for _ in range(10001)]
queue = deque([[root_node, 0]])
while queue:
    nx, s = queue.popleft()
    step[s].append(pos[nx])
    if left_child[nx] != -1:
        queue.append([left_child[nx], s+1])
    if right_child[nx] != -1:
        queue.append([right_child[nx], s+1])

level = 1
answer = 1
for i in range(10001):
    step[i].sort()
    if len(step[i]) > 1:
        if answer < step[i][-1] - step[i][0] + 1:
            answer = step[i][-1] - step[i][0] + 1
            level = i+1

print(level, answer)

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

풀이 과정

1. 초기 현재 값과 단계를 큐에 넣은 다음, BFS를 진행한다.
   1. 다음 단계의 값에 일단 i+1을 넣어준다. -> 버튼 A
   2. 버튼 B를 구현할 때, 현재 단계의 값이 0이거나 입력받은 값을 2배한 값이 99999보다 크다면 버튼 B를 누를 수 없는 것이므로 버튼 A를 누른 결과만 진행한다.
   3. 아니라면, 2를 곱한 값의 가장 앞자리의 숫자를 하나 줄여주어야 하므로 1 * 10^(전체 자릿수-1)를 빼준다.
      • 예를 들면, 4자리라면 1000을 빼준다. 
2. 큐가 비게 되거나, 단계가 T를 넘어가게 되면 "ANG"를 출력해 주고, 목표한 값에 도달한다면 현재 단계를 출력시켜 준다.

소스 코드

import sys
from collections import deque

input = lambda: sys.stdin.readline().rstrip()

N, T, G = map(int, input().split())
queue = deque()
queue.append([N, 0])

def get_next_number(i):
    temp = i * 2
    if i == 0 or temp > 99999:
        return [i+1]
    index = 1
    while temp//10 != 0:
        temp //= 10
        index *= 10
    
    return [i+1, i * 2 - index]

visited = set()
visited.add(N)

while queue:
    target, step = queue.popleft()
    if step == T+1:
        print("ANG")
        break
    if target == G:
        print(step)
        break
    for nx in get_next_number(target):
        if nx not in visited:
            queue.append([nx, step+1])
            visited.add(nx)
else:
    print("ANG")

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

풀이 과정

1. 맨 오른쪽에서부터 왼쪽으로 진행하면서 N을 찾는다.
2. N이 아니라면 옮겨야 되는 값이므로 횟수를 하나 증가시킨다.
3. N이라면 찾아야 하는 값을 N-1로 줄여서 현재 위치에서부터 찾는다.
4. 2-3을 맨 왼쪽까지 반복한다.

- 위 과정을 반복하면 찾아야 하는 값 기준으로 왼쪽에서 보았을 때 증가하는 수열이 나온다.(맨 마지막 값이 N)

- 또한, 옮겨야 되는 값들은 큰것부터 작은것 순으로 맞추어서 앞에 넣어주기만 하면 되기 때문에 결국 (2)에서 구한 횟수를 그대로 리턴해주면 된다. 

- 생각보다 잘 안풀리는 문제였음

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()
N = int(input())
books = [int(input()) for _ in range(N)]

find_target = N
answer = 0
for i in range(N-1, -1, -1):
    if books[i] != find_target:
        answer += 1
    else:
        find_target -= 1

print(answer)

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

풀이 과정

1. 파이썬의 슬라이싱 기능을 이용하면 쉽게 풀 수 있는 문제이다.
2. 리스트에 1~10까지 원소를 넣어둔 다음 입력받은 바구니 순서에 맞추어서 슬라이싱 해준다.
   • i, j, k가 입력되면 ~i, j~k까지, i~k까지, j~에 맞추어서 슬라이싱 해준다.
3. 최종 슬라이싱 된 리스트를 출력시켜 준다.

소스 코드

import sys

input = lambda: sys.stdin.readline().rstrip()

N, M = map(int, input().split())
buckets = [i for i in range(1, N+1)]

for _ in range(M):
    i, j, k = map(int, input().split())
    i, j, k = i-1, j-1, k-1
    buckets = buckets[:i] + buckets[k:j+1] + buckets[i:k] + buckets[j+1:]
    
print(*buckets)