DP / 재귀+ Memorization 문제https://www.acmicpc.net/problem/10942 접근 방식재귀 + Memorization 기법을 활용하여 문제를 풀었다. 한 수열에 대해 질문의 개수가 M(1 ≤ M ≤ 1,000,000)번 주어진다. 질문의 개수가 들어올 때마다 재귀호출하여 값을 구하는 것은 매우 비효율적(반복됨)이다.따라서, memo에 기록해둔 값이 있다면 dfs를 재귀호출하지 않고, memo에 기록해둔 값을 바로 리턴하도록 구현하였다. 💡 풀이코드 (성공)import syssys.setrecursionlimit(10**9)# 7'''1 -> [[1][-1][-1][-1][-1][-1][-1]] 1,2,3,4,5,6,72 -> [[1][-1][-1][-1][-1][-1]..

DP / DFS + Memorization 문제https://www.acmicpc.net/problem/2011 접근 방식어떤 암호가 주어졌을 때, 그 암호의 해석이 몇 가지가 나올 수 있는지 경우의 수 구하기 -> 같은 암호에 대해 반복해서 해석하는 것을 방지하고 계산 효율성을 높이기 위해 dp나 memorization 기법을 활용하자 !-> 암호의 i번째 자리에 대해 이미 구한 가짓수는 dp 또는 memo 배열에 저장해 두자.dfs만 사용하는 것은 불필요한 연산을 반복하게 되므로 memorizatino 기법을 활용하여 memo 배열에 기록하자.-> 만약, memo에 기록해둔 값이 있다면 dfs를 재귀호출하지 않고, memo에 기록해둔 값을 바로 리턴하자. 💡 풀이코드 (성공)'''1. 처음에 생각했..

BFS, DFS 문제https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근방식숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수 구하기 -> DFS로 풀어 모든 경우의 수 탐색특정 숫자를 변환하였을 때의 타겟 넘버를 만족하는지를 비교하여 가짓수(경우의 수) 구하는 것이므로 return값 설정 풀이코드  (실패, 오답-cnt를 전역변수로 선언)import syssys.setrecursionlimit(10 ** 9)cnt = 0oper = [1, ..

재귀, 분할정복 문제https://www.acmicpc.net/problem/2448 접근 방식 별은 위와 같이 n // 2로 분할해도 같은 형상을 갖는다. 즉, 특정 패턴이 반복되어 나타내는 것을 볼 수 있다. 이는 전형적인 분할정복 문제의 특징이다. 분할정복 문제는 재귀로 풀면 쉽게 풀리므로 나 또한 재귀로 접근해겠다.  💡 풀이코드 (성공)import sysn = int(sys.stdin.readline())graph = [[' '] * n * 2 for _ in range(n)]def star(n, r, c): if n == 3: graph[r][c] = '*' for j in range(c - 1, c + 2): if j == c: contin..

재귀 문제https://www.acmicpc.net/problem/5639  풀이코드  (실패, 시간초과)# 무한입력을 위해 try - except 추가# 25%에서 시간초과 코드 import syssys.setrecursionlimit(10**9)class Node: def __init__(self, data): self.data = data self.left = None self.right = Nonedef insert(root, data): if root == None: return Node(data) else: if root.data > data: # 왼쪽 root.left = insert(root..

재귀, 분할정복 문제 https://www.acmicpc.net/problem/1074 풀이코드  (실패1, 메모리초과)import sys N, r, c = map(int, sys.stdin.readline().split())arr = [[-1] * 2 ** N for _ in range(2 ** N)]def visit(n, i, j): global cnt, r, c if n == 1: arr[i][j] = cnt cnt += 1 else: if arr[r][c] != -1 : return newSize = n // 2 visit(newSize, i, j) visit(newSize, i, j + newSize) ..