close
1. 집합이란 무엇인가집합은 공통된 특성을 지닌 원소들의 모음이다. 컴퓨터 과학에서는 데이터를 중복 없이 저장하고, 원소의 포함 관계를 빠르게 판단할 수 있다는 점에서 의미가 크다. 예를 들어 ⟨⟨A ∪ B⟩⟩처럼 둘 이상의 집합을 합치는 연산(합집합), ⟨⟨A ∩ B⟩⟩처럼 공통 원소를 찾는 연산(교집합), 그리고 ⟨⟨A ⊆ B⟩⟩처럼 포함 여부를 판단하는 연산(부분집합)이 대표적이다. 프로그래밍 언어에서는 배열, 리스트, 맵 등과 달리 중복을 허용하지 않는 컬렉션이라는 특징이 추가된다. 자바의 ⟨⟨HashSet⟩⟩, 파이썬의 ⟨⟨set⟩⟩이 이에 해당하며, 해시 함수를 이용해 평균 O(1)의 포함 여부 검사, 삽입, 삭제를 지원한다. 이러한 집합 개념은 이후 다룰 서로소 집합(Disjoint Set)..
1. 플로이드 워셜 알고리즘 구현플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘이다. 입력으로 주어지는 간선의 방향성과 가중치를 기반으로, 그래프 내 모든 노드 간의 최소 비용을 계산할 수 있다. 백준 11404번 문제는 이 알고리즘의 전형적인 구현 문제로, 단일 시작점이 아니라 모든 정점 간의 최소 비용을 구해야 하는 것이 핵심이다. 이를 해결하기 위해 인접 행렬을 활용하여 그래프를 표현하고, 3중 for문을 통해 플로이드-워셜 알고리즘을 적용한다. 특히 중요한 점은, 같은 도시를 연결하는 간선이 여러 개 있을 수 있기 때문에, 더 작은 비용으로 갱신하는 처리가 필요하다는 것이다. 아래는 해당 문제의 플로이드-워셜 알고리즘 구현 코드이다:impor..
1. 들어가기 전에최단 경로 문제를 풀 때 흔히 떠올리는 것은 BFS나 다익스트라 알고리즘이다. 하지만 간선의 가중치가 0 또는 1로만 이루어진 경우라면, 일반적인 BFS에 덱(Deque)을 결합한 0-1 BFS를 사용할 수 있다. 이 방식은 우선순위 큐를 사용하는 다익스트라보다 구현이 간단하고 빠를 수 있다.대표적인 예시로, 백준 13549번 "숨바꼭질 3" 문제가 있다. 이 문제는 수빈이가 현재 위치에서 동생의 위치까지 이동할 때 걸리는 시간을 최소화하는 문제로, 다음과 같은 세 가지 이동 방식이 있다:x - 1로 이동 (1초 소요)x + 1로 이동 (1초 소요)x * 2로 이동 (0초 소요)가중치가 0 또는 1로 정해져 있기 때문에, 이 문제는 0-1 BFS로 해결할 수 있다.아래는 해당 문제를 푼..
1. 누적합누적합(prefix sum)이란 배열의 특정 구간 합을 빠르게 계산하기 위해 미리 누적된 합을 저장하는 방식이다. 이 방식을 이용하면 여러 구간 합을 반복해서 구할 때 중복된 연산을 줄이고, 효율성을 높일 수 있다.누적합이 유용한 상황의 대표적 예로 백준 11441번(합 구하기)과 11660번(구간 합 구하기 5)을 살펴보자.1차원 누적합 (백준 11441번 - 합 구하기)이 문제는 1차원 배열에서 특정 구간의 합을 여러 번 구하는 문제다. 각 위치까지의 누적합을 미리 계산해두면, 이후 구간 합 계산을 O(1)의 시간 복잡도로 처리할 수 있다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamRe..
1. 점화식 활용다이나믹 프로그래밍(DP)은 문제를 작은 부분 문제로 나누고, 이 작은 문제들의 해답을 바탕으로 더 큰 문제를 해결하는 방식이다. 특히 DP 문제는 반복적인 패턴을 점화식으로 표현하여 구현하는 경우가 많다. 점화식은 이전 상태를 기반으로 다음 상태를 정의하는 수학적 표현이며, DP 문제 해결의 핵심이라 할 수 있다. 이번 단락에서는 점화식을 명확히 정의하여 DP를 구현하는 예제로, 백준의 13699번(카탈란 수)과 16395번(파스칼의 삼각형)을 통해 DP에서의 점화식 활용을 알아보겠다. 이 두 문제는 공통적으로 이전 단계의 값을 활용해 다음 단계의 값을 구하는 명시적인 점화식을 갖추고 있다. 각 점화식은 다음과 같다.13699번 (카탈란 수)카탈란 수를 DP로 구현한 코드는 다음과 같다..
Stream 이란?자바의 스트림(Stream)은 데이터의 흐름을 추상화한 개념으로, 컬렉션(List, Set 등)이나 배열에 저장된 데이터를 선언형 스타일로 처리할 수 있게 해준다.반복문 없이도 요소를 필터링하거나 변환, 집계할 수 있으며, 내부 반복을 통해 코드의 간결성과 가독성을 높여준다.예를 들어, 숫자 리스트에서 짝수만 골라 제곱한 결과를 구하고 싶다면 기존에는 이렇게 작성했을 것이다.List list = Arrays.asList(1, 2, 3, 4, 5);List result = new ArrayList();for (Integer i : list) { if (i % 2 == 0) { result.add(i * i); }}하지만 스트림을 사용하면 이렇게 바뀐다.List re..
