# backjoon
[백준] 11505번 - 구간 곱 구하기
문제 분석 이 문제를 풀기에 앞서 다음과 같은 개념이 필요하다. >(AB) % C == (A%C)(B%C) % C 위의 개념을 인지하며, 세그 먼트 트리를 이용해 풀면된다. 소스 코드
[백준] 10868번 - 최솟값
문제 분석 세그 먼트 트리의 개념을 이용해서, 원하는 구간의 최솟값을 구할 수 있다. 주어지는 N개의 값들을 리프노드에 저장하고, 최솟값을 만족하도록 위로 올라오면서, 최솟값 트리의 형태로 만들어준다. 그 후, 원하는 구간을 찾아 올라오면서 최솟값을 얻어내면 된다. 소스 코드
[백준] 2042번 - 구간 합 구하기
문제 분석 해당 문제에서는 데이터 변경이 일어나므로, 데이터 변경시에 시간이 많이 소요되는 합 배열로는 풀 수 없다. 따라서, 세그먼트 트리의 개념을 이용해서 풀면된다. 세그 먼트 트리란 💡 구간 합, 최소 , 최대 구하는 경우에 사용될 수 있다. 다음의 3단계로 진행된다. 트리 초기화 질의 값 구하기 데이터 업데이트 하기 트리 초기화 💡 2k ≥ N을 만족하는 k의 최솟값을 구한 후 (2k)*2를 트리 리스트의 크기로 정하면 된다. 예를 들어, 8개의 데이터가 존재한다고 할때, k=3 이 되며 16크기의 리스트를 만들면 된다. 이후, 만든 트리 리스트의 2^k번째 인덱스 부터 N개의 데이터를 차례대
Backjoon_2751 문자와 문자열_Python풀이
[수 정렬하기2] [문제] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. [입력] 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. [출력] 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. [TestCase] [입력] 5 5 4 3 2 1 [출력] 1 2 3 4 5 [알고리즘 분류] 정렬
[백준] 1991번 - 트리 순회
문제 분석 문제에서 주어진 노드간의 관계를 트리 형태의 자료구조에 적절하게 저장하고, 그 안에서 탐색을 수행하면 된다. 따라서 인접리스트의 형태로 트리의 관계를 표현하고, 재귀함수를 통해 탐색을 수행하여 문제를 해결하면된다. 소스 코드
[백준] 14425번 - 문자열 집합
문제 분석 집합 S에 속해 있는 단어들을 이용해 트라이 구조를 생성하고, 트라이 검색을 이용해 문자열 M개의 포함 여부를 카운트하는 전형적인 트라이 자료구조 문제이다. 소스 코드
Backjoon_27866 문자와 문자열_Python풀이
문자와 문자열 [문제] 단어 S와 정수 i가 주어졌을 때, S의 i번째 글자를 출력하는 프로그램을 작성하시오. [입력] 첫째 줄에 영어 소문자와 대문자로만 이루어진 단어 S가 주어진다. 단어의 길이는 최대 1,000이다. 둘째 줄에 정수 i가 주어진다. (1 <= i <= |S|) [출력] S의 i번째 글자를 출력한다. [TastCase] [입력] Sprout 3 [출력] r [알고리즘 분류] 구현 문자열 [알아두면 좋은 정보] Python은 문자열을 index로 접근 가능하다.
[백준] 1068번 - 트리
문제 분석 트리의 관계를 인접리스트로 표현하고, DFS를 통해 부모-자식의 관계를 설정하여 표현할 수 있다. 따라서 DFS 및 visited배열을 통해 주어진 입력대로 관계를 설정하고 풀어나가면 된다. 소스 코드
[백준] 11725번 - 트리의 부모 찾기
문제 분석 트리를 어떻게 구조화 할지에 대한 문제이다. 인접리스트로 트리의 구조를 만들어보고, DFS를 통해 비교해가면서, 부모노드의 번호를 저장해주면 된다. 이때 트리의 루트 노드가 1이라고 주어져 있으므로, 1번 부터 DFS를 진행하면 된다. 소스 코드
[백준] 1414번 - 불우이웃돕기
문제 분석 인접 행렬의 형태로 데이터가 들어오기 때문에 이 부분을 최소 신장 트리가 가능한 형태로 변형하는 것이 필요하다. 먼저 문자열로 주어진 랜선의 길이를 숫자로 변형해 랜선의 총합을 저장한다. 이때 i와 j가 같은 곳의 값은 같은 컴퓨터를 연결한다는 의미이므로 별도 에지로 저장하지 않고 나머지 위치의 값들을 i->j로 가는 에지로 생성하고, 에지리스트에 저장하여 최소 신장 트리로 해결하며 된다. 즉, 총 나올수 있는 랜선의 길이 - 최소로 가능한 랜선의 길이 를 통해 문제를 해결하면 된다. 소스 코드
[백준] 17472번 - 다리 만들기 2
문제 분석 문제에서 주어진 N과 M의 크기가 매우 작은 편이라 시간 복잡도에 제약은 크지 않다. 문제를 해결하기 위해서는 먼저 주어진 지도에서 섬으로 표현된 값을 각각의 섬마다 다르게 표현하는 과정이 필요하다. 이후에는 각 섬의 모든 위치에서 다른 섬으로 연결할 수 있는 에지가 있는지 확인하고 우선순위큐에 해당 거리를 기준으로 오름차순하여 에지 리스트의 형태로 저장한다. 마지막으로는 유니온파인드와 연결하여, 최소신장트리를 활용해 문제를 해결할 수 있다. 이때 최소신장트리에서는 에지의 개수는 '노드-1' 이 될때 까지 반복한다. (
[백준] 1197번 - 최소 스패닝 트리
문제 분석 최소 신장 트리를 묻고 있는 문제로, 최소 신장 트리를 구하여 해결하면 된다. 최소 신장 트리의 특징 💡 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로, 사이클을 포함하지 않는다. N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 개다. 최소 신장 트리의 핵심 이론 💡 1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기 최소 신장 트리는 데이터를 노드가 아닌 에지 중심으로 저장하므로 인접 리스트가 아닌 에지리스트의 형태로 저장한다. 이 리스트는 일반적으로 노드 변수 2개와 가중치 변수로 구성된다. 또한, 사이클 처리를 위한
[백준] 1389번 - 케빈 베이컨의 6단계 법칙
문제 분석 사람들을 각각 노드로 봤을 때, 각각의 노드에서 여러 노드로 가는 최소값을 구해주고 이러한 값들을 더해준 후, 비교하면 되므로, 플로이드-워셜 알고리즘을 통해 해결하면 된다. 소스 코드
[백준] 11403번 - 경로 찾기
문제 분석 모든 노드 쌍에 관해 경로가 있는 지에 대해 묻고 있으므로, 플로이드워셜 알고리즘을 통해 문제를 풀면 된다. 소스 코드
[백준] 11404번 - 플로이드
문제 분석 모든 도시의 쌍과 관련된 최솟값을 구하는 문제이다. 그래프에서 시작점을 지정하지 않고, 모든 노드와 관련된 최소 경로를 구해야 하므로, 플로이드-워셜 알고리즘을 통해 해결하면 된다. 플로이드-워셜 알고리즘은 다음과 같다. 😊플로이드 워셜 💡 ✅ 최단 경로 탐색 ✅ 음수 가중치 허용 ✅ 동적 계획법의 원리 이용 😊플로이드 워셜의 핵심이론 💡 플로이드-워셜 알고리즘 의 핵심적인 원리 A노드에서 B 노드까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로이다. > DS = M
[백준] 1219번 - 오민식의 고민
문제 분석 벨만-포드 알고리즘의 원리를 바탕으로 요구사항에 따라 내부 로직을 바꿔야 하는 문제이다. 기존 벨만-포드는 최단 거리를 구하는 알고리즘이지만, 이 문제에서는 도착 도시에 도착할 때 돈의 액수를 최대로 하고 싶기 때문에 업데이트 방식을 반대로 변경해야한다. 또한 돈을 무한히 많이 버는 케이스가 있다고 하는 것을 바탕으로 음수 사이클이 아닌 양수 사이클을 찾도록 변경이 필요하다. 마지막으로 예외처리가 1개 필요한데, 양수 사이클이 있어도 출발 노드에서 이 양수 사이클을 이용해 도착 도시에 가지 못하는 경우이다. 즉, 양수 사이클에 도착노드가 없는 경우이다. 이 부분을 해결하기 위해 에지의 업데이트를 N-1번이 아닌, 충분히 큰 수만큼 추가로 돌리면서, 업데이트를 수행하도록 하였다.
[백준] 11657번 - 타임머신
문제 분석 시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0 또는 음수가 가능하다는 점이다. 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포드 알고리즘을 사용하면 된다. 다음은 벨만 포드 알고리즘과 관련된 원리에 대한 설명이다. 벨만-포드 알고리즘은 다음 3가지 단계의 원리로 동작한다. 💡 1단계 : 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기 : 주어진 경로를 에지 리스트의 형태로 설계하고, 최단 경로 리스트를 초기화 한다. 이때, 최단 경로 리스트에서 시작 노드의 번
[백준] 1854번 - K번째 최단경로 찾기
문제 분석 시작점과 도착점이 주어지고 해당 목적지까지 가는 K번째 최단경로를 구하는 문제이다. K번째 최단 경로를 해결하기 위해서는 다음과 같은 아이디어로 접근하면 된다. > 1. `최단 경로를 표현하는 리스트를 K개의 row를 갖는 2차원 리스트의 형태로 변경하고자 한다. 이렇게 하면 최단 경로뿐만 아니라 최단 경로 ~ K번째 최단 경로까지 표현할 수 있다.` > 2. 기존 다익스트라 로직에서 사용한 노드를 방문 리스트에 체크해 두고 다음 도착 시 해당 노드를 다시 사용하지 않도록 설정하는 부분은 삭제가 필요하다. k번째 경로를 찾기 위해서는 노드를 여러번 쓰는 경우가 생기기 때문이다. 또한 추가로, 최단 거리 리스트를 채우는 경우에는 다음과 같은 규칙을 적용하여 채우면 된다. > 1. `
[백준] 1916번 - 최소비용 구하기
문제 분석 시작점과 도착점이 주어지고, 이 목적지까지 가는 최소 비용(최단거리)를 구하는 문제이다. 또한 버스 비용의 범위가 음수가 아니기 때문에 다익스트라 알고리즘을 통해 해결 할 수 있다. 소스 코드
[백준] 1753번 - 최단경로
문제 분석 시작점과 다른 노드와 관련된 최단 거리를 구하는 문제로, 다익스트라 알고리즘의 가장 기본적인 문제이다. 따라서 다음과 같은 매커니즘을 통해 시작점으로 부터 각각의 노드까지의 최단거리를 구하면 된다. > 1. 인접 리스트로 그래프 구현하기 > 주어진 노드들 간의 연결을 인접리스트를 이용하여 표현해준다. > 2. 최단 거리 리스트 초기화 하기 > 최단 거리 리스트를 만들고 출발 노드의 인덱스에 해당하는 곳의 값은 0, 이외의 인덱스의 값들은 무한 으로 초기화 한다. > 3. 값이 가장 작은 노드 고르기 > 최단 거리 리스트에서 현재 값이 가장 작은 노드를 고른다. > 4. 최단 거리 리스트 업데이트 하기 > 선택된 노드의 연결된 에지의 값을 바탕으로 다른