Code Inside

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(너비 우선 탐색)는 그래프 탐색에서 가장 많이 사용되는 알고리즘✅ 각각의 장점과 사용해야 하는 문제 유형을 이해하는 것이..

📌 트리는 사이클을 가질 수 있는가?➡ "아니요, 트리는 절대 사이클을 가질 수 없습니다!" 🚀➡ 트리는 "사이클이 없는 연결 그래프"입니다.🚀 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..

https://school.programmers.co.kr/learn/courses/30/lessons/42861 섬 연결하기 문제의 경우, n개의 섬이 있고, costs에 [섬1, 섬2, 비용] 형태로 연결 비용이 주어짐.모든 섬을 최소 비용으로 연결하는 방법을 찾아야 함.MST(최소 신장 트리, Minimum Spanning Tree) 알고리즘(Kruskal or Prim)으로 해결함최소 비용으로 연결해야 하므로 사이클이 생겨서는 안됨📌 사이클이 형성되면 안 되는 이유 (MST에서)➡ MST(최소 신장 트리, Minimum Spanning Tree)는 "모든 노드를 연결하면서도, 사이클이 없는 트리"여야 함.➡ 즉, 같은 노드를 두 번 방문하는 "순환 경로(사이클)"가 있으면 트리가 아님!1. MS..

https://school.programmers.co.kr/learn/courses/30/lessons/42861📌 MST (Minimum Spanning Tree, 최소 신장 트리)란?➡ "모든 정점을 연결하는 간선들의 부분집합 중, 최소 비용으로 연결할 수 있는 트리" ➡ Greedy(탐욕법) 알고리즘을 기반으로 동작 1. MST(최소 신장 트리)의 특징https://www.geeksforgeeks.org/spanning-tree/ Spanning Tree - GeeksforGeeksA Computer Science portal for geeks. It contains well written, well thought and well explained computer science and progra..