본문 바로가기

Algorithm475

[파이썬] 코드트리 : 고대 문명 유적 탐사 (골드4) [파이썬] 코드트리 : 고대 문명 유적 탐사 (골드4)https://www.codetree.ai/training-field/frequent-problems/problems/ancient-ruin-exploration/description?page=1&pageSize=20풀이방향성 생각BFS + 구현회전은 피벗 주변 8칸을 큐에 담아서 rotate 전체코드from collections import dequeK,M = map(int,input().split())arr = [list(map(int,input().split())) for _ in range(5)]numbers = list(map(int,input().split()))dire = [(1,0),(0,1),(-1,0),(0,-1)]# BFS를 돌려서.. 2024. 5. 1.
[파이썬] 프로그래머스 : N으로표현 (레벨3) [파이썬] 프로그래머스 : N으로표현 (레벨3)https://school.programmers.co.kr/learn/courses/30/lessons/42895풀이방향성 생각<ul style="list-style.. 2024. 4. 24.
[파이썬] 프로그래머스 : 올바른 괄호의 개수 [파이썬] 프로그래머스 : 올바른 괄호의 개수 (레벨4) https://school.programmers.co.kr/learn/courses/30/lessons/12929 풀이 방향성 생각 DFS로 탐색하면서 중복 방문한 노드는 메모제이션한 값으로 프루닝. 전체코드 def solution(n): dp = [[-1]*(n+1) for _ in range(n+1)] def dfs(l,r): # 맞춰서 도달 했으면 카운팅 if (l,r) == (0,0): return 1 # r을 더 많이쓰면 올바르지 않음. 괄호는 주어진 개수만 사용해야함 if l>r or l 2024. 4. 23.
[파이썬] 프로그래머스 : 사칙연산 (레벨4) [파이썬] 프로그래머스 사칙연산 (레벨4) https://school.programmers.co.kr/learn/courses/30/lessons/1843 풀이 방향성 생각 분할정복 or State DP가 생각났다. 분할정복으로 풀이하면, 부분 구조의 최대값, 최소값이 필요하다. ()앞에 어떤 부호가 붙는지가 중요해서 부호 별로 메모제이션을 해줘야한다. 나는 각 현재 숫자에 영향을 줄 수 있는 - 개수가 몇 개 있는지, 현재 몇 번째 숫자를 연산중인지 2가지 상태를 기준으로 삼고 2차원 DP를 업데이트 했다. (-) 부호를 만나면 괄호를 열 수 있다. 숫자 앞에 열려있는 괄호가 홀수개면 (-) 홀수개가 있으므로 빼기, 짝수개면 더하기. 숫자 연산이 끝나면 열려있는 괄호 c개 중 0~c개를 닫을 수 있다... 2024. 4. 23.

티스토리툴바