[백준] 2533 - 사회망 서비스(SNS) (tree DP)문제 소개백준 2533번 사회망 서비스(SNS) 문제 정리합니다.이 문제는 친구 관계가 트리로 주어졌을 때 최소 얼리 어답터 수를 구하는 문제입니다.핵심은 각 노드의 상태(얼리 어답터 여부)에 따른orion-log.tistory.com해결 과정 및 코드핵심 최적화 아이디어ArrayList → 배열 기반 인접 리스트: 메모리 접근 패턴 개선ArrayList[] 대신 int[] head, next, to 사용2차원 → 1차원 DP 배열: 메모리 접근 최적화dp[node][0/1] 대신 dp0[node], dp1[node] 분리비트 연산 활용: 곱셈을 시프트 연산으로 대체2 * n → n 로 연산코드시간 복잡도: O(N)공간 복잡도: O(N)impo..

문제 소개백준 2533번 사회망 서비스(SNS) 문제 정리합니다.이 문제는 친구 관계가 트리로 주어졌을 때 최소 얼리 어답터 수를 구하는 문제입니다.핵심은 각 노드의 상태(얼리 어답터 여부)에 따른 최적값을 DP로 계산하는 데 있습니다.문제 링크: 사회망 서비스(SNS) - 백준 2533번 문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:문제 조건 분석: 얼리 어답터가 아닌 사람은 모든 친구가 얼리 어답터여야 함그래프 특성 - 트리: 친구 관계가 트리 구조로 주어짐 (사이클 없음)완전탐색의 한계: 각 사람마다 2가지 선택(얼리 어답터 O/X)이 있으므로 2^N은 시간초과분할정복 아이디어: 부모 노드의 답 = 자식 노드들의 답을 조합해서 구할 수 있음부모가 얼리 어답터면: 자식은 어떤 상태든 O..

문제 소개백준 2015번 - 수들의 합4 문제를 정리합니다.이 문제는 정수 배열 A에서 연속된 부분 구간의 합이 K인 경우의 개수를 구하는 문제입니다.단, N(배열 길이)이 최대 200,000이므로 모든 구간을 직접 탐색하는 O(N²) 방식으로는 시간 내에 해결할 수 없습니다.문제 링크: 수들의 합4 - 백준 2015번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:문제 입력 크기(N ≤ 200,000)를 보면 O(N²) 전수 탐색은 시간 초과가 된다.누적합(prefix sum) 을 사용하면 임의 구간 A[l..r]의 합을 O(1)로 구할 수 있다.sum(l..r) = prefix\[r\] - prefix\[l-1\].prefix\[r\] - prefix\[l-1\] == K 이면 prefix..

[백준] 점프 문제 풀이 https://orion-log.tistory.com/96참고할 주요 개념 설명✅ Java에서 자료형 범위 – long을 쓰라는 명확한 신호문제에서 “경로 수는 2⁶³ - 1보다 작거나 같다”는 조건은 사실상 다음 의미와 같다:👉 int로는 절대 안 되고 long을 써야 한다는 공식 힌트자료형바이트 수표현 가능 범위byte1 byte-2⁷ ~ 2⁷ - 1 (-128 ~ 127)short2 bytes-2¹⁵ ~ 2¹⁵ - 1 (-32,768 ~ 32,767)int4 bytes-2³¹ ~ 2³¹ - 1 (약 21억)long8 bytes-2⁶³ ~ 2⁶³ - 1 (약 ±9.2×10¹⁸)예시로 dp[i][j] += dp[x][y] 연산이 수십억 번 중첩될 수 있으므로, int는 누적 ..

문제 소개점프 - 백준 1890번 문제를 정리합니다.이 문제는 게임판에서 오른쪽 또는 아래 방향으로만 이동하며 도달 가능한 경로의 개수를 세는 DP 유형의 문제입니다.핵심은 "현재 위치에서 점프 칸 수만큼만 이동 가능"하고, "0이 나오는 칸은 종착점"이라는 규칙을 만족해야 합니다.문제 링크: 점프 - 백준 1890번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:도착할 수 있는 경로 수를 저장할 dp[i][j] 배열 정의시작점 (0,0)에서 출발해, 오른쪽 또는 아래로 점프하는 방식으로 경로 누적각 칸에서 이동 가능한 거리(jump)를 읽고, i + jump 또는 j + jump 위치에 dp[i][j]를 더함0이 적힌 칸은 더 이상 점프할 수 없으므로 무시해결 과정 및 코드핵심 아이디어dp[..

문제 소개에디터 - 백준 1406번 문제를 정리합니다.이 문제는 간단한 텍스트 에디터를 구현하는 문제로, 문자열 수정 명령어들을 빠르게 처리할 수 있는 자료구조 선택이 핵심입니다.문제 링크: 에디터 - 백준 1406번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:문자열 중간 삽입, 삭제 연산이 많기 때문에 일반 String 또는 ArrayList로는 시간 초과 발생커서를 기준으로 왼쪽/오른쪽 문자들을 두 개의 자료구조(스택 or 덱)로 나눠 저장명령어마다 O(1) 또는 O(1)에 가까운 속도로 처리할 수 있도록 구현해결 과정 및 코드핵심 아이디어문자열을 커서를 기준으로 왼쪽(left 덱)과 오른쪽(right 덱)으로 나누어 저장커서는 항상 left와 right 사이에 있는 것으로 간주각 명령..

문제 소개두 수의 합 - 백준 3273번 문제를 정리합니다.이 문제는 수열에서 두 수를 골라 합이 특정 값이 되는 경우의 수를 찾는 문제입니다.특히 이 문제는 수의 범위가 정해져 있고, 모든 수가 서로 다른 양의 정수라는 조건이 있어서, 카운팅 배열을 이용한 O(n) 풀이가 가능합니다.문제 링크: 두 수의 합 - 백준 3273번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:수열의 각 수를 인덱스로 사용해 boolean 배열에 존재 여부를 기록수열을 다시 순회하면서 x - a[i]가 존재 배열에 포함되어 있는지 확인(a, b)와 (b, a)를 각각 세게 되므로 최종 카운트는 2로 나눠서 출력해결 과정 및 코드핵심 아이디어수열에 있는 모든 수를 exists[num] = true로 표시이후 다시 ..

문제 소개두 수의 합 - 백준 3273번 문제를 정리합니다.이 문제는 주어진 수열에서 두 수를 골라 합이 특정 값이 되는 경우의 수를 구하는 투 포인터 유형의 문제입니다.핵심은 정렬된 배열에서 양쪽 끝에서 좁혀가는 방식으로 효율적으로 조건을 만족하는 쌍을 찾는 것입니다.문제 링크: 두 수의 합 - 백준 3273번 문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:정렬 후 투 포인터 기법을 사용하여 양쪽 끝에서 포인터를 이동합이 목표보다 작으면 왼쪽 포인터 증가, 크면 오른쪽 포인터 감소합이 목표와 같으면 카운트 증가 후 왼쪽 포인터 증가모든 원소가 서로 다른 양의 정수이므로 중복 쌍에 대한 처리를 따로 고려하지 않아도 됨해결 과정 및 코드핵심 아이디어수열을 정렬한 뒤, 가장 작은 수(left)와..

문제 소개고층 건물 - 백준 1027번 문제를 정리합니다.이 문제는 각 고층 빌딩에서 볼 수 있는 다른 빌딩의 수를 구하는 시뮬레이션 문제입니다.핵심은 두 빌딩 사이를 잇는 직선이 다른 빌딩에 가려지지 않아야 한다는 조건을 만족하는지 확인하는 것입니다.문제 링크: 고층 건물 - 백준 1027번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:각 빌딩 i에 대해 오른쪽 빌딩 j를 차례로 탐색(i, height[i])와 (j, height[j])를 연결하는 직선의 기울기를 계산이 기울기가 지금까지 본 것 중 가장 크면 → i와 j는 서로 볼 수 있음이때 기울기가 maxGradient보다 작거나 같다면 → 중간에 있는 빌딩이 가리는 것해결 과정 및 코드핵심 아이디어빌딩 i에서 오른쪽으로 나아가며 j를..

문제 소개한 줄로 서기 - 백준 1138번 문제를 정리합니다.이 문제는 각 사람마다 왼쪽에 자신보다 키 큰 사람이 몇 명 있었는지만 기억할 때, 전체 줄 서기 순서를 구하는 문제입니다.문제 링크: 한 줄로 서기 - 백준 1138번문제 접근 방식이 문제는 다음과 같은 방식으로 접근했습니다:사람들의 키는 1부터 N까지 정수이며, 입력 순서는 키 1부터 N까지 오름차순 기준키가 큰 사람부터 거꾸로 순회하며 줄을 세움 → 작은 사람보다 큰 사람이 먼저 줄에 들어가 있어야 삽입 위치가 정확히 계산됨LinkedList를 사용해 원하는 위치에 빠르게 삽입각 사람은 본인이 기억하는 큰 사람 수만큼 왼쪽에 사람을 두고 해당 위치에 삽입해결 과정 및 코드핵심 아이디어입력의 i번째 값은 키가 i+1인 사람이 왼쪽에 있어야 ..