https://school.programmers.co.kr/learn/courses/30/lessons/67258

문제

풀이

def solution(gems):
    gem_types = len(set(gems))  # 보석 종류의 개수
    gem_dict = {}  # 현재 구간에 포함된 보석의 개수를 기록할 딕셔너리
    answer = [0, len(gems) - 1]  # 최소 구간의 시작과 끝 인덱스 저장
    left = 0  # 윈도우의 왼쪽 포인터
    min_len = len(gems)  # 최소 구간 길이

    for right in range(len(gems)):  # 윈도우의 오른쪽 포인터 이동
        gem = gems[right]
        if gem in gem_dict:
            gem_dict[gem] += 1
        else:
            gem_dict[gem] = 1

        # 현재 구간에 모든 보석이 포함될 때까지 윈도우의 왼쪽 포인터 이동
        while len(gem_dict) == gem_types:
            # 현재 구간의 길이가 더 짧으면 갱신
            if right - left < min_len:
                min_len = right - left
                answer = [left + 1, right + 1]  # 인덱스는 1부터 시작이므로 +1

            # 왼쪽 포인터 이동
            gem_dict[gems[left]] -= 1
            if gem_dict[gems[left]] == 0:
                del gem_dict[gems[left]]
            left += 1

    return answer

📌 보충설명

예시 ["DIA", "RUBY", "RUBY", "DIA", "DIA", "EMERALD", "SAPPHIRE", "DIA"]를 가지고 코드를 살펴보자.

일단 left, right 둘 다 0 에서 시작.

for right in range(len(gems)):  # 윈도우의 오른쪽 포인터 이동
        gem = gems[right]
        if gem in gem_dict:
            gem_dict[gem] += 1
        else:
            gem_dict[gem] = 1

모든 보석들을 포함할 때까지 right을 옮긴다. 즉 여기서는 맨 마지막에 있는 다이아 이전, 7번을 가르키게 된다. 그러면 answer 는 아직 [1, 7] 이 된다.

 # 현재 구간에 모든 보석이 포함될 때까지 윈도우의 왼쪽 포인터 이동
    while len(gem_dict) == gem_types:
        # 현재 구간의 길이가 더 짧으면 갱신
        if right - left < min_len:
            min_len = right - left
            answer = [left + 1, right + 1]  # 인덱스는 1부터 시작이므로 +1

        # 왼쪽 포인터 이동 (구간 축소)
        gem_dict[gems[left]] -= 1
        if gem_dict[gems[left]] == 0:
            del gem_dict[gems[left]]
        left += 1

그 후, while len(gem_dict) == gem_types: 이게 진짜 생각하기 어려운데, 모든 보석을 포함한다면 계속해서 left 포인터를 통해 범위를 줄여나간다.

왼쪽 보석 gems[left]는 dia 가 되고, dia 는 지금 3개였는데 2개로 줄인다. 구간에 여전히 4가지 보석이 포함되어 있으므로 left 포인터를 한 칸 더 이동한다. 그 다음 gems[left] 는 ruby 가 된다. 이거도 2개에서 1로 줄인다. 그러면 answer 가 우선 [3,7]이 된다. 그 다음 gems[left]는 ruby이다. gem_dict 에서 루비의 개수가 0 이 되어 루비가 사라진다. 그럼 while 문에서 나오게 된다.

마지막으로 right 이 7 이 되고, 여덟 번째 보석을 확인하는데 dia 이다. 여전히 루비가 없기에 while 문이 실행되지 않고 끝이 난다.

따라서 정답은 [3,7] 이 된다.

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

문제

풀이

#1 내 첫 풀이는 n개씩 +와 -를 리스트에 넣고, itertools.permutations한 후 set 을 써서 모든 결과값을 도출하는 것이었다. -> 당연한 시간 초과

#2 dfs / bfs 를 이용해보기로 한다.

def solution(numbers, target):
  leaves = [0]          # 모든 계산 결과를 담자      
  count = 0 

  for num in numbers : 
    temp = []

    # 자손 노드 
    for leaf in leaves : 
      temp.append(leaf + num)    # 더하는 경우 
      temp.append(leaf - num)    # 빼는 경우 

    leaves = temp 

  # 모든 경우의 수 계산 후 target과 같은지 확인 
  for leaf in leaves : 
    if leaf == target : 
      count += 1

  return count

일단 나는 이 코드를 보고, leaves = temp 를 생각하지 못했다. 모든 계산 결과를 담는 리스트가 있어야하고, 더하는 경우, 빼는 경우를 다 리스트에 넣는 거 까진 했는데, 이후에서 막혀서 답지를 봤다. 그랬더니 천재적으로 leaves = temp 로 업데이트 시켜주면서 leaves 안에는 모든 계산 결과만 끝에 남게끔 짰더라... 세상은 넓고 천재는 많다.

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

문제

풀이

유튜브: 알고리즘 코딩테스트 문제풀이 강의 - 12 오큰수 구하기 (백준 17298)

import sys
n = int(input())
A = list(map(int, sys.stdin.readline().split()))
answer = [-1] * n
stack = []

for i in range(n):
    while stack and A[stack[-1]] < A[i]:
        answer[stack.pop()] = A[i]
    stack.append(i)


print(*answer)

📌 주의

수열의 값이 아닌 인덱스를 저장하는 것. 진짜 색다른 풀이법이다.

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

문제

풀이

# n은 다리를 건너는 트럭의 수, w는 다리의 길이, 그리고 L은 다리의 최대하중
from collections import deque 
n,w,l = map(int, input().split())
trucks = list(map(int, input().split()))
trucks = deque(trucks)
bridge = deque([0] * w)

total_weight = 0
second = 0

while bridge:
    second += 1
    # 왼쪽에서 다리를 다 통과한 트럭의 무게를 뺴준다
    exited_truck = bridge.popleft() 
    total_weight -= exited_truck

    # 대기 중인 트럭이 존재할 때
    if trucks:
        if total_weight + trucks[0] <= l:
            started_truck = trucks.popleft()
            total_weight += started_truck
            bridge.append(started_truck)

        else:
            bridge.append(0)

print(second)

📌 주의

일단 bridge 의 길이로 while 문을 돌리는 발상이 어렵다. bridge 길이만큼 0을 초기설정으로 두었다면, 이미 반은 성공한 것.

그 다음에 if trucks 적는 것을 까먹게 된다. 대기 중인 트럭이 없는데 계속 확인을 하게 된다면, 무한루프에 갇혀버릴 것이다.

마지막으로 deque 와 total_weight 를 이용하면 시간 절약에 도움이 된다. 프로그래머스에서는 total_weight 대신 계속 sum(bridge) 해서 풀었는데 시간 초과 에러가 뜨더라.

https://school.programmers.co.kr/learn/courses/30/lessons/43105

문제

풀이

def solution(triangle):
    # 최대 높이 500
    array = [0] * 500
    n = len(triangle) 

    # 역삼각형 생성 
    triangle = sorted(triangle, key=lambda x: -len(x))

    for i in range(0, n):
        # 한 줄 
        temp = triangle[i]
        for j in range(0, len(temp)):
            array[j] = max(array[j], array[j+1]) + temp[j]

    return array[0]

📌 주의

피보나치 같이 생겼지만 피보나치 보다 어려운 문제. 바텀업으로 풀꺼면 진짜 헷갈리니까 시간 소요는 되더라도 역삼각형으로 만들고 푸는 걸 추천.

https://school.programmers.co.kr/learn/courses/30/lessons/42746

문제

풀이

def solution(numbers):
    answer = ''

    numbers = list(map(str, numbers))

    numbers.sort(key = lambda x : x*3,reverse=True) # 3번씩 반복하면 붙였을때 큰수 찾기 가능

    for i in numbers:
        answer += i

    return str(int(answer))

📌 주의

1. 숫자 리스트를 문자열 리스트로 변환한다.
2. 각 문자열을 3번 반복하여 문자열 비교를 통해 각 숫자가 어떻게 붙을 때 가장 큰 수를 만들 수 있는지 판단하여 내림차순으로 정렬한다.
3. 정렬된 숫자들을 차례로 붙여서 가장 큰 숫자를 만든다.
4. 만들어진 숫자가 000 같은 경우일 때를 대비하여 숫자로 변환 후 다시 문자열로 변환한다.

https://school.programmers.co.kr/learn/courses/30/lessons/64064

문제

풀이

from itertools import permutations

def solution(user_id, banned_id):
    count = len(banned_id)
    combinations = permutations(user_id, count)
    answer = set()

    # 각 조합에 대해 확인 
    for com in combinations:
        found = True

        # banned_id와 비교하기 위한 index 설정
        for idx in range(count):
            cid = com[idx]
            bid = banned_id[idx]

            # 길이가 다르면 바로 제외
            if len(cid) != len(bid):
                found = False
                break

            # 한 글자씩 비교
            for i in range(len(cid)):
                if bid[i] == '*':
                    continue
                if bid[i] != cid[i]:
                    found = False
                    break

            if not found:
                break

        if found:
            answer.add(tuple(sorted(com)))

    return len(answer)

📌 주의

user_id의 배열의 크기는 1이상 8이하라고 명시되어 있으므로 그냥 permutations 을 썼다. for idx in range(count): 를 할 생각을 못해서 시간이 오래걸렸다.

https://school.programmers.co.kr/learn/courses/30/lessons/68936#

문제

0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.

1. 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2. 만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
3. 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다. arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

풀이

def conquer(temp):
    one = any(1 in row for row in temp)
    zero = any(0 in row for row in temp)

    if one == False:
        return 0  # 모두 0으로 이루어짐
    elif zero == False:
        return 1  # 모두 1로 이루어짐
    else: 
        return 2  # 0과 1이 섞여 있음

def divide(arr):
    width = len(arr) // 2
    height = len(arr) // 2

    # 배열을 4개로 나누기
    temp1 = [row[:width] for row in arr[:height]]  # 왼쪽 위
    temp2 = [row[width:] for row in arr[:height]]  # 오른쪽 위
    temp3 = [row[:width] for row in arr[height:]]  # 왼쪽 아래
    temp4 = [row[width:] for row in arr[height:]]  # 오른쪽 아래

    # 각 부분을 정복
    result1 = conquer(temp1)
    result2 = conquer(temp2)
    result3 = conquer(temp3)
    result4 = conquer(temp4)

    # 각각의 부분 결과를 합산
    answer0, answer1 = 0, 0

    if result1 == 1:
        answer1 += 1
    elif result1 == 0:
        answer0 += 1
    else:
        temp_answer0, temp_answer1 = divide(temp1)
        answer0 += temp_answer0
        answer1 += temp_answer1

    if result2 == 1:
        answer1 += 1
    elif result2 == 0:
        answer0 += 1
    else:
        temp_answer0, temp_answer1 = divide(temp2)
        answer0 += temp_answer0
        answer1 += temp_answer1

    if result3 == 1:
        answer1 += 1
    elif result3 == 0:
        answer0 += 1
    else:
        temp_answer0, temp_answer1 = divide(temp3)
        answer0 += temp_answer0
        answer1 += temp_answer1

    if result4 == 1:
        answer1 += 1
    elif result4 == 0:
        answer0 += 1
    else:
        temp_answer0, temp_answer1 = divide(temp4)
        answer0 += temp_answer0
        answer1 += temp_answer1

    return answer0, answer1

def solution(arr):
    one = any(1 in row for row in arr)
    zero = any(0 in row for row in arr)

    # 초기 정답
    answer0, answer1 = 0, 0

    if one == False:
        # 모든 값이 0인 경우
        return [1, 0]
    elif zero == False:
        # 모든 값이 1인 경우
        return [0, 1]
    else: 
        # 배열을 분할해서 탐색
        answer0, answer1 = divide(arr)

    return [answer0, answer1]

📌 주의

else: temp_answer0, temp_answer1 = divide(temp1) answer0 += temp_answer0 answer1 += temp_answer1

만일 네모 안에 0 과 1 이 섞여있다면 2를 반환하고 else 문으로 갈텐데, 그러면 그 네모를 다시 4등분할 수 있는 지 확인하기 위해 재귀적으로 부른다. 반환되는 값 temp_answer0는 temp1에서 발견된 0의 개수이고, temp_answer1는 temp1에서 발견된 1의 개수가 된다. 이 값을 누적해서 더해주면 최종적으로 0과 1의 개수를 알 수 있다. 처음에 나는 else: return 을 해버려서 함수가 끝까지 확인하지 않는 그런 코드를 작성해버렸다. 재귀는 어렵다.

그리고 10번 테스트 케이스에서 틀렸었는데 (과거에) [[1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1], [1, 1, 1, 1]] 가 테스트 케이스였다. 따라서 모든 값이 1인 경우엔 하나의 1만 남아서 모든 값이 0 일 경우 혹은 1일 경우를 따로 빼주었다.

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

문제

풀이

n, l = map(int, input().split())
from collections import deque

# l의 길이가 n보다 작거나 같을 때까지만 탐색
for length in range(l, 101):  # 최대 길이는 100으로 설정 (제약 조건이 있을 수 있음)
    # 연속된 숫자의 시작값을 구함 (n에서 l개의 숫자의 합이 되도록)
    start = (n - (length * (length - 1)) // 2) / length

    # 시작값이 자연수가 아니면 건너뜀
    if start < 0 or start != int(start):
        continue

    # 시작값이 0 이상이고 자연수일 때만 처리
    start = int(start)
    answer = [start + i for i in range(length)]

    # 조건에 맞는 경우를 찾으면 출력하고 종료
    if sum(answer) == n:
        print(*answer)
        exit()

# 만약 조건에 맞는 경우가 없으면 -1 출력
print(-1)

📌 주의

나는 이 문제를 start 를 구할 생각을 못해서 틀렸다. 나는 그냥 start 를 n//l로 하고 슬라이딩 윈도우 기법을 사용하려 했는데 더 똑똑한 방법이 있었다. 예를 들면, n = 18 l = 4 일 때, 합은 start + start+1 + start+2 + ... 가 된다. 즉 합 = 4 x start + (0+1+2+3)

그래서 start = (n - (length * (length - 1)) // 2) / length 이렇게 된다.

https://school.programmers.co.kr/learn/courses/30/lessons/42839

문제

풀이

from itertools import permutations
import math

def is_prime(num):
    # 2보다 작은 숫자는 소수가 아님
    if num < 2:
        return False

    # 2부터 √num까지 나누어떨어지는지 확인
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0

    # 조합 생성 
    numbers_list = list(numbers)
    numbers_set = set()

    # 숫자의 자리수 만큼
    for i in range(1, len(numbers_list) + 1):
        temp = permutations(numbers_list, i)
        for j in temp:
            result = int(''.join(j))
            numbers_set.add(result)  # 중복 방지를 위해 set에 바로 추가

    # 소수 판별
    for num in numbers_set:
        if is_prime(num):
            answer += 1

    return answer

📌 주의

• for 문이 너무 많으니 소수 판별 함수를 따로 만드는 것을 추천.
• set 은 append 가 아닌 add 와 Update 를 쓴다. 까먹지 말자.

문제

풀이

나는 false, true 에 꽂혀서, 어차피 false 에다 true 를 곱하면 false 인데, 대강 그렇게 풀면 되지 않을까라고 생각했다. 그래서 일단 1 빼고 다 false 로 만든 후, 하나씩 true로 바꿔서 answer 에 넣는 방식으로 풀었다.

2로 나누어떨어지고 dp[i//2]가 참일 때, 아니면 3으로 나누어떨어지고 dp[i//3]이 참일 때, 아니면 5로 나누어떨어지고 dp[i//5]가 참일 때.

그러면 어떤 식으로 동작하냐면 i = 2 i % 2 == 0, i // 2 = 1 (True)

i = 3 i % 3 == 0, i // 3 = 1 (True)

i = 4 i % 2 == 0, i // 2 = 2 -> dp[2] = True

이런 식으로 계속해서 가장 최근 숫자를 의존해서 풀어나간다.

n = int(input())
dp = [False] * (1001)  # 충분히 큰 범위로 dp 리스트 생성
dp[1] = True  # 1은 기본적으로 못생긴 수
answer = [1]  # 못생긴 수 리스트, 1은 기본값으로 포함

for i in range(2, 1001):
    if len(answer) == n:  # n번째 못생긴 수를 찾으면 종료
        break

    # 2, 3, 5로 나누어떨어지는 경우만 True로 설정
    if i % 2 == 0 and dp[i // 2]:
        dp[i] = True
    elif i % 3 == 0 and dp[i // 3]:
        dp[i] = True
    elif i % 5 == 0 and dp[i // 5]:
        dp[i] = True

    if dp[i]:  # 못생긴 수일 경우 리스트에 추가
        answer.append(i)

print(answer[-1])  # n번째 못생긴 수 출력

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

문제

풀이

n = int(input())

t = []  # 각 상담에 걸리는 시간
p = []  # 각 상담의 이익

# 상담 정보 입력
for _ in range(n):
    t1, p1 = map(int, input().split())
    t.append(t1)
    p.append(p1)

# DP 테이블 초기화
dp = [0] * (n + 1)

# DP 계산
for i in range(n):
    # 먼저 상담을 선택하지 않을 경우 (이전까지의 최대 이익을 그대로 넘김)
    dp[i + 1] = max(dp[i + 1], dp[i])

    # 상담이 끝나는 날짜가 퇴사일을 넘지 않는 경우에만 상담을 선택
    if i + t[i] <= n:
        dp[i + t[i]] = max(dp[i + t[i]], dp[i] + p[i])

# 최종적으로 얻을 수 있는 최대 이익 출력
print(dp[n])

n = 7 t = [3, 5, 1, 1, 2, 4, 2] p = [10, 20, 10, 20, 15, 40, 200] 이라 하고 코드가 어떻게 동작하는 지 알아보자.

첫 번째 상담: 3일 동안 이익 10 dp = [0, 0, 0, 10, 0, 0, 0, 0]

두 번째 상담: 5일 동안 이익 20 dp = [0, 0, 0, 10, 0, 20, 0, 0]

세 번째 상담: 1일 동안 이익 10 dp[4] = dp[3] + 10 → dp[4] = 20 dp = [0, 0, 0, 10, 20, 20, 0, 0]

네 번째 상담: 1일 동안 이익 20 dp[5] = dp[4] + 20 → dp[5] = 40 dp = [0, 0, 0, 10, 20, 40, 0, 0]

다섯 번째 상담: 2일 동안 이익 15 dp = [0, 0, 0, 10, 20, 40, 0, 55]

여섯 번째와 일곱 번째는 퇴사일까지 끝낼 수 없어 선택할 수 없다.

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

문제

풀이

예시) 동전 종류: 1,2,5 목표 금액: 10

금액 10을 주어진 동전 종류로 만들 수 있는 방법:

• 1을 10번 사용하기
• 2를 5번 사용하기
• 5를 2번 사용하기
• 2를 1번 사용하고, 1 을 8번 사용하기... 등 총 10가지 방법이 있다.

dp[i] 는 금액 i를 만들 수 있는 경우의 수를 의미한다. dp[0] = 1이 된다. 왜냐하면 0원을 만드는 방법은 동전을 사용하지 않는 1가지 방법 밖에 없기 때문이다.

그렇다면 동전 종류를 업데이트 해보자. 동전 1만 주어졌을 때, dp[1] += dp[1 - 1] -> dp[1] = 1 dp[2] += dp[2 - 1] -> dp[2] = 1 dp[3] += dp[3 - 1] -> dp[3] = 1 dp[4] += dp[4 - 1] -> dp[4] = 1 ... dp[10] += dp[10 - 1] -> dp[10] = 1 어떤 금액이든 1가지 밖에 없다.

그렇다면 동전 2도 주어지면 어떻게 될까? dp[2] += dp[2 - 2] -> dp[2] = 2 dp[3] += dp[3 - 2] -> dp[3] = 2 dp[4] += dp[4 - 2] -> dp[4] = 3 dp[5] += dp[5 - 2] -> dp[5] = 3 1원 5개, 2원 2개와 1원 1개, 2원 1개와 1원 3개 ... dp[10] += dp[10 - 2] -> dp[10] = 6

핵심은 dp[i] 는 금액 i를 만들 수 있는 모든 방법의 경우의 수이고, dp[i] 는 dp[i - 동전의 가치]를 통해 현재 동전을 사용하는 경우의 수를 추가하는 것이다.

import sys
input = sys.stdin.readline
n, k = map(int, input().split())
coins = [int(input()) for _ in range(n)]

# DP 테이블 초기화
dp = [0] * (k + 1)
dp[0] = 1  # 0원을 만드는 방법은 1가지 (아무 동전도 사용하지 않는 경우)

# 동전 순회
for coin in coins:
    for i in range(coin, k + 1):
        dp[i] += dp[i - coin]

# 결과 출력
print(dp[k])

📌 주의

동전의 순서는 고려하지 않으므로, 각 동전으로 만들 수 있는 모든 금액을 DP 테이블에 누적한다. 각 동전에 대해 목표 금액 k까지 순회하므로, 시간 복잡도는 O(n * k)가 된다.

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

문제

풀이

피보나치는 크게 3가지 방법으로 풀 수 있다.

1. 재귀 가장 흔히 알려진 방법이다.

   def recursive(i):
    if i == 1 or i == 2:
        return 1
    else: 
        return recursive(i-1) + recursive(i-2)
   

a = recursive(10) print(a)

1 1 2 3 5 8 13 21 34 55 89
an = a(n-1) + a (n-2)의 점화식을 갖는다. 

하지만 이렇게 되면 똑같은 수를 여러 번 계산하게 되어 효율성이 떨어진다.
그렇다면 이미 계산한 수를 저장하면 된다!


2. **탑다운 방식** 

```python
d = [0] * 101  # 피보나치 수열 값을 저장하는 배열, 인덱스를 맞추기 위해 101로 설정

def fibo(x):
    if x == 1 or x == 2:
        return 1

    if d[x] != 0:
        return d[x]

    d[x] = fibo(x-1) + fibo(x-2)  # 메모이제이션을 통해 값을 저장
    return d[x]

print(fibo(10))  # fibo(10)의 결과를 출력

3. 다이나믹 프로그래밍 방식 (보텀업)

   n = int(input())
   

data = [0] * 46

data[1] = 1 data[2] = 1

for i in range(3, n+1): data[i] = data[i-1] + data[i-2]

print(data[n])

```

📌 주의

점화식을 생각하는 것이 DP의 핵심 방법 같다.

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

문제

풀이

n = int(input())
k = int(input())
apple = []
for _ in range(k):
    apple.append(list(map(int, input().split())))

map = [[0] * n for _ in range(n)]
for row, col in apple:
    map[row-1][col-1] = 1


# 뱀의 방향 변환 횟수 
l = int(input())

direction = []
time = []
for _ in range(l):
    a,b = input().split()
    time.append(int(a))
    direction.append(b)

row, col = 0, 0
second = 0
snake = [(row, col)]
current_direction = 0  # 0: 동, 1: 남, 2: 서, 3: 북

# 동, 남, 서, 북 이동 방향 설정
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]


while True:
    # 다음 위치로 이동
    row += dr[current_direction]
    col += dc[current_direction]
    second += 1

    # 벽에 부딪히거나, 자기 자신의 몸에 부딪히면 게임 종료
    if not (0 <= row < n and 0 <= col < n) or (row, col) in snake:
        break

    # 사과가 있는 경우
    if map[row][col] == 1:
        map[row][col] = 0  # 사과 먹기
    else:
        snake.pop(0)  # 꼬리 이동        

    # 뱀의 새로운 머리 추가
    snake.append((row, col))

    # 방향 변환 시간에 도달했을 경우
    if time and second == time[0]:
        if direction[0] == 'L':  # 왼쪽 회전
            current_direction = (current_direction - 1) % 4
        elif direction[0] == 'D':  # 오른쪽 회전
            current_direction = (current_direction + 1) % 4
        time.pop(0)
        direction.pop(0)

print(second)

📌 주의

• 무조건 뱀의 새로운 머리를 추가하고, 사과가 없을 경우 꼬리를 제거한다.
• 이 문제에서 내가 생각하는 핵심은 방향이동이다. # 0: 동, 1: 남, 2: 서, 3: 북 으로 두고,

  dr = [0, 1, 0, -1] # 행의 변화
  dc = [1, 0, -1, 0] # 열의 변화
  

동쪽 (current_direction = 0): dr[0] = 0 (행은 변화하지 않음) dc[0] = 1 (열이 1 증가, 즉 오른쪽으로 이동)

남쪽 (current_direction = 1): dr[1] = 1 (행이 1 증가, 즉 아래쪽으로 이동) dc[1] = 0 (열은 변화하지 않음)

서쪽 (current_direction = 2): dr[2] = 0 (행은 변화하지 않음) dc[2] = -1 (열이 1 감소, 즉 왼쪽으로 이동)

북쪽 (current_direction = 3): dr[3] = -1 (행이 1 감소, 즉 위쪽으로 이동) dc[3] = 0 (열은 변화하지 않음)

그래서 이동을 계산하면
```python
row += dr[current_direction]
col += dc[current_direction]

방향 전환의 경우

if direction[0] == 'L':  # 왼쪽 회전
    current_direction = (current_direction - 1) % 4
elif direction[0] == 'D':  # 오른쪽 회전
    current_direction = (current_direction + 1) % 4

% 4 연산은 방향 값이 0 미만으로 내려가는 것을 방지한다. 예를 들어 0 (동) 에서 90도 왼쪽 회전을 위해 -1 을 하면 -1 이 되어버린다. 하지만 -1 % 4 를 하면 3으로 (북) 올바른 방향으로 변환된다.

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

문제

풀이

인풋받기

import sys
input = sys.stdin.readline
n = int(input())
towers = list(map(int, input().split()))

시간초과를 예상하고도 푼 방법

answer = []
stack = []

for i in range(n):
    if stack == []:
        answer.append(0)

    else:
        if nlist[i] > max(stack):
            answer.append(0)
        else:
            for j in range(len(stack)-1, -1, -1):
                if stack[j] >= nlist[i]:
                    answer.append(j+1)
                    break

    stack.append(nlist[i])

print(*answer)

이 문제는 스택을 이용해야만 시간초과에서 벗어날 수 있다. 그럼 스택을 어떻게 이용할까? 스택의 탑이 현재 탑보다 낮으면 스택에서 제거.

stack = []
answer = [0] * n

for i in range(n):

    while stack:
        if stack[-1][1] > towers[i]:
            answer[i] = stack[-1][0] + 1
            break
        else:
            stack.pop()

    stack.append((i, towers[i]))
print(*answer)

예를 들어보자. [6, 9, 5, 7, 4]

• 탑 1: stack = [(0, 6)], answer = [0, 0, 0, 0, 0]
• 탑 2: stack = [(1, 9)], answer = [0, 0, 0, 0, 0]
• 탑 3: stack = [(1, 9), (2, 5)], answer = [0, 0, 2, 0, 0]
• 탑 4: stack = [(1, 9), (3, 7)], answer = [0, 0, 2, 2, 0]
• 탑 5: stack = [(1, 9), (3, 7), (4, 4)], answer = [0, 0, 2, 2, 4]

그리고 일단 answer에다가 [0,0,0,0,0]을 넣고 시작하는 게 훨씬 편한 것 같다.

📌 주의

스택과 친해지기...

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

문제

풀이

진짜 답지 보기 전까지 이해 못했던 문제. 이게 뭐람 ; 참고한 사이트: https://afterdawncoding.tistory.com/202

• n=1: 방문횟수는 맨 처음 위치 한 개, 1

• n=2: 1칸 위로 2칸 오른쪽 혹은 1칸 아래로 2칸 오른쪽만 가능. 4개의 이동 방법을 다 못쓰기에 최대 4. min(4, (m+1)//2)

• n이 3이상일 때, m에 따라 갈린다.

  • m이 6이하일 때, 4개의 이동 방법을 다 못쓰기에 최대 4. min(4, m)

  • m이 7이상일 때, m-2만큼 가능.

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
if n == 1:
    print(1)
elif n == 2:
    print(min(4, (m+1)//2))
elif m <= 6:
    print(min(4, m))
else:
    print(m-2)

📌 주의

이런 천재적인 아이디어는 누가 어떻게 생각해내는 것일까?

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

문제

풀이

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
nlist = []
for _ in range(n):
    nlist.append(int(input()))

nlist.sort()

start = 1
end = nlist[-1] * m

while start <= end: 
    mid = (start + end) // 2

    count = 0
    for i in nlist:
        if mid >= i:
            count += mid // i

    if count < m: 
        start = mid + 1

    else:
        answer = mid 
        end = mid - 1

print(answer)

📌 주의

첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 숫자보고 이분탐색으로 풀어야겠다라고 생각... 근데 항상 다른 방법이 있을 것이라고 착각하게 되는 문제 중 하나.

• start 는 항상 0 이나 1 에 두기.

• end 는 최악의 경우에다 두기.
• print(mid)를 할 경우, start, mid, end는 이미 값이 변질되어버리기 때문에 answer 를 꼭 사용하기.

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

문제

풀이

투포인터 너무 싫어... 투포인터라고 생각까지는 했다. 근데 생각에 오류가 있었다. 만약에 while temp[nlist[end]] > k: 어떤 숫자의 빈도가 k를 초과하면, start 를 하나 움직이는 것이 아니라 아예 end - 1로 가야한다고 생각했다.

n, k = map(int, input().split())
nlist = list(map(int, input().split()))

start = 0
end = 0
temp = dict.fromkeys(nlist, 0)  # 수열의 각 숫자에 대한 빈도 카운트를 0으로 초기화

max_len = 0

while end < n:
    temp[nlist[end]] += 1  # 현재 end 위치의 숫자의 빈도 증가

    # 만약 어떤 숫자의 빈도가 k를 초과하면, start를 이동시켜야 함
    while temp[nlist[end]] > k:
        temp[nlist[start]] -= 1  # start 위치의 숫자의 빈도 감소
        start += 1  # start를 오른쪽으로 이동

    # 조건을 만족하는 부분 수열의 길이를 계산하여 최대 길이 갱신
    max_len = max(max_len, end - start + 1)

    end += 1  # end를 오른쪽으로 이동

print(max_len)

📌 주의

아직 멀었군 투포인터

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

문제

풀이

괄호를 쳐서 식의 답을 최소로 만드는 것. (- 와 - 사이의 수)를 전부 괄호를 치면 된다. 그래서 나는 직접 괄호를 치려 그랬는데, 한심한 아이디어였고 ; (- 부분)을 스플릿 할 생각을 하지 못했고 ;

n = str(input())
# - 로 split
minus = n.split('-')

plus = []
for i in minus:
    temp = 0
    for j in i.split('+'):
        temp = temp + int(j)
    plus.append(temp)

result = plus[0]
for i in plus[1:]:
    result -= i
print(result)

일단 -로 스플릿을 한다. 55-50+40 이면 [55, 50+40] 을 만든다.

temp 를 0 으로 두고, 또 한 번의 for 문을 이용해서 이번에는 + 로 나눈다. 그 값을 plus 라는 리스트에 넣는다. 그러면, 첫 값을 result 를 넣고, 나머지를 다 빼면 된다.

📌 주의

스플릿을 생각하자.