# backjoon
[백준] 11505번 - 구간 곱 구하기
문제 분석 이 문제를 풀기에 앞서 다음과 같은 개념이 필요하다. >(AB) % C == (A%C)(B%C) % C 위의 개념을 인지하며, 세그 먼트 트리를 이용해 풀면된다.
[백준] 10868번 - 최솟값
세그 먼트 트리의 개념을 이용해서, 원하는 구간의 최솟값을 구할 수 있다.주어지는 N개의 값들을 리프노드에 저장하고, 최솟값을 만족하도록 위로 올라오면서, 최솟값 트리의 형태로 만들어준다.그 후, 원하는 구간을 찾아 올라오면서 최솟값을 얻어내면 된다.
[백준] 2042번 - 구간 합 구하기
해당 문제에서는 데이터 변경이 일어나므로, 데이터 변경시에 시간이 많이 소요되는 합 배열로는 풀 수 없다.따라서, 세그먼트 트리의 개념을 이용해서 풀면된다.다음의 3단계로 진행된다.트리 초기화질의 값 구하기데이터 업데이트 하기이후, 만든 트리 리스트의 2^k번째 인덱스
[백준] 1991번 - 트리 순회
문제에서 주어진 노드간의 관계를 트리 형태의 자료구조에 적절하게 저장하고, 그 안에서 탐색을 수행하면 된다.따라서 인접리스트의 형태로 트리의 관계를 표현하고, 재귀함수를 통해 탐색을 수행하여 문제를 해결하면된다.
[백준] 14425번 - 문자열 집합
문제 분석 집합 S에 속해 있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트하는 전형적인 트라이 자료구조 문제이다. 소스 코드
[백준] 1068번 - 트리
트리의 관계를 인접리스트로 표현하고, DFS를 통해 부모-자식의 관계를 설정하여 표현할 수 있다.따라서 DFS 및 visited배열을 통해 주어진 입력대로 관계를 설정하고 풀어나가면 된다.
[백준] 11725번 - 트리의 부모 찾기
트리를 어떻게 구조화 할지에 대한 문제이다. 인접리스트로 트리의 구조를 만들어보고, DFS를 통해 비교해가면서, 부모노드의 번호를 저장해주면 된다.이때 트리의 루트 노드가 1이라고 주어져 있으므로, 1번 부터 DFS를 진행하면 된다.
[백준] 1414번 - 불우이웃돕기
인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 필요하다.먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다.이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장
[백준] 17472번 - 다리 만들기 2
문제에서 주어진 N과 M의 크기가 매우 작은 편이라 시간 복잡도에 제약은 크지 않다.문제를 해결하기 위해서는 먼저 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현하는 과정이 필요하다.이후에는 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는
[백준] 1197번 - 최소 스패닝 트리
최소 신장 트리를 묻고 있는 문제로, 최소 신장 트리를 구하여 해결하면 된다.최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지리스트의 형태로 저장한다.이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다.또한, 사이클
[백준] 1389번 - 케빈 베이컨의 6단계 법칙
사람들을 각각 노드로 봤을 때, 각각의 노드에서 여러 노드로 가는 최소값을 구해주고 이러한 값들을 더해준 후, 비교하면 되므로,플로이드-워셜 알고리즘을 통해 해결하면 된다.
[백준] 11404번 - 플로이드
모든 도시의 쌍과 관련된 최솟값을 구하는 문제이다.그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구해야 하므로,플로이드-워셜 알고리즘을 통해 해결하면 된다.플로이드-워셜 알고리즘은 다음과 같다.DS = Math.min(DS, DS + DK)DS는
[백준] 1219번 - 오민식의 고민
벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제이다. 기존 벨만-포드는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야한다. 또한 돈을 무
[백준] 11657번 - 타임머신
시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 점이다. 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하
[백준] 1854번 - K번째 최단경로 찾기
시작점과 도착점이 주어지고 해당 목적지까지 가는 K번째 최단경로를 구하는 문제이다.K번째 최단 경로를 해결하기 위해서는 다음과 같은 아이디어로 접근하면 된다.최단 경로를 표현하는 리스트를 K개의 row를 갖는 2차원 리스트의 형태로 변경하고자 한다. 이렇게 하면 최단
[백준] 1916번 - 최소비용 구하기
시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 다익스트라 알고리즘을 통해 해결 할 수 있다.
[백준] 1753번 - 최단경로
시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로, 다익스트라 알고리즘의 가장 기본적인 문제이다.따라서 다음과 같은 매커니즘을 통해 시작점으로 부터 각각의 노드까지의 최단거리를 구하면 된다.인접 리스트로 그래프 구현하기주어진 노드들 간의 연결을 인접리스트를 이용하