DP / Knapsack 문제https://www.acmicpc.net/problem/12865  냅색(Knapsack) 알고리즘 냅색 알고리즘은 대표적인 동적 계획법(DP) 문제 중 하나로, 주어진 가방에 담을 수 있는 무게 제한과 각 물건의 가치를 고려하여 최대한의 가치를 얻는 문제다. 이 알고리즘은 크게 두 가지 유형으로 나뉜다. 1. 분할 가능한 배낭 문제 (Fractional Knapsack): 물건을 부분적으로 쪼개어 담을 수 있는 경우에 해당한다.각 물건의 가치를 무게로 나눈 값(즉, 무게 대비 가격 비율)을 기준으로 물건을 정렬하여 높은 비율 순서대로 가방에 담는다.가방의 남은 용량보다 물건의 무게가 크다면, 물건을 잘라서 넣는다. 이렇게 하면 쉽게 최대 가치를 얻을 수 있다.2. 0-1 ..

그래프, BFS/DFS 문제https://www.acmicpc.net/problem/1967 트리의 지름 트리의 지름이란?어떤 두 노드를 선택해서 당겼을 때, 가장 길게 늘어나는 경우의 두 정점 사이의 거리를 말한다.즉, 트리의 지름이란 트리 상에서 가장 먼 거리를 가지는 두 정점 사이의 경로이다.위의 그래프에서 9 노드와 12 노드의 사이의 거리는 45이며, 이 경로가 트리의 지름이 된다. 트리의 지름을 구하는 순서1. DFS를 통해 임의의 정점(x)로부터 가장 먼 정점(y)를 구한다.2. DFS를 통해 구해진 (y) 정점으로부터 가장 먼 정점(z)를 구한다.3. (y) 정점과 (z) 정점을 잇는 경로가 트리의 지름이 된다.  💡 풀이코드 (성공 - DFS)# DFS# visited 초기화 주의 im..

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..