투 포인터란?말 그대로 두 개의 포인터(인덱스)를 이용해 배열을 탐색하는 알고리즘특히 정렬된 배열에서 선형 시간 또는 이분 탐색과 결합해 더 빠르게 처리할 수 있다는 장점이 있다.핵심 아이디어: 두 개의 포인터를 이용해 하나의 배열 또는 두 개의 배열을 동시에 탐색하며 불필요한 반복을 줄이고 시간 복잡도를 낮추는 방식! DSA Visualizations | Hello InterviewAce your software engineering coding interview with hands on, interactive lessons on data structures and algorithms. Hello Interview will help you master the most common interview qu..

위상 정렬이란?위상 정렬은 방향 그래프(DAG, Directed Acyclic Graph)에서 노드들을 순서대로 정렬하는 알고리즘이때 정렬된 순서는 모든 간선 (A → B)에 대해 A가 B보다 먼저 나와야 하는 순서를 보장 주로 다음과 같은 문제 상황에서 사용:작업 순서 정하기 (예: 건물을 짓기 전에 먼저 지어야 하는 건물 존재)강의 수강 순서 (선수 과목이 있는 경우)프로젝트 모듈 간의 의존성 처리 동작 방식 (Kahn's Algorithm - BFS 기반)모든 노드의 진입 차수(indegree)를 계산한다.진입 차수가 0인 노드들을 큐에 넣는다.큐에서 하나씩 꺼내어 결과 리스트에 추가하고 연결된 노드의 진입 차수를 1 감소시킨다.새로 진입 차수가 0이 된 노드를 큐에 넣는다.큐가 빌 때까지 반복한..

순열(Permutation)이란? 친구 3명(A, B, C) 중에서 2명을 뽑아 줄을 세운다면 어떻게 될까? 이렇게 순서를 고려해서 고르는 경우를 순열이라고 부릅니다.예를 들어:A → BB → AA → CC → AB → CC → B 총 6가지죠. 순서가 바뀌면 다른 경우로 세는 게 포인트예요! 수학적으로는 이렇게 표현해요:nPr = n! / (n - r)! 즉 `n`개의 항목 중 `r`개를 순서를 고려해서 고르는 경우의 수입니다. 순열을 Java로 구현해 보자!흐름 설명어떤 항목들( `arr`)에서중복 없이 하나씩 골라( `visited`)`r`개가 되면 출력해요.코드public class Permutation { static char[] arr = {'A', 'B', 'C'}; // 선택할 항목..

친구 5명 중에서 2명을 골라 카페에 같이 갈 사람을 뽑는다고 생각해 볼게요.“철수, 영희”를 고르는 것과“영희, 철수”를 고르는 건 순서가 다르지만 결과는 똑같죠? 이렇게 순서에 상관없이 선택하는 걸 조합(Combination)이라고 합니다.(+ 순서에 따라 구분하여 선택하는 건 순열) 수학적인 공식은 다음과 같습니다:nCr = n! / (r! * (n - r)!) 예를 들어 5명 중 2명을 뽑는 경우의 수는:5C2 = 5! / (2! * 3!) = 10 그런데 팩토리얼로 다 해결될까요?작은 수에서는 괜찮지만 숫자가 커지면 문제는 달라집니다.예를 들어 100C50을 구하려면 100! 같은 엄청나게 큰 수를 계산해야 하고 이건 long 자료형도 쉽게 넘어서요.그래서 우리는 좀 더 프로그래밍 친화적인 방법..

신장 트리(Spanning Tree)원래 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 [자료구조] #7_1 트리트리 구현시 로직이 많이 들어가서 알고리즘 같은 느낌을 준다. 구현하기 복잡하기 때문에 자료구조 중에서 면접에서 자주 질문이 나오는 편이다. ** 트리(Tree) 구조 Node와 Branch를 이용해서, 사이itsanisland.tistory.com신장 트리의 조건본래의 그래프의 모든 노드를 포함해야 함모든 노드가 서로 연결트리의 속성을 만족시킴(사이클이 존재하지 않음) 최소 신장 트리(Minimum Spanning Tree, MST)가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree를 지칭함 최소 신장 트리 알고리즘그래프에서 ..

최단 경로 문제최단 경로 문제란? 두 노드를 잇는 가장 짧은 경로를 찾는 문제가중치 그래프 (Weighted Graph)에서 간선 (Edge)의 가중치 합이 최소가 되도록 하는 경로를 찾는 것이 목적 최단 경로 문제 종류1. 단일 출발 및 단일 도착(single-source and single-destination shortest path problem) 최단 경로 문제그래프 내의 특정 노드 `u`에서 출발해서 또 다른 특정 노드 `v`에 도착하는 가장 짧은 경로를 찾는 문제 2. 단일 출발(single-source shortest path problem) 최단 경로 문제그래프 내의 특정 노드 `u`와 그래프 내 다른 모든 노드 각각의 가장 짧은 경로를 찾는 문제(다익스트라 알고리즘) 3. 전체 쌍(al..