# 0과 1로만 이루어진 수n = int(input())# n 자리 이친수의 개수dp = [0]*(n+1)dp[1] = 1#이친수는 0으로 시작할 수 없음 (단한가지)if n >= 2: dp[2] = 1# 10 만 가능함 (단한가지)for i in range(3,n+1): # 3자리부터 n자리까지의 이친수 개수를 구할 때까지 반복 dp[i] = dp[i-1] + dp[i-2] # 전형적인 피보나치 수열과 동일한 점화식print(dp[n]) 이친수 조건:0으로 시작 ❌1이 두 번 연속 나오면 안 됨 (11 ❌)이진수만 사용 가능 (0 또는 1)즉, 이친수는 맨 끝이 1이면 반드시 그 앞은 0 이어야 함 이 문제를 DP로 풀이하는 이유: 어떤 자릿수까지 올 때 그 이전 자릿수의 패턴만 ..
#연산 재활용 -> dpX = int(input())dp = [0] * (X+1) # 기본적인 dp 세팅for i in range(2,X+1): dp[i] = dp[i-1] +1 #그리디로 푼다면 짝수, 홀수로 바로 나눌 수 있지만 #이 문제의 경우 경우의 수를 고려하는 최솟값임 if i % 2 == 0: dp[i] = min(dp[i], dp[i//2]+1) # if i % 3 == 0: dp[i] = min(dp[i], dp[i//3]+1) # print(dp[X])
https://school.programmers.co.kr/learn/courses/30/lessons/42862 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 이 문제에서 얻고 가야할 부분 1. set() - remove메서드의 낮은 시간 복잡도, 얕은 복사2. 문제에서 작은 예시를 통해 문제를 이해하자 ->* 여벌의 체육복을 가져온 사람은 단 한명에게만 체육복을 빌려줄 수 있다.* 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.def solution(n, lo..
DFS vs BFS 각각 언제 사용해야 할까?개인적으로 탐색 문제의 경우 1. 완전 탐색 -> 2. DFS -> 3. BFS 으로 시도해봄 기준DFSBFS탐색 방식한 경로를 끝까지 탐색 후 백트래킹같은 레벨을 먼저 탐색자료구조스택(Stack) / 재귀(Recursion)큐(Queue)시간 복잡도O(V + E)O(V + E)사용 예시경로 탐색, 백트래킹, 사이클 판별최단 경로 탐색, 레벨별 탐색적합한 경우경우의 수 탐색, 트리 탐색최단 거리, 미로 탐색, 다차원 탐색✅ DFS는 모든 경로를 탐색해야 하는 경우✅ BFS는 최단 거리 탐색이 필요한 경우 ✅ DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)는 그래프 탐색에서 가장 많이 사용되는 알고리즘✅ 각각의 장점과 사용해야 하는 문제 유형을 이해하는 것이..
[자료구조] 트리(Tree)와 사이클
📌 트리는 사이클을 가질 수 있는가?➡ "아니요, 트리는 절대 사이클을 가질 수 없습니다!" 🚀➡ 트리는 "사이클이 없는 연결 그래프"입니다.🚀 1️⃣ 트리의 정의Types of Trees in Data Structure based on the number of children출처: https://www.geeksforgeeks.org/types-of-trees-in-data-structures/ 📌 트리(Tree)란?사이클이 없는 "연결 그래프"N개의 노드가 있으면, 항상 "N-1개의 간선"을 가짐모든 노드가 연결되어 있으며, 경로가 유일함루트(Root)에서 시작하여 부모-자식 관계로 이루어짐📌 트리의 핵심 조건1️⃣ 모든 노드가 연결되어 있어야 함 (즉, 한 개의 연결 요소)2️⃣ 사이클이 ..
이 문제 풀면서 궁금했던 점: 공유기 1개가 몇개까지 커버치는지가 궁금했는데 문제 방향이랑은 크게 상관이 없음 이분 탐색으로 풀어야겠다는 생각은 못하고 각 공유기의 지점을 포인터로 지정해야 하나 생각함 -> 근데 이래 버리면 포인터가 공유기 개수만큼 있어야 하니까 안됨 -> 완전 탐색으로 풀어야 하나 생각함 -> 시간이...?????????되나 ➡ N = 200,000, C = 200,000일 때,➡ 가능한 공유기 간 거리(gap)의 최대값은 1,000,000,000 (10억)➡ 완전 탐색(O(N * max_gap))으로 해결하려면 최악의 경우 200,000 * 10^9 = 2 * 10^13결론: 최대, 최소 거리 문제의 경우 시간복잡도를 계산해보고 완전 탐색 안될거 같으면 이진탐색으로 가자...for ..
코딩 테스트에서 "완전 탐색(Brute Force)"이 불가능한 경우를 어떻게 알까?➡ 시간 복잡도를 기반으로 연산 횟수를 계산하면 알 수 있습니다.💡 핵심:컴퓨터는 1초에 약 10^8 ~ 10^9(1억 ~ 10억)번 연산을 수행 가능따라서 "최악의 경우 연산 횟수" 를 계산하여 1억을 넘으면 비효율적인 알고리즘이라고 판단할 수 있음완전 탐색(Brute Force) 이 가능한지 시간 복잡도를 계산하여 결정해야 함- 삼성 제외 일반적인(?) 코테 문제들의 시간 제한은 1초이기 때문에 1억이내(10^8)의 연산으로 끝내야 함- 1억 이상의 완전 탐색을 요구하지 않음 🚀 1️⃣ 연산 횟수에 따른 알고리즘 선택 기준 연산 횟수시간 복잡도알고리즘N ≤ 10O(N!) (팩토리얼)완전 탐색 가능 (순열, 백트래킹..
큰 문제를 작은 문제로 나누어 풀고, 중복 계산을 줄여 효율적으로 해결하는 알고리즘 기법🚀 동적 계획법(DP)이란?✅ 큰 문제를 작은 하위 문제로 나누어 푸는 방식✅ 이전에 계산한 결과를 저장하여 중복 계산을 줄임 → 메모이제이션(Memoization) 사용 / 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가 ✅ "최적 부분 구조(Optimal Substructure)"와 "중복되는 부분 문제(Overlapping Subproblems)"가 존재할 때 사용 가능 🚀 DP의 두 가지 접근 방법1️⃣ Top-Down (재귀 + 메모이제이션)큰 문제를 작은 문제로 나누어 푸는 방식재귀 + 딕셔너리(memo) 또는 리스트(dp[])를 사용하여 중복 계산을 줄임def fib(n): if n..