# 0: 갈수있는 곳 1: 벽 2: 먹이
# 계속 오른쪽으로만 가는데 벽이 있으면 한칸 아래로 감

maze = []
x, y = 1, 1
for i in range(10):
  maze.append(list(map(int, input().split())))

dx = (0, 1)
dy = (1, 0)
turn_count = 0

# 첫 위치는 방문처리
maze[x][y] = 9

while True:
  # 회전을 두번 했다면 종료
  if turn_count >= 2:
    break
  
  # 이동할 곳이 벽이 아니라면
  if maze[x+dx[turn_count]][y+dy[turn_count]] == 0:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    turn_count = 0
  # 이동할 곳이 벽이라면
  elif maze[x+dx[turn_count]][y+dy[turn_count]] == 1:
    turn_count += 1
  # 그 외의 경우는 먹이를 발견했을 때
  else:
    x = x + dx[turn_count]
    y = y + dy[turn_count]
    maze[x][y] = 9
    break

for i in range(10):
  for j in range(10):
    print(maze[i][j], end=' ')
  print("")

a, b = map(int, input().split())
target = abs(a - b)

# 먼저 10으로 나눠준다
result = target // 10
target = target % 10


if target in [1, 5]: # 1: +1 / 5: +5
  result += 1
elif target in [2, 4, 6, 9]: # 2: +1,+1 / 4: 5,-1 / 6: 5,+1 / 9: +10,-1
  result += 2
elif target in [3, 7, 8]: # 3: +1,+1,+1 / 7: +5,+1,+1 / 8: +10,-1,-1
  result += 3

print(result)

쓸데없이 생각을 너무 복잡하고 길게 하는것 같다. 최적해를 찾기 위해 생각을 단순화 시킬 필요가 있다

고작 이거하나 짜는데 1시간이 걸렸다

t = int(input())
dPrice, tPrice = map(int, input().split())
dCalorie = int(input())

tCalorie = []
for i in range(t):
  tCalorie.append(int(input()))
  
# cpd의 효율을 위해 내림차순 정렬
tCalorie.sort(reverse=True)

totalCalorie = dCalorie
totalPrice = dPrice
cpd = totalCalorie // totalPrice # calorie per dollar

for x in tCalorie:
  # 토핑의 cpd가 전체 cpd보다 높으면 토핑 추가
  if (x // tPrice) > cpd:
    totalCalorie += x
    totalPrice += tPrice
    cpd = totalCalorie // totalPrice
  # 오름차순 정렬이기때문에 한번만 만족하지 못해도 루프 탈출
  else:
    break

print(format(cpd,".0f"))

접근은 거의 다 했는데 누적 평균값을 고려하지 않아서 조금 헤맸음

from sys import stdin

period, r = map(int, stdin.readline().split())

schedule = [0] * period

for i in range(0, period):
  schedule[i] = (list(map(str, stdin.readline().rstrip())))

start, end = map(int, stdin.readline().split())
start -= 1 # 인덱스 접근을 편하게 하기위해 감소
end -= 1
changeCount = -1

while start < end:
  maxDay = 0
  
  for i in range(r):
    count = 0
    for j in range(start, end):
      # 빈방을 발견하면 계속 확인함
      if schedule[j][i] in 'O':
        count += 1
      else:
        break
    # 최대 숙박 가능일
    if maxDay < count:
      maxDay = count

  # 숙박 가능일이 0이 아니면 방이 있음
  if maxDay != 0:
    start += maxDay
    changeCount += 1
  # 숙박 가능일이 0이면 예약이 다 찬상태
  else:
    changeCount = -1
    break

print(changeCount)

시간초과가 계속 뜨길래 입력방법도 바꿔보고 했다가 뒤늦게 안 사실은 마지막에 break 하나를 안넣어서 루프탈출을 못해서 그런거였다. 그걸 못찾고 계속 코드 다듬다가 30분이 갔다

이번에는 충분히 할 수 있는데도 '이 방법은 아니지 않을까?' 하면서 고민을 너무 오래했다

최대 숙박 가능일들을 뽑아서 방 번호와 튜플로 묶어서 리스트에 보관하는 뻘짓을 했었는데 조금 생각해보니 그런 데이터를 보관할 필요가 없다는걸 깨닫고 다 날려버림

# [0]시작월 [1]시작일 [2]종료월 [3]종료일

# 3/1 ~ 11/30
# 1. 시작일(초기3/1) 이하 꽃중에 가장 늦게까지 피는 꽃 선택
# 2. 해당 꽃 종료일 이하 꽃중에 현재 종료일보다 더 뒤쪽으로 가장 늦게까지 피는 꽃 선택
# 만약 선택할 수 없다면 0 반환후 즉시 종료
# 매 선택마다 11/30이 초과되는지 확인해야한다
# 선택된 꽃 카운팅 해서 출력

n = int(input())

array = [0] * n
for i in range(n):
  array[i] = list(map(int, input().split()))

# 시작월일 기준으로 정렬
array.sort(key = lambda x: (x[0], x[1]))

index, result = 0, 0
start = [3, 1]
end = [11, 30]

longFlower = array[0]
while True:
  count = 0
  for i in range(index, n):
    # 시작일보다 아래에 있는 꽃 탐색
    if (array[i][0] < start[0]) or (array[i][0] <= start[0] and array[i][1] <= start[1]):
      # 가장 늦게까지 피는 꽃 탐색
      longFlower = max(longFlower, array[i], key = lambda x: (x[2], x[3]))
      count += 1
      index = i + 1 # 루프 횟수를 줄이기 위한 변수
    else:
      break

  # 시작 날짜를 꽃의 끝나는 날로 재지정
  start[0], start[1] = longFlower[2], longFlower[3]
  result += 1

  # 조건을 만족한 경우 루프 탈출
  if start[0] > end[0]:
      break
  # 조건을 하나도 찾지 못한경우 경우의 수가 없음
  elif count == 0:
    result = 0
    break

print(result)

220719 solved

뭔가.. 뭔가 좀 깔끔하지 않은 것 같은데 아무튼 풀었음

처음에 주석으로 워크플로우 대충 구상해놓고 하니까 수월했음

from collections import deque

n = int(input())

def bfs(pivot, start):
  queue = deque([start])

  while queue:
    val = queue.popleft()

    # 최대 범위보다 크면 루프 종료
    if val >= 2**64:
      return 0
    # 나누어지면 공배수라는 뜻
    elif val % pivot == 0:
      return val

    # 큐에 값 추가. 그림으로 그리면 이진트리와 비슷한 그림이 그려짐
    queue.append(val * 10)
    queue.append(val * 10 + 1)

print(bfs(n, 1))

220716 solved

BFS 이용. 이상하게 문제 이해가 오래걸려서 풀이를 좀 찾아본 뒤에서야 이해했음

# 2605 캔디팡 220715

width, height = 7, 7

graph = []
for i in range(height):
  graph.append(list(map(int, input().split())))

# 7x7 리스트 초기화
visited = [[False] * width for _ in range(height)]

count = 0

def dfs(x, y, color):
  global count
  
  if x <= -1 or x >= width or y <= -1 or y >= height:
    return False

  # 방문하지 않음과 동시에 같은 색상인것만 골라서 방문처리
  if visited[x][y] == False and graph[x][y] == color:
    visited[x][y] = True
    count += 1
    dfs(x+1, y, color)
    dfs(x-1, y, color)
    dfs(x, y+1, color)
    dfs(x, y-1, color)
    return True

  return False

result = 0

for i in range(width):
  for j in range(height):
    dfs(i, j, graph[i][j])
    # 3개 이상의 색이 연달아 있는 경우만 카운팅
    if count >= 3:
      result += 1
    count = 0

print(result)

220715 solved

DFS 이용

# _: 색칠되지 않은 부분, *: 색칠된 부분

paint = []
for i in range(10):
  paint.append(list(input()))

x, y = map(int, input().split())

def dfs(array, _x, _y):
  if _x <= -1 or _x >= 10 or _y <= -1 or _y >= 10:
    return

  # 보통 인지하는 x,y와 배열의 행렬은 반대이므로 바꿔서 사용
  if array[_y][_x] == '_':
    array[_y][_x] = '*'
    dfs(array, _x+1, _y)
    dfs(array, _x-1, _y)
    dfs(array, _x, _y+1)
    dfs(array, _x, _y-1)
  else:
    return

dfs(paint, x, y)

for i in range(10):
  for j in range(10):
    print(paint[i][j], end='')
  print("")

220716 solved

일반적인 DFS. visited 처리를 따로 안해도 됨

from queue import PriorityQueue

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

graph = [[0] for _ in range(v+1)]
indegree = [0] * (v+1)
p_queue = PriorityQueue()

for i in range(n):
  x, y = input().split()
  x, y = int(x), int(y)
  graph[x].append(y)
  indegree[y] += 1

for i in range(1, v+1):
  if indegree[i] == 0:
    p_queue.put(-i)

while not p_queue.empty():
  here = -p_queue.get()
  print(here)

  for i in graph[here]:
    indegree[i] -= 1
    if indegree[i] == 0:
      p_queue.put(-i)

정답은 이건데 솔직히 봐도 아직 모르겠음

삽질의 기록들

# v: 정점의 개수 n: 간선의 개수. 인덱스는 둘다 1부터 쓸것

from queue import PriorityQueue

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

# 열n+1 행v+1. 행 인덱스 0은 버릴거기때문에 v만 한개 더 크게
# 앞쪽이 가로길이(열/간선), 뒤쪽이 세로길이(행/정점)
graph = [[0] for _ in range(v+1)]

# 탐색 시작 노드를 저장할 변수
init_v = 0

for i in range(n):
  x, y = input().split()  
  graph[int(x)].append(int(y))
  if i == 0:
    init_v = int(x)
    
result = []

def dfs(array, start, visited):
  # 우선순위 큐 사용 선언
  p_queue = PriorityQueue()
  p_queue.put(start)
  visited[start] = True

  # 큐가 빌때까지
  while not p_queue.empty():
    v = p_queue.get() 
    # 우선순위 큐를 통해 나온 값은 언제나 최소값과 중복이 아님을 보장받는다
    result.append(v)

    for i in range(1, len(array[v])):
      if not visited[array[v][i]]:
        p_queue.put(array[v][i])
        visited[array[v][i]] = True
        
  return

# 방문을 체크하는 리스트
visitedCheck = [False] * (v+1)

dfs(graph, init_v, visitedCheck)

# 주어진 노드 개수만큼 들어가지 않았다면 탐색을 실패했다는 소리
# 애초에 중복은 우선순위 큐에 들어가지 않으니 순회인지, 끊긴건지는 알 수 없음
if len(result) <= v-1:
  print(-1)
else:
  for i in range(len(result)):
    print(result[i])

반례를 보니 우선순위 큐로 풀리네? 해서 짜놨더니 막히고 다음 반례를 확인하니까 아니었음

여전히 헤메고 있는중

def gcd(a, b):
  if a % b == 0:
    return b
  else:
    return gcd(b, a % b)

유클리드 호제법을 재귀함수로 구현

두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 했을 때, A와 B의 최대공약수는 B와 R의 최대공약수와 같다

def dfs(graph, v, visited):
  # 현재 노드를 방문 처리
  visited[v] = True
  print(v, end=' ')
  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

# 2차원 리스트로 각 노드가 연결된 정보를 표현
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [ 1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8]
  [1, 7]
]

# 1차원 리스트로 각 노드가 방문된 정보를 표현
visited = [False] * 9

dfs(graph, 1, visited)

from collections import deque

def bfs(graph, start, visited):
  # 큐 구현을 위해 deque 라이브러리 사용
  queue = deque([start])
  # 현재 노드를 방문 처리
  visited[start] = True
  # 큐가 빌 때까지 반복
  while queue:
    v = queue.popleft()
    print(v, end=' ')
    # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True

# 2차원 리스트로 각 노드가 연결된 정보를 표현
graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

# 1차원 리스트로 각 노드가 방문된 정보를 표현
visited = [False] * 9

bfs(graph, 1, visited)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)):
  # i부터 1까지 1씩 감소하며 반복함
  for j in range(i, 0, -1):
    # 왼쪽의 값보다 작으면
    if array[j] < array[j-1]:
      # 서로 값을 교환한다
      array[j], array[j-1] = array[j-1], array[j]
    # 현재 값보다 더 작은게 없다면 루프 종료
    else:
      break

print(array)

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
  # 시작 인덱스가 끝 인덱스보다 크거나 같으면 즉시 종료
  if start >= end:
    return

  pivot = start
  left = start+1
  right = end

  # 좌측 인덱스가 우측 인덱스보다 작을 때
  while(left <= right):
    # pivot보다 크거나 같은 값을 찾을 때까지 우측으로 한칸씩 이동
    while(left <= end and array[left] <= array[pivot]):
      left += 1
    # pivot보다 작거나 같은 값을 찾을 때까지 좌측으로 한칸씩 이동
    while(right > start and array[right] >= array[pivot]):
      right -= 1
    # 인덱스가 서로 교차하면 피벗과 right를 바꿔준다
    if(left > right):
      array[right], array[pivot] = array[pivot], array[right]
    # 그렇지 않다면 left와 right를 바꿔준다
    else:
      array[left], array[right] = array[right], array[left]

  # 가장 좌측부터 새로운 기준 값 직전까지의 범위로 설정
  quick_sort(array, start, right-1)
  # 새로운 기준 값 직후부터 가장 우측까지의 범위로 설정
  quick_sort(array, right+1, end)

quick_sort(array, 0, len(array)-1)
print(array)

분할-정복의 대표적인 알고리즘.

병합 정렬과 더불어 대부분의 프로그래밍 언어들의 정렬 라이브러리의 근간이 되는 알고리즘.

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  if len(array) <= 1:
    return array
    
  pivot = array[0] # 피벗은 첫 번째 원소
  tail = array[1:] # 피벗을 제외한 리스트

  left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
  right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

파이썬의 장점을 활용해 코드 간결화가 가능하다. 리스트 슬라이싱과 리스트 컴프리헨션 사용

단, 좌우로 분할시키는 과정에서 시간적 손해가 조금 더 있다

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8, 0, 5, 2]

count = [0] * (max(array) + 1)

for i in range(len(array)):
  count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
  for j in range(count[i]):
    print(i, end=' ')

데이터가 0과 999,999 단 2개만 존재하는 경우 메모리를 너무 크게 잡아먹는 비효율성이 발생할 수 있다

동일한 값을 가지는 데이터가 여러 개 등장할 때 효과적으로 사용할 수 있다

# 재귀로 구현
def binary_search(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2
  # 찾은 경우 중간점 인덱스 반환
  if array[mid] == target:
    return mid
  # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
  elif array[mid] > target:
    return binary_search(array, target, start, mid - 1)
  # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
  else:
    return binary_search(array, target, mid + 1, end)

# 원소의 개수와 찾고자 하는 값을 입력 받기
n, target = map(int, input().split())
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

# 반복문으로 구현
def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
      return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
      end = mid - 1
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
      start = mid + 1
  return None

# 원소의 개수와 찾고자 하는 값을 입력 받기
n, target = map(int, input().split())
# 전체 원소 입력 받기
array = list(map(int, input().split()))

# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result == None:
  print("원소가 존재하지 않습니다.")
else:
  print(result + 1)

추가로 bisect_left, bisect_right라는 라이브러리 함수도 기본 제공된다. c++의 lower_bound, upper_bound와 동일함

값이 특정 범위에 속하는 데이터의 개수를 구하거나 같은 숫자가 몇개가 있는지 구할때 사용할 수 있다

다음과 같은 특징을 지닌다

- 부모 노드보다 왼쪽 자식 노드가 작다

- 부모 노드보다 오른쪽 자식 노드가 크다

왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드 가 항상 성립해야 한다

# 한 번 계산된 결과를 메모이제이션 하기 위한 리스트 초기화
d = [0] * 100

# 피보나치 함수를 재귀함수로 구현(Top-down)
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(99))

큰 문제를 해결하기 위해 작은 문제를 호출하기 때문에 재귀는 Top-down 방식이다
한번 계산된 결과를 저장하는것을 메모이제이션(캐싱) 이라고 한다

# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

# 피보나치 함수를 반복문으로 구현(Bottom-up)
for i in range(3, n+1):
  d[i] = d[i - 1] + d[i - 2]
  
print(d[n])

반대로 작은 문제를 모아 큰 문제를 해결하기 때문에 반복문은 Bottom-up 방식이다
Top-down 방식과 다르게 앞서 계산된 결과를 저장하기 위한 리스트를 DP 테이블 이라고 부른다

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
  # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[x] != x:
    return find_parent(parent, parent[x])
  return x

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

# 노드의 개수와 간선(union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
  parent[i] = i

# union 연산을 각각 수행
for i in range(e):
  a, b = map(int, input().split())
  union_parent(parent, a, b)

# 각 원소가 속한 집합 출력
print('각 원소가 속한 집합: ', end='')
for i in range(1, v + 1):
  print(find_parent(parent, i), end=' ')

print()

# 부모 테이블 내용 출력
print('부모 테이블: ', end='')
for i in range(1, v + 1):
  print(parent[i], end=' ')

기본적인 서로소 집합 알고리즘. 최악의 경우 find 함수는 O(V)로 작동하기때문에 효율적이지 못하다.

하지만 경로 압축이라는 아주 간단한 과정으로 최적화를 할 수 있다.

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
  # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
  if parent[x] != x:
    parent[x] = find_parent(parent, parent[x])
  return parent[x]

union 함수들의 처리 완료후 부모 테이블은 위와 동일하게 나오지만, 이후 find 함수를 한번 호출하면 부모 테이블의 각 노드들의 부모는 루트 노드로 갱신된다.

# 큐를 이용한 위상 정렬

from collections import deque

# 노드의 개수와 간선의 개수 입력받기
v, e = map(int, input().split())

# 모든 노드에 대한 진입차수는 0으로 초기화
indegree = [0] * (v + 1)
# 각 노드에 연결된 간선 정보를 담기 위한 연결 리스트 초기화
graph = [[] for i in range(v  +1)]

# 방향 그래프의 모든 간선 정보를 입력 받기
for _ in range(e):
  a, b = map(int, input().split())
  graph[a].append(b)
  # 진입 차수를 1 증가
  indegree[b] += 1

# 위상 정렬 함수
def topology_sort():
  result = [] # 알고리즘 수행 결과를 담을 리스트
  q = deque() # 큐 기능을 위한 deque 라이브러리 사용
  # 처음 시작할 때는 진입차수가 0인 노드를 큐에 삽입
  for i in range(1, v + 1 ):
    if indegree[i] == 0:
      q.append(i)
  # 큐가 빌 때까지 반복
  while q:
    # 큐에서 원소 꺼내기
    now = q.popleft()
    result.append(now)
    # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
    for i in graph[now]:
      indegree[i] -= 1
      # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
      if indegree[i] == 0:
        q.append(i)
  # 위상 정렬을 수행한 결과 출력
  for i in result:
    print(i, end=' ')
    
topology_sort()