백준
1.백준 1026번 : 보물 (Python)
백준 문제 링크 위 글자를 클릭하면 해당 문제의 내용을 읽을 수 있다. 문제를 읽던 도중 "S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다." 이런 문구가 나와서 정렬을 어떻게 해야할지 고민을 했는데 예제 입출력을 보고 굳이 B에 있는 수를 재배열 하지 않아도 된다고 생각했다. 어쨌든 두 수의 곱...
2.백준 2776번 : 암기왕 (Python)
본문 링크 > 📌 이분탐색의 시작점과 끝점을 어떻게 잡을 것인가? 이분탐색에서 가장 먼저 생각해야할 부분은 바로 시작점과 끝점 이라고 생각한다. 처음 주어진 리스트는 숫자의 목록만 있을뿐 숫자의 범위는 주어지지 않기 때문에 L1 리스트 자체를 숫자의 범위라고 생각했다. 최소값을 0이아니라 L1[0]의 값을 , 최대값을 임의의 큰 수가 아니라 L1[-...
3.백준 2792번 : 보석상자 (Python)
본문 링크 처음에 문제를 이해했지만 어떻게 시작할지 많이 고민했다. 이분탐색 문제를 풀때 출발점은 시작점과 어떻게 끝점을 잡을것인가? 를 먼저 생각하는 것이다. 이것은 금방 해결할 수 있었는데 문제는 어떻게 탐색할것인가? 였다. > 📌 KeyPoint: 보석을 동일한 개수로 최대한 많은 인원에게 나누어 줘야 개인이 가지는 보석의 수가 최소화된다. 이...
4.백준 16401 : 과자 나눠주기 (Python)
본문 링크 > 📌 시작점과 끝점을 어떻게 잡을것인가? 처음에는 `1 ≤ L1, L2, ..., LN ≤ 1,000,000,000` 범위를 따라서 1부터 1,000,000,000로 정했으나 , 최대값은 리스트의 max값으로 설정해도 충분하다. > 📌 어떻게 탐색할 것인가? start=1 , end=max(L)로 잡은뒤 , count 변수를 선언해...
5.백준 16564 : 히오스 프로게이머 (Python)
본문 링크 > 📌 최대 팀 목표레벨을 어떻게 구할 것인가? 문제에서 핵심적으로 물어보는 내용은 최대 팀 목표 레벨을 구하는 것이다. 하지만 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K의 범위는 (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000) 이다. 시간복잡도 O(n^2)과 같은 풀이로 시도하면 시간 초과가 발생할수 있기...
6.백준 2467 : 용액 (Python)
본문 링크 > 📌 특성값이 0에 가장 가까운 용액을 만들어내는 경우를 어떻게 찾을것인가? 먼저 N의 범위는 (2 > ❓ 어떻게 투 포인터를 적용할 것인가? 먼저 리스트 L을 정렬시킨다. start는 리스트의 시작점 , end는 리스트의 마지막점으로 잡는다. 만약 L[start]+L[end]의 합이 0보다 작다면 start값을 증가시킨다. 왜냐하면 ...
7.백준 1940 : 주몽 (Python)
본문 링크 >📌 만들수 있는 갑옷의 개수를 어떻게 구할 것인가? 아주 기초적이고 전형적인 투 포인터 문제이다. 정렬된 리스트에서 start=0 , end=N-1로 잡고 두 수의 합이 M과 같으면 count 변수에 1을 더해준다. 만약 M보다 작다면 start를 증가시키고 M보다 크다면 end를 감소 시킨다. >✅ 코드에서 중요한 부분 리스트는 정렬...
8.백준 2018 : 수들의 합 5 (Python)
본문 링크 > 📌 N을 연속된 자연수의 합으로 나타내는 경우의 수를 어떻게 구할 것인가? 투 포인터로 풀 수 있다. total 값을 정해두고 만약 total이 N보다 크면 start를 증가 시킨후 total 값을 감소한다. 만약 N보다 작으면 end 값을 증가시킨후 total 값을 증가시킨다. 예시로 N=6일때 1+2 까지 더했다면 total=3 ...
9.백준 9024 : 두 수의 합 (Python)
본문링크 🔑 『나의 코드』 🔑 『다른사람의 코드』 >📌 K에 가장 가까운 두수의 합을 어떻게 구할것인가? 이 문제는 이분탐색&투 포인터 문제이다. 나는 '두 수의 합' 이라는 문장때문에 투포인터를 사용하였으나 이분탐색으로도 가능합니다. 투 포인터 코드에 대해 설명만 하겠습니다. K의 가장 가까운 두 수의 합을 찾기 위해서는 `K-두 수` 의 ...
10.백준 3151 : 합이 0 (Python)
본문 링크 🔑『처음 시도했지만 틀렸던 코드』 🔑『수정한 코드』 > 📌 어떻게 3명의 합이 0인 지접을 찾을 것인가? 삼분탐색도 가능할꺼같으나 N의 범위가 1 ≤ N ≤ 10000 이기 때문에 반복문으로 1부터 N까지 돌린다음에 매개변수를 2개를 사용하여 투 포인터를 사용했다. 처음에는 문제가 아주 평범하게 느껴져서 일반적인 투 포인터 알고리즘...
11.백준 12099 : 점심메뉴 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 먼저 문제에서 주어지는 수의 범위를 보자. 1 ≤ N ≤ 10만 , 1 ≤ Q ≤ 5000 이다. 이 범위를 완전탐색을 통해 풀기에는 시간이 매우 많이 소모된다. 따라서 이분탐색을 사용하기로 했다. >📌 이분탐색을 어떻게 할것인가? 이분탐색은 어떤 조건을 만족하는 x의 최대 , 최소값을 구할 때 쓰인다...
12.백준 3649 : 로봇 프로젝트 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 문제 자체는 되게 쉽지만 n의 범위는 0 ≤ n ≤ 1000000 이다. 완전탐색으로 풀기에는 매우 오래 걸리기 때문에 투 포인터를 사용하였다. >📌 어떻게 투 포인터를 사용할 것인가? 먼저 리스트 L을 정렬해준후 , start=0 ; end=T-1로 잡은후 L[start]+L[end]값이 x보다 크면 en...
13.백준 16434 : 드래곤 앤 던전 (Python)
본문 링크 > 📌 어떻게 문제에 접근할 것인가? 문제자체는 길어보이지만 내용은 쉽다. 초기 용사의 공격력과 던전의 수가 주어졌을때 턴제게임처럼 용사가 먼저 때린 후 , 몬스터가 용사를 때린다. 그리고 체력이 먼저 `0 이 되는사림이 진다. 이때 던전을 깰수있는 최소 HP` 를 구하는 것이다. 하지만 하나같이 문제에서 주어지는 변수의 범위가 괴랄하다....
14.백준 17951 : 흩날리는 시험지 속에서 내 평점이 느껴진거야 (Python)
본문 링크 >📌 어떻게 현수가 받을 수 있는 최대 점수를 구할것인가? 문제에서 주어진 변수의 범위는 K , N (1 ≤ K ≤ N ≤ 10^5) 이다. 하지만 이를 완전탐색으로 풀기에는 시간이 너무 오래걸리기 때문에 이분 탐색을 통해 풀이하고자 한다. >📌 어떻게 탐색할것인가? 이분탐색의 mid값을 현수가 받을수 있는 점수로 설정한다. 그리고 리...
15.백준 20444 : 색종이와 가위 (Python)
본문링크 >📌 어떻게 접근할 것인가? 문제에서 정수 `n, k 가 (1 ≤ n ≤ 2^31-1, 1 ≤ k ≤ 2^63-1)` 이다. 이렇게 큰 범위를 완전탐색으로 풀기에는 시간이 너무 오래걸리기 때문에 이분탐색을 통해 접근해보았다. 먼저 가위질을 하면서 나오는 경우의 수를 직접 시뮬레이션 해서 구해보았다. 7번 가위질 - `( 8 , 14 , 1...
16.백준 20917 : 사회적 거리 두기 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 먼저 문제에서 주어지는 범위를 보면 `1 ≤ T ≤ 10 , 2 ≤ s ≤ n ≤ 200,000` 이다. 즉 완전탐색처럼 `O(N^2)` 으로 풀면 시간초과가 난다. 문제에서 가장 가까운 두 좌석의 거리의 최대값을 구하고자 하므로 이분탐색을 사용하도록 한다. >📌 어떻게 이분탐색할것인가? 일단 리스트를 ...
17.백준 23829 : 인물예술탐사주간 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 문제 자체는 쉽다. Q지점에서 사진을 찍었을때 모든 나무의 위치에다가 Q지점을 뺀 절대값을 구하면 된다. 예제입출력을 보면 입력 5 2 1 3 7 9 10 4 12 출력 18 30 태영이가 $i$ 번째로 사진을 찍은 위치 $X_i$ 보자. 4일때는 `(4-1) + (4-3) + (7-4) + (9-4) +...
18.백준 23830 : 제기차기 (Python)
본문 링크 >📌 문제를 어떻게 접근할 것인가? 제기차기 점수의 합이 $S$ 점 이상인지 확인하는 문제이다. 다만 어떤 학생의 제기차기 점수가 $K+r$ 초과라면 그 학생의 점수에서 $p$ 를 빼고 제기차기 점수이 $K$ 미만이라면 그 학생의 점수에 $q$ 를 더한다. 이때 $S$ 점을 넘는 $K$ 의 최소값을 구한다. 문제 조건을 보면 아래와 같다...
19.백준 23978 : 급상승 (Python)
본문 링크 >📌 문제에 어떻게 접근할 것인가? 먼저 예제입출력을 보자 입력 3 10 1 2 4 출력 3 $X$ 가 3일때 `3 3 2 3 2 1 0` 으로 총 14원이 만들어진다. 이를 점화식을 만들어보면 수학공식을 통해 n부터 m까지의 합 S=(n+m) X (m-n+1)//2_ 과 1부터 n까지의 합 S= n X (n+1)//2_ 을 사용해서...
20.백준 2473 : 세 용액 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 어떤 리스트를 주어졌을때 세수의 합이 0 에 가장 가까운 것을 찾는 문제이다. 두 용액이나 용액 문제를 풀었다면 이 문제는 투 포인터를 사용하여 풀 수 있다는 것을 알것이다. 하지만 세 수의 합은 어떻게 구할까? 문제 조건에서 보면 $N$은 3 이상 5,000 이하의 정수이다. 반복문으로 리스트 한 값을 잡고...
21.백준 11728 : 배열 합치기 (Python)
본문 링크 투 포인터 힙 정렬 >📌 어떻게 문제에 접근할 것인가? 문제는 간단하게 두 배열을 합한후 정렬하는 것이다. 하지만 범위가 $1 ≤ N, M ≤ 1,000,000$ 이므로 그냥 `sort` 를 해버리면 시간초과가 나버린다. 따라서 투포인터와 힙 정렬을 사용하였다. 먼저 투 포인터에서는 `a=b=0 으로 잡아준후 A[a] 와 B[b] 값...
22.백준 9728 : Pair sum (Python)
본문 링크 >📌 어떻게 풀것인가? 리스트가 주어졌을때 두 수의 합이 $M$과 같은 경우의 수를 찾는 문제이다. 아주 전형적인 투 포인터 문제이다. `start=0 , end=N-1 , count=0 으로 잡고 두 수의 합이 M보다 크다면 end` 를 감소시키고 작다면 `start 를 증가시킨다. 만약 두 수의 합이 $M$ 과 같다면 start 와 co...
23.백준 17609 : 회문 (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? 유사 회문을 찾기 위해서는 문자열을 결국 전부 탐색하는 수밖에없다. 하지만 문자열의 길이는 3 이상 100,000 이하이므로 $O(N)$ 으로 해결가능한 방법이있을까? 투 포인터를 사용한다면 가능하다. 매번 문자열 하나를 지우면서 하나하나 확인하는것보다 투 포인터를 사용해 같은 문자를 최대한 지운 후 유...
24.백준 20922 : 겹치는 건 싫어 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 같은 원소가 $K$ 이하인 최장 연속 부분 수열을 구하는 문제이다. 문제에서 주어지는 범위를 보면 $N$의 범위가 ($1 \le N \le 200\,000$) 이다. 따라서 이 문제는 가능하면 $O(N)$ 이하로 풀어야지 시간초과가 나지않는다. 따라서 모든 수를 탐색하고 $O(N)$으로 탐색가능한 투 포인터...
25.백준 2230 : 수 고르기 (Python)
본문 링크 > 📌 어떻게 문제에 접근할 것인가? 두 수의 차이가 $M$ 이상이면서 제일 작은 값을 찾는 문제이다. $N$ 의 범위를 보면 $1 ≤ N ≤ 100,000$ 이고 두 수의 차이를 묻는 문제이기 때문에 $O(N)$ 으로 탐색가능한 투 포인터를 사용하였다. >📌 투 포인터를 어떻게 사용할 것인가? 먼저 리스트 $L$ 을 입력받고 정렬해...
26.백준 17799 : Feeding Seals (Python)
본문 링크 > 📌 어떻게 문제에 접근할 것인가? 문제에서 $N,C$ 가 주어진다. $N$ 은 배열의 길이 $C$ 는 한사람이 최대 나를수있는 크기이다. 단 한번에 최소 1개부터 최대 2개를 운반할수있다. 예제 입출력을 보자. 입력 4 100 44 35 66 67 출력 3 (35+44) , 66 , 67 총 3번의 횟수가 필요하다. 그럼 가장 작은...
27.백준 6137 : 문자열 생성 (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? $S$ 라는 문자열이 주어졌을때 매번 왼쪽끝과 오른쪽끝 문자 중 하나를 $T$ 문자의 끝에 붙인다. 이때 $T$ 가 사전순으로 가장 빠른 문자열을 만드는 문제이다. 이떄 `CDBC` 라는 문자를 보자. 여기서 묻고자 하는것은 왼쪽끝과 오른쪽 끝 문자가 같을때 어떤문자를 $T$ 문자에 붙일것인가? 이다....
28.백준 1253 : 좋다 (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? $N$ 개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. $N$ 개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 이 문장을 보자마자 투 포인터 문제임을 확신할 수 있었다. 두 수의...
29.백준 2579 : 계단오르기 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 3가지 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. $DP$ 를 사용해 풀었다. 첫번째부터 네번째 계단을 올라가는 경우를 생각하자. $DP[1]=L[...
30.백준 4158 : CD (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? 문제는 간단하다. 상근이와 선영이가 가지고 있는 공통된 CD 의 개수를 구하는 문제이다. 다만 문제에서 주어지는 $N,M$ 의 범위는 $1≤N,M ≤1,000,000$ 이다. 즉 $O(N^2)$ 으로 완전탐색을 하면 시간초과가 난다. 따라서 모든 리스트를 $O(N)$ 으로 탐색가능한 투 포인터를 사용하기...
31.백준 25916 : 싫은데요 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 연속으로 막을수 있는 구멍의 최대값을 찾는 문제이다. 누적합으로도 풀수있을것같으나 좀더 익숙한 투 포인터로 풀기로 했다. >📌 어떻게 투 포인터를 적용할 것인가? `start 와 end 를 1 로 잡는다. 만약 햄스터가 오른쪽 구멍을 막을 수 있으면 end` 값을 증가시킨다. 그렇지 않으면 `start` 값...
32.백준 24416 : 알고리즘 수업 - 피보나치 수 1 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 아주 기본적인 피보나치 수 구하는 문제이다. 다만 시작 dp 값은 1,1이고 N-2 값도 함께 출력해야한다.
33.백준 9148 : 신나는 함수 실행 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 문제 그대로 코드를 구현하면 된다. 다만 재귀를 통해 함수가 작동하므로 메모제이션 방법을 사용해야한다. 그대로 구현하면 시간초과가 나니깐 주의하자. `dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]` 로 3차원 배열을 잡고 만약 이미 방문했다면 `return...
34.백준 1912 : 연속합 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 연속한 어떤 수들의 합중 가장 큰 값을 구하는 문제이다. 아주 기초적인 $DP$ 문제라고 느껴졌다. $DP$ 배열을 입력받고 `DP[i]는 DP[i]와 DP[i-1]+DP[i]` 값중 더 큰 값을 가지도록 한다. 즉 음수인 값은 알아서 뛰어넘게 되고 양수끼리만 더하게 된다. 이후 양수끼리만 더해진 값들의 ...
35.백준 1788 : 피보나치 수의 확장 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 피보나치 수에 새로운 규칙을 적용한 문제이다. 바로 $F(n)$ 이라는 피보나치 값이 있을때 $n$ 이 음수일때도 구하는 문제이다. `F(1)=F(0)+F(-1) 이고 이는 F(-1)=F(1)-F(0)` 로 나타낼수있다. 이것을 점화식으로 바꾸면 `F(-N) =F(-N+2)-F(-N+1)` 이다. 따라서 $N$...
36.백준 2491 : 수열 (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? _**가장 긴 증가하는 수열과 가장 긴 감소하는 수열값중 더 큰 값을 구하는 문제이다. $dp$ 배열을 만들어 주고 0 으로 초기화 해준다. 만약 값이 증가하면 $dp$$up$ 배열에 이전값과 1 을 더한값을 넣어준다. 이전값이 0 보다 크면 연속해서 증가하고 있다는 의미이다. 반대로 $dp$$down...
37.백준 11051 : 이항 계수 2 (Python)
본문 링크 >📌 문제에 어떻게 접근할 것인가? 단순히 이항계수 $nCk$ 값을 구하는 문제이다. 이때 $nCk$ 값은 $n!/k!(n-k)!$ 으로 나타낼 수 있다. 굳이 여러번 팩토리얼 값을 구하지말고 리스트 `L` 을 만들어 주어서 1000 까지 팩토리얼 값을 미리 만들어 준다. 그리고 $n!$ 값과 $k!$ , $(n-k)!$ 값을 리스트에서...
38.백준 11726 : 2xn 타일링 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 이런문제는 일단 최소 n=5 일때까지 시뮬레이션을 직접 돌려봐야한다. 그러면 `[1,2,3,5,8]` 이라는 값이 나올텐데 유심히 보면 피보나치 수와 같은 원리이다. 이 문제를 처음부터 보자말자 피보나치라는걸 알아차린 사람은 없을것이다. 하지만 직접 경우를 구해보면 출제자의 의도를 알 수 있다. >✅ 코드...
39.백준 11727 : 2xn타일링 2 (Python)
본문 링크 >📌 어떻게 문제에 접근할 것인가? 혹시 2xn 타일링 1 문제를 풀지않았다면 먼저 풀고오기를 바란다. 2xn 타일링 1 본문 링크 n=5일때까지 시뮬레이션을 해보았을때 [1,3,5,11,21] 값이 나오는 것을 확인 할 수 있다. 일단 피보나치 값은 아니지만 증가하는 수열이다. 그렇다면 어떻게 증가할것인가? 2xn 타일링 1 문제...
40.백준 1092 : 배 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 크레인을 박스를 처리하는 시간의 최소값을 구하는 문제이다. 가만히 생각해보면 매번 크레인이 들수있는 가장 큰 박스를 처리하면 가장 빠르지않을까? 라는 아이디어가 떠올랐고 바로 구현해주었다. `Nlist 와 Mlist` 를 정렬해준다. 만약 가장 무거운 박스를 처리할수있는 크레인이 가장 무거운 박스보다 값이 작다...
41.백준 2565 : 전깃줄 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수를 출력하는 문제이다. 단순하게 생각하자면 왼쪽 전기줄을 정렬하면 왼쪽전기줄은 서로 엉킬일이 없어진다. 즉 오른쪽 전기줄만 신경쓰면된다. 따라서 왼쪽 전기줄을 정렬했을때 오른쪽 전기줄의 가장 긴 증가하는 부분수열의 길이 를 구하면 된다....
42.백준 11053 : 가장 긴 증가하는 부분 수열 (Python)
본문 링크 >📌어떻게 접근할 것인가? 다이나믹 프로그래밍 알고리즘 중에 유명한 $LIS : ( Longest Increasing Subsequence )$ 알고리즘 문제이다. 우리가 구하고자 하는 값은 부분 수열중 가장 긴 부분수열을 찾는 문제이다. 이중 반복문을 사용하여서 모든 리스트 값을 탐색한다. 이때 `L[i] > L[j] and dp[i]...
43.백준 11722 : 가장 긴 감소하는 부분 수열 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 가장 긴 증가하는 부분 수열 문제 와 아주 비슷한 문제이다. 가장 긴 증가하는 부분 수열 알고리즘에서 if 문을 조금 바꿔주면 해결된다. `if a[i]<a[j] and dp[i]<dp[j]` 가 가지는 의미는 부분수열이 감소하면서 이전의 감소한 횟수보다 큰가? 라는 의미이다. 예제 입출력을 보자. 입력 6...
44.백준 12015 : 가장 긴 증가하는 부분 수열 2 (python)
본문 링크 📌 이분탐색 코드 📌bisect 라이브러리 코드 >📌 어떻게 접근할 것인가? 이전의 가장 긴 증가하는 부분 수열 문제에서는 $O(N^2)$ 을 활용한 풀이방법을 사용했다. 하지만 이번에는 $N$ 의 범위가 $N (1 ≤ N ≤ 1,000,000)$ 이기때문에 $O(N^2)$ 알고리즘을 사용할수 없다. 따라서 이분탐색을 활용하여 $O...
45.백준 14002 : 가장 긴 증가하는 부분 수열 4 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 가장 긴 증가하는 부분 수열 알고리즘 이다. 하지만 특이한점은 가장 긴 증가하는 부분 수열을 출력한다는 점이다. 가장 긴 증가하는 부분 수열 2 시리즈의 2번째 문제에서는 $O(Nlog N)$ 으로 문제를 풀었지만 이 풀이방법은 가장 긴 증가하는 부분수열의 길이만 구할수있고 실제로 가장 긴 증가하는 부분 수열의...
46.백준 11054 : 가장 긴 바이토닉 부분 수열 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 가장 긴 증가하는 부분 수열 알고리즘을 활용한 문제이다. 바이토닉 부분수열은 증가하거나 감소하는 가장 긴 부분 수열의 길이를 구하는 문제이다. 간단하게 가장 긴 증가하는 부분 수열 알고리즘을 2번 적용시키면된다. 다만 이때 감소하는 부분수열의 길이는 원래 리스트를 역순으로 고친다음에 증가하는 부분 수열로 ...
47.백준 14003 : 가장 긴 증가하는 부분 수열 5 (Python)
본문 링크 >📌 어떻게 탐색할 것인가? 이 문제에서는 가장 긴 증가하는 부분수열의 길이와 그때의 배열을 구하는 문제이다. 이전 시리즈 문제에서 배열을 구할때에는 $O(NlogN)$ 으로 가장 긴 증가하는 부분수열이 길이만 구할수 있을 뿐 배열을 구할순 없기 때문에 $O(N^2)$ 의 알고리즘으로 배열을 구하였다. 하지만 문제에서 $N$ 의 범위는 ...
48.백준 2568 : 전깃줄 - 2 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 이전의 전깃줄 1 문제 를 풀어봤다면 접근방법은 간단하다. 왼쪽의 전깃줄을 정렬하고 오른쪽 전기줄의 최장 연속 길이 부분 수열을 구하는 알고리즘을 사용하면 된다. 다만 까다로운 점은 전깃줄의 개수가 최대 `100,000` 이므로 $O(Nlog N)$ 안에 해결해야한다. 또한 개수도 구하고 없에야하는 전기줄도...
49.백준 4781 : 사탕가게 (Python)
본문 링크 > 📌 어떻게 문제에 접근할 것인가? 단순히 배낭문제를 조금 활용한 문제이다. 물건의 칼로리와 가격이 주어졌을때 중복사용을 허용하여 만들수 있는 최대 칼로리 값이다. 다만 까다로운 점은 사탕의 중복사용이 가능하다는 점이고 문제에서 주어지는 수의 범위이다. $n,m-(1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00)$ $n$ ...
50.백준 11066 : 파일 합치기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이 문제는 혼자못풀정도로 어려운 난이도였다. 이해하기도 굉장히 어렵기 때문에 문제에서 주는 예제를 통해 이해를 해보고자 한다. 예제 입력을 보자 입력 4 40 30 30 50 출력 300 먼저 DP는 2차원 배열을 사용할 것이고, DPi는 i에서 j까지 합하는데 필요한 최소 비용이 된다. 또한 배열을 효율적...
51.백준 10986 : 나머지 합 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 단순 구간합 문제라고 생각했다. 하지만 2차원 배열을 사용하니 메모리 초과. 2중반복문을 사용하니 시간초과가 나왔다. 따라서 우리는 더 간단한 아이디어를 통해 문제를 접근하고자 한다. 먼저 누적합 배열을 만들어 보자. 예제 입력 5 3 1 2 3 1 2 그럼 $SUM=[0,1,3,6,7,9]$ 가 된다. 이...
52.백준 11660 : 구간합 구하기 5 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 처음엔 단순히 1차원 누적합처럼 풀었다가 틀렸다. 2차원적으로 누적합을 생각했을때 $dp$ 의 증가값은 $dpi=dpi+dpi-1-dpi-1+Li-1$ 이고 $x1,y1$ 부터 $x2,y2$ 까지의 합은 $dpx2-dpx1-1-dpx2+dpx1-1$ 가 올바른 식이 된다. 왜냐하면 3번째 그림의 겹치는 부...
53.백준 25682 : 체스판 다시 칠하기 2 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 2차원 $dp$ 배열을 만들어서 시작점이 $W$ 일때와 $B$ 일때 누적합을 구해준다. 이후 $K×K$ 크기만큼 배열을 탐색해서 누적합의 최소값을 찾는다. $dp$ 배열의 2차원 누적합은 $dpi+1=dpi+dpi+1-dpi+value$ 으로 계산해준다. 이때 `value` 는 체스판이 $color$ 와 같...
54.백준 1806 : 부분합 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 누적합 알고리즘을 공부중이라 일단 주어진 배열을 누적합으로 만들어 보았다. 연속된 수들의 합이 $S$ 이상일때 거리의 최소값을 구하는 문제이다. 이때 `3번째 인덱스와 4번째 인덱스의 합 5+10=15` 로써 거리가 2임을 알 수 있다. 가만히 보면 누적합 배열에서 `24-9=15` 가 됨을 확인 할 수 있...
55.백준 2143 : 두 배열의 합 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 오래 생각해봤는데 아무래도 가장 깔끔한 방법은 $dp1$ 배열과 $dp2$ 배열에 각각 모든 연속 부분수열을 넣는것이다. 이후 $dp2$ 배열을 정렬해서 `for i in range(len(dp1))` 과 정렬된 $dp2$ 값을 이분탐색해서 두 값의 합이 T 일때 경우의 수를 찾는것이다. 하지만 아주 까다로...
56.백준 2616 : 소형기관차 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 누적합과 다이나믹 프로그래밍을 섞은 문제였다. 누적합을 써야했다고 생각한 이유는 특정 연속수열의 합을 구할때 누적합 배열하나만 만들어놓으면 연속수열의 합을 매번 바로바로 구할수 있기 때문이다. 또한 다이나믹 프로그래밍을 써야만 했던 이유는 기관차의 최대 개수가 $50000$ 이기 때문에 $O(N^2)$ 풀이법으...
57.백준 2208 : 보석 줍기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이문제는 3가지 규칙이 존재한다. 보석을 줍다가 뒤로 돌아갈수 없다. 즉 연속적으로 보석을 주워야한다. 보석을 줍다가 멈추면 함정이 발생한다. 다만 보석을 $M$ 개 이상 주우면 함정이 발생하지 않는다. 보석을 가치를 최대로 되게끔 주운다. 문제에서는 보석의 개수와 $M$ 의 값 , 그리고 보석하나하나의 가...
58.백준 10800 : 컬러볼 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 문제를 풀면서 좀 오래 고민했다. 아이디어는 많이 떠올랐지만 문제에서 주어지는 $N$ $(1 ≤ N ≤ 200,000)$ 범위때문에 어떻게 최적화를 할지 고민했다. 누적합의 한가지 특성을 활용하기로 했다. 정렬되어있는 기존 배열과 그 배열의 누적합의 인덱스는 같다. 예를들어보면 $[3,6,10,15]$ 라...
59.백준 8933 : MCS (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 전형적인 슬라이딩 윈도우 문제이다. 처음에 문제가 이해가 되지않았는데 예제 입력에서 3 GCAGGAGCGCCAGG 위와 같은경우 경우의 수는 `["GCA" , "CAG" , "AGG" , "GGA" , "GAG" , "AGC" , "GCG" , "CGC" , "GCC" , "CCA" , "CAG" , "AG...
60.백준 13422 : 도둑 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제에서 M개의 연속된 집을 고르는 방법 이라는 조건이 주어졌을때 슬라이딩 윈도우를 사용할 생각을 했다. 그리고 까다로운 조건이 집은 원형을 이룬다는 것인데 단순하게 리스트 $L$ 에다가 $0$부터 $M$번째 인덱스를 `append` 해주면 1차원 배열으로 보나 원으로 보나 똑같이 모두 탐색 가능하게 된다....
61.백준 17081 : RPG Extreme (Python)
본문 링크 >📌 어떻게 접근할 것인가? 그냥 구현문제입니다. 처음엔 코드길이가 20000 B 이상 넘었는데 코드부분을 수정해서 8500 B 로 줄였습니다. 여라가지 고려해야할 사항들과 내가 푼 방법에 대해 이야기 해보도록 하겠습니다. 📌 1. 입력받기&변수 세로, 가로를 먼저 입력받습니다. 그래프를 입력받습니다. 이동 경로를 덱을 통해 입...
62.백준 14395 : 4연산 (Python)
본문 링크 >📌 어떻게 접근할 것인가? BFS 를 통해 탐색하였다. 다만 중요한것은 $s$ 와 $t$ 의 범위가 $(1 ≤ s, t ≤ 10^9)$ 이라는 점이다. 즉 중복체크를 위해 visit 방문배열을 만들면 메모리 초과가 발생한다. 따라서 $set$ 을 사용하기로 했다. $set$ 은 `if a in b` 를 실행할시 $O(1)$ ~ $O(...
63.백준 13023 : ABCDE (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 전형적인 $DFS$ 문제이다. 문제를 읽다가 처음에는 모든 친구들이 서로 연결되어있어야 하는 줄 알았다. 알고보니 5명 이상만 서로 연결되어있으면 된다. $DFS$ 매개변수에 `count` 변수를 만들어서 얼마나 깊이 탐색해주었는지 확인해준다. 만약 5명이상이라면 1을 출력하고 바로 코드를 종료해준다. 하지만...
64.백준 1189 : 컴백홈 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 그래프 탐색 문제이다. $DFS$ 를 통해 문제를 풀었다. 방문처리는 한번 왔던 지점에 $T$ 라는 벽을 새운후 백트래킹을 사용하여 재귀호출이 끝난뒤에 다시 빈칸으로 만들어주었다. 우리는 오른쪽위로 도착하면서 이동횟수가 K인 경우의 수를 구해야하기때문에 단순히 `visit=[ [False] × M for i ...
65.백준 24501 : blobaww (Python)
본문 링크 🔑 코드 1 🔑 코드 2 >📌 어떻게 접근할 것인가? 문제에서 원하는것은 $ESM$ 문자열의 경우의 수를 찾는것이다. 다만 주의해야할점은 문자열이 추가될때는 현재 문자에서 아래 또는 오른쪽방향으로만 추가해야한다. 예를들어 (1,1) + (2,2) + (3,3) 으로 문자열이 추가가 될수있지만 (1,1) + (2,2) +(2,1) 이런...
66.백준 3197 : 백조의 호수 (Python)
본문 링크 >📌 어떻게 접근할 것인가? BFS 문제지만 여러가지 생각해야할 점이 많습니다. 매번 모든 물에 대해서 얼음의 녹는것을 탐색한후 다시 백조가 서로 만날수있는지 탐색을 하면 시간초과가 납니다. 따라서 덱을 2개를 사용해야합니다. 그래프 값이 물이라서 주변에 얼음을 녹일 수 있다면 덱을 하나 추가로 만들어서 얼음이 녹은 지점의 좌표를 넣어줍...
67.백준 12920 : 평범한 배낭2 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 기본적인 배낭문제입니다. 단 한가지 다른점은 물건의 개수가 주어진다는 것입니다. 따라서 물건의 개수를 어떻게 처리할것인가? 에 대해 중심적으로 생각해야합니다. 물건의 종류 , 물건의 무게 , 물건의 개수를 모두 고려하게 되면 $O(NVK)$ 로 아주 많은 시간을 소비하게 됩니다. 시간을 줄이기 위하여 물...
68.백준 19951 : 태상이의 훈련소 생활 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 예제입력을 보면 과정은 어렵지 않은 문제이다. 다만 N,M 범위가 $1 ≤ N ≤ 100,000$ , $1 ≤ M ≤ 100,000$ 이라는 점이다. 즉 $O(N^2)$ 으로 풀이를 한다면 시간초과 발생한다. 총 $M$ 번의 흙을 옮기는 일을 한번에 할 수 없을까? >📌 첫번째 접근 먼저 누적합을 사용하였다...
69.백준 9372 : 상근이의 여행 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 기본적인 트리 문제이다. 다만 문제에서는 가장 적은 비행기를 타고 모든 국가를 여행하는 것이다. 이때 한번 탄 비행기는 여러번 탈 수 있기 때문에 트리를 그저 한번 순회 해준후에 트리의 크기를 구해주면된다. 트리 순회를 하기 위해서 $DFS$ 알고리즘을 사용하였다.
70.백준 9934 : 완전 이진 트리 (python)
본문 링크 >📌 어떻게 접근할 것인가? 중위 순회의 결과값을 보고 기존 트리를 구현하는문제이다. 문제 입력 예시를 잘 보면 가장 중앙값이 부모노드가 되고 다시 반으로 나누어서 그 반중에 가장 중앙값이 다시 부모노드가 된다. 따라서 노드의 높이를 저장하기 위해 2차원 배열 `answer` 을 선언해주고 분할정복처럼 `mid=(start+end)//...
71.백준 1068 : 트리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리가 주어졌을때 임의의 노드를 삭제시킨후에 리프노드의 개수를 구하는 문제이다. 간단하게 삭제하고자 하는 노드와 그 하위 노드들을 전부다 -2 로 처리해준다. 이후 트리의 크기를 전부 탐색하면서 삭제되지 않으면서 부모가 없는 , 리프노드인 값들의 개수를 출력해준다.
72.백준 1707 : 이분 그래프 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이분 그래프 판별 문제이다. `AtCoder Beginner Contest 282` 에도 이분그래프 문제가 나와서 이분 그래프 기초 문제를 풀었다. 일단 이분그래프가 무엇인지 부터 살펴보자. 이분 그래프는 인접한 정점들이 현재 정점과 색깔이 다르게 칠해서 모든 정점을 2가지의 색으로 칠할 수 있는 그래프이...
73.백준 5639 : 이진 검색 트리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리의 전위순회 결과를 후위순회한 결과를 출력하는 문제이다. $Tree$ 리스트를 입력받고 DFS 를 사용한다. 먼저 트리의 왼쪽노드를 우선탐색 해준다. 후위순회는 `왼쪽-오른쪽-루트` 순으로 탐색하기 때문에 전위순회에서 가장 작은값이 가장 왼쪽에 있으므로 가장 작은값을 찾은뒤에 이후 오른쪽 정점을 탐색한다...
74.백준 15900 : 나무 탈출 (Python)
본문 링크 ` > 📌 어떻게 접근할 것인가? 모든 리프토드에 말이 있고 서로 번갈아가면서 말을 부모 노드로 옮긴다. 이후 말이 루트노드에 도착하면 말은 사라지고 더이상 말을 옮길수 없는 사람이 지게된다. 여러번 시뮬레이션을 하다 보면 모든 리프노드에서 루트노드까지의 거리의 합이 홀수인지 짝수인지에 따라 결과가 정해진다. >📌 Code 단순히 ...
75.백준 14675 : 단절점과 단절선 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 일단 단절점과 단절선에 대해 알아보자. 단절점(cut vertex) : 해당 정점을 제거하였을 때, 그 정점이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 정점을 단절점이라 한다. 단절선(bridge) : 해당 간선을 제거하였을 때, 그 간선이 포함된 그래프가 2개 이상으로 나뉘는 경우, 이 간선을 단...
76.백준 15681 : 트리와 쿼리 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 다행히 문제에서 힌트가있어 설명이 아주 잘 되어있었다. 만약 정점의 수를 매번 쿼리마다 계산하면 시간초과가 난다. 따라서 `distance` 리스트를 선언하여 한번이 탐색으로 모든 정점의 수를 계산한다. 이런 트리가 있다고 해보자. 먼저 리프노드에 도착하면 리프노드의 값을 1로 초기화 한다. 이는 $DFS$ 탐...
77.백준 17073 : 나무 위의 빗물 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 문제를 잘 읽어보자. 루트노드부터 물을 흘려보내서 점점 아래로 물이 내려간다. 이때 가장 중요한 문장은 다음과 같다. 영훈이는 나무를 바라보면서 더 이상 물이 움직이지 않는 상태가 되었을 때 각 정점에 어느 정도의 물이 있게 될지 궁금해졌다. 즉 결국에는 물이 리프노드에만 존재하게 된다. 따라서 리프노드의 ...
78.백준 1240 : 노드사이의 거리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 서로 연결된 정점과 간선의 가중치가 주어졌을때 두 정점의 거리를 구하는 문제입니다. 단순히 $DFS$ 를 통해 구현했습니다. 다만 $Tree$ 를 입력받을때 서로 연결된 정점뿐만 아니라 가중치도 함께 넣어주고 방문 체크를 해주면서 $M$ 개의 쿼리에서 $a,b$ 두 지점이 같아질때까지 계속 탐색을 해줍니다. ...
79.백준 1967 : 트리의 지름 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리의 지름을 구하는 방법은 루트노드에서 가장 거리가 먼 지점 $x$ 를 구한뒤 트리의 $x$ 지점에서 거리가 가장 먼 $y$ 지점이 트리의 지름이 됩니다. 이것을 증명하기에는 너무 복잡하기도 하고 깔끔하게 정리하신 분이 있기 때문에 bedamino님의 블로그 를 참조하거나 귀류법으로 증명하신 구사과님의 블...
80.백준 7662 : 이중 우선순위 큐 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 최대값과 최소값을 찾기 위해서 우선순위 큐를 2개를 사용해야합니다. 하지만 중요한것은 특정 값을 제거할때 최대값 힙에서 값을 제거했다면 똑같이 최소값 힙에서도 값을 제거해줘야 한다는 점입니다. 따라서 방문 체크배열 `visit=[False]*K` 를 선언해준 후에 원소를 추가할때마다 `visit[j]=Tru...
81.백준 18870 : 좌표 압축 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제는 간단하다. 리스트 값이 주어질때 그 값보다 작은 값들의 개수를 구하면 된다. 예제입력을 보자. 5 2 4 -10 4 -9 이때 2보다 작은 값은 -10 , -9 이므로 개수는 2가된다. 4보다 작은 값은 2,-10,-0 이므로 개수는 3이된다. -10보다 작은값은 없으므로 개수는 0 이 된다. -9...
82.백준 4803 : 트리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 그래프가 주어졌을때 트리인지 아닌지 판별하는 문제입니다. 이 문제를 풀면서 `return` 에 대해 좀 더 깊게 공부했습니다. > 📌 첫번째 조건문 , if i==Previous 첫번째 조건문입니다. 왜 이런조건 사용했을까요? 일단 의미는 "이전 노드와 현재 노드가 같은가?" 입니다. 먼저 저희는 트리...
83.백준 4256 : 트리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 전위순회와 중위순회의 결과가 주어졌을때 후위순회를 출력하는 문제이다. 3 6 5 4 8 7 1 2 5 6 8 4 3 1 2 7 위와 같이 입력을 받았다고 하자. 첫번째가 전위순회 , 두번째가 중위순회이다. 전위순회에서 순서대로 탐색했을때 각 노드는 부모노드가 된다. 3은 6 7의 부모노드이고 6은 5...
84.백준 19542 : 전단지 돌리기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 처음에 문제를 보고 이해가 되지않았습니다. 만약 $D$ 가 1일때 거리가 1 인 노드들은 전단지를 던질수 있기 때문에 2에서는 전단지를 던져서 4로 갈 필요가없고 , 5에서는 전단지를 6으로 던져서 갈 필요가 없습니다. 따라서 거리가 $D$ 이상인 노드들에 대해 거리만 찾으면됩니다. 이를 수식화 하면 최소 ...
85.백준 20924 : 트리의 기둥과 가지 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이 문제는 문제를 잘 읽어보야아한다. 트리에 특수한 개념을 적용시켰다. 먼저 기가노트에 대해 알아보자. 기가노트란 처음으로 자식 노드가 $2$ 개 이상인 노드를 말한다. 따라서 기가노드는 $4$ 가 된다. 이때 주의해야할 점은** 기가노드가 존재하지 않을때 , 즉 한방향으로만 트리가 존재할때 리프노드를 기가...
86.백준 2263 : 트리의 순회 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제는 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 것이다. 블로그 - 이 분의 블로그를 참고하였는데 정말 깔끔하게 잘 설명해주셨다. 함수의 개형은 다음과 같다. 이때 중요한 것은 후위순회의 가장 끝부분은 루트라는 점이다. 위 순회를 안다면 루트의 값 알아낼 수 있고 중위 순회에서 그 루트 값 위...
87.백준 2250 : 트리의 높이와 너비 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제에서 원하고자 하는 값은 같은 행(가로줄) 에 존재하는 노드들의 인덱스 차이의 최대값 과 그때의 깊이를 구하는 것이다. 문제에서는 노드 4 와 7 이 깊이 3이고 인덱스 차이는 19-2+1=18 이다. 이때 인덱스 차이를 구할때 마지막에 1을 구해야한다. > 📌 그림에 숨겨진 요소 인덱스 차이를 구할...
88.백준 16437 : 양 구출 작전 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 예제 2번을 보자. 노드 5 - 2 - 1 로 올라가서 1100이 추가되고 노드 3 - 1 로 올라가서 100이 추가된다. 이때 노드 4 -1 에서 올라갈때는 늑대가 올라갈 필요는없으며 노드 7 - 6 으로 올라갈때 양은 늑대에게 전부 잡히므로 0 이 된다. 즉 이 문제는 리프노드부터 루트노드까지 역으로 ...
89.백준 24230 : 트리 색칠하기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제에서 중요한 점은 2가지이다. 하나의 정점에 색칠하면 해당 정점 아래 있는 모든 정점이 같은 색으로 칠해진다. 모든 정점을 칠할 수 있는 입력만 주어진다. 그리고 색칠을 최소한으로 색칠하기 위해서는 위에서 아래로 색칠해야한다. 따라서 종합적으로 생각해보면 루트노드에서 자식노드로 이동하면서 색칠해야하는 ...
90.백준 6597 : 트리 복구 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백준 4256 : 트리 와 똑같은 문제이다. 이전에 이 문제에 대해 글을 자세히 써놨다. 거의 똑같은 코드이지만 주의해야할 점은 입력 테스트 케이스의 수가 주어지지 않기 때문에 `try-except` 문법을 사용해야한다.
91.백준 9489 : 사촌 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 처음에 엄청 삽질을 한 문제이다. $Tree$ 를 입력받기 위해서 연속한 수끼리 부모-자식 관계가 되도록 배열도 3개씩 쓰고 겨우 구현했더니 사촌 노도를 찾는거에서 또 막혀버렸다. 다른사람의 풀이를 보니깐 굳이 복잡하게 생각할 필요도없고 리스트도 쓸 필요가없었다. > 📌 from collections im...
92.백준 18126 : 너구리 구구 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리의 아주 기초적인 문제이다. 트리 처음공부할떄 풀면 좋은 문제라고 생각이 든다. 문제에서 트리와 가중치가 주어졌을때 가중치의 최대값을 구하는 것이다. 먼저 $Tree$ 를 입력받을때 양방향이기 때문에 2번 append 해주고 가중치도 같이 넣어준다. 이후 visit 배열을 통해 방문 처리를 해준다. t...
93.백준 15805 : 트리 나라 관광 가이드 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리를 순회한 결과를 통해서 부모를 찾는 문제입니다. 잘 보면 **한번도 방문하지 않은 지점은 이전의 노드가 바로 부모노드입니다.** 따라서 $set$ 을 사용하여 중복처리를 합니다. 만약 처음방문하는 지점이라면 $dp$ 배열에다가 이전ㅇ 인덱스 값을 넣어줍니다. 이후 중복이 없는 $set$ 의 길이를 출...
94.백준 1595 : 북쪽나라의 도로 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 총 2번의 접근을 하였습니다. 처음에는 그냥 모든 노드들을 루트노드라고 생각해서 완전탐색을 했습니다. 하지만 시간초과가 발생했습니다. 두번째로는 리프노드에서만 출발을 하였습니다. 하지만 이것도 시간초과가 발생하였습니다. 문제에서 중요한 것은 거리가 가장 먼 두 도시 사이의 거리 입니다. 가만히 생각해보면 이...
95.백준 25516 : 거리가 k이하인 트리 노드에서 사과 수확하기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 트리의 $DFS$ 를 통해 풀었습니다. $DFS$ 의 매개변수에 level 을 추가함으로써 깊이를 측정해줍니다. 따라서 깊이가 $K$ 보다 작으면서 사과가 있는 노드라면 total 변수에 $1$ 을 추가해줍니다. 그리고 visit 배열을 통해 중복방문을 처리해줍니다. 문제에서 루트 노드는 $0$ 이라고 선언...
96.백준 21738 : 얼음깨기 펭귄 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이문제는 문제를 꼼꼼하게 읽어봐야한다. 문제에서는 총 2가지의 블록이 있다. 지지대 블록 일반 블록 지지대 블록은 트리 형식으로 다른 블록과 연결되어있다. 이때 문제에서 서로 다른 두 얼음을 연결하는 경로는 단 하나뿐이기 때문에 사이클이 없다. 즉 트리 그래프이다. 그리고 다음으로 얼음이 깨지는 조건이다...
97.백준 22856 : 트리 순회 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 잘 생각해보자. 문제에서 주어지는 그림에서 오로지 한방향으로만 이동하는 지점이 어디인가? 바로 중위순회의 끝 이다. 즉 항상 오른쪽으로 가는 지점에 대해서는 오로지 한번씩만 방문한다. 총 2번의 $DFS$ 를 사용하였다. 첫번째 $DFS$ 는 단순히 모든 노드들을 이동하면서 거리를 구한다. 두번째 $DF...
98.백준 1717 : 집합의 표현 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드 기초 문제입니다. 유니온 파인드 알고리즘에 대해서는 이전에 유니온 파인드 - Union Find 이 글에서 다뤘던 적이 있습니다. 일단 유니온 파인드를 수행하기 전에 배열을 만들고 모든 노드가 자신의 번호를 가르키도록 합니다. 이후 $Find$ 함수를 만들어 주고 $Union$ 함수도 만들어 줍...
99.백준 1976 : 여행 가자 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 전형적인 유니온 파인드 문제입니다. 유니온 파인드를 하기 전에 모든 노드들은 자기 번호를 가르키게 하고 i번째 줄의 j번째 수는 i번 도시와 j번 도시의 연결 정보를 의미한다. 에 맞게 $Union$ 을 잘 해주면됩니다. 그리고 마지막에 모든 여행장소의 최상위 노드가 같은지 확인해줍니다.
100.백준 4195 : 친구 네트워크 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드와 비슷하지만 다른점이 2가지가 있습니다. 정수가 아니라 문자열을 입력받는다 두 노드가 같은 집합인지가 아니라 관계의 수를 구한다. 일단 문제를 해결하기 위해서 2개의 딕셔너리를 사용하였습니다. parent 는 문자열 집합을 담당하고 number 은 관계의 수를 담당합니다.. $Find$ 함수...
101.백준 20040 : 사이클 게임 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드를 사용해 풀었습니다. 문제에서 구하고자 하는 것은 그래프가 사이클이 생기는지 체크하는겁니다. 중요한것은 유니온 파인드로 두 노드를 합칠때 , 먼저 두 노드의 최상위 부모를 찾은 뒤에 그것이 같으면 합칠시 사이클이 생기므로 먼저 Find(a) 와 Find(b) 가 같은지 확인해줍니다. 같다면 바...
102.백준 20955 : 민서의 응급 수술 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드를 통해 풀었습니다. 먼저 문제에서는 뉴런들을 붙이거나 잘라서 사이클없는 트리를 만드는 것이 목표입니다. 일단 먼저 문제에서 주어지는 뉴런의 연결 요소들을 유니온 파인드를 통해 연결해줍니다. 이때 사이클이 없어야 하므로 Find(a) 와 Find(b) 가 다를때만 연결합니다. 그렇다면 유니온 ...
103.백준 1043 : 거짓말 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 원래는 유니온 파인드 문제지만 문제에서 주어지는 입력값의 범위가 작아서 반복문을 여러개 사용해도 시간초과가 나지 않는다. 일단 진실을 아는 사람들의 집합을 입력받고 파티에 참석하는 사람들을 입력받는다. 이후 $M$ 번동안 파티에 대해서 진실을 아는 사람이 한명이상이라도 존재하는 경우 $dp[i]=True$ ...
104.백준 16562 : 친구비 (Python)
본문 링크 📌 내 풀이 📌 수정한 풀이 > 📌 어떻게 접근할 것인가? 일단 일반적인 유니온 파인드 코드로 구성하면 됩니다. 집합을 합치고 disjoint 배열 값에 따라서 친구비용의 최소값을 구해주었습니다. 다만 유니온 파인으로 집합을 합치는 과정에서 문제가 생겼습니다. 5 4 100 1 1 1 1 1 1 5 2 4 4 3 5 4 이런 입...
105.백준 10216 : Count Circle Groups (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 2차원 좌표에서 거리가 $R$ 일때 두 좌표가 같은지 확인하는 방법은 기하학적인 방법으로 찾을 수 있습니다. $math.sqrt((X1-X2)2+(Y1-Y2)2)<=R1+R2$ 이후 이 공식을 통해서 두 지점이 같은 범위에 속하는지 판별 한 후에 유니온 파인드 알고리즘을 사용하면됩니다.
106.백준 17352 : 여러분의 다리가 되어 드리겠습니다! (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드 기초 문제입니다. 먼저 원래는 모든 다리가 서로 연결되어있습니다. 다만 문제에서 어떤 다리 하나를 잘랐기 때문에 유니온 파인드를 사용하면 서로 다른 집합 2개가 발생합니다. 따라서 유니온 파인드를 실행 해준뒤에 check 라는 $set$ 을 만들어 주어서 서로 다른 집합 2개를 출력해줍니다.
107.백준 18116 : 로봇 조립 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드를 사용했습니다. 다만 문제에서 부품의 번호가 꼭 $N$ 이하이라는 조건이 없기 때문에 배열을 처음 만들때 $10^6+1$ 크기만큼 만들어 줍니다. 그리고 같은 부품의 개수도 빠르게 구하기 위해서 $dp=[1]*(10^6+1)$ 로 만들어 주고 $Union$ 할때마다 부품의 개수를 dp[b]+=d...
108.백준 7511 : 소셜 네트워킹 어플리케이션 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드 기초문제입니다. Find(A)==Find(B) 를 통해서 두 노드가 같은 집합인지 찾으면 됩니다. 유니온 파인드를 알고 있으면 문제에서 주어지는 그대로 구현하시면 됩니다. 마지막에 줄바꿈 문자를 위해 print() 를 넣어야합니다.
109.백준 24391 : 귀찮은 해강이 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드 기초 문제입니다. 문제에서 강의실 시간표가 주어졌을때 해강이가 밖에 나와야 하는 최소 횟수 를 구하는 것입니다. 유니온 파인드를 사용해서 , 새로운 강의가 나타났을때 다른 집합에 있다면 $+1$ 을 해주면 됩니다. 이는 으로 구현할 수 있습니다. 유니온 파인드를 구현해주고 강의실이 속한 ...
110.백준 17250 : 은하철도 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 유니온 파인드를 구현해주면 되는 문제입니다. 다만 문제에서 두 지점의 경로를 주어졌을때 바로 값을 출력해야합니다. 이는 $a$,$b$ 를 $Union$ 한 후에 print(dp[min(Find(a),Find(b))]) 를 사용하면 답을 출력할 수 있습니다. 또한 주의해야할 점은 같은 경로는 더해주면 안됩니...
111.백준 25187 : 고인물이 싫어요 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제에서 청정수를 얻을 수 있는지를 판별하는 것입니다. 청정수가 담긴 물탱크의 수가 고인물이 담긴 물탱크의 수보다 더 많은 경우 청정수를 얻을 수 있다. 유니온 파인드를 사용하여서 풀었습니다. 문제에서 청정수라면 $1$ , 고인물이라면 $0$ 을 주는데 유니온 파인드를 사용해서 배열의 값을 합쳐야 하기 때문...
112.백준 23324 : 어려운 모든 정점 쌍 최단 거리 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 일단 기본적으로 유니온 파인드를 사용해주었다. 다만 가중치가 1인 지점이 하나가 있는데 이는 $Union$ 을 사용하지 않았다. 왜냐하면 1-2 인 지점과 3-4-5 로 가는 지점 2개에 대해서 두 지점의 길이의 곱이 답이기 때문이다. 만약 예제 2처럼 가중치가 1인 두 노드의 최상위 부모가 같다면 사이클이...
113.백준 1197 : 최소 스패닝 트리 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 기초 문제입니다. 크리스칼 , 프림 알고리즘을 그대로 구현해주면 됩니다. 최소 스패닝 이론에 관한 글은 제가 쓴 블로그 를 참조하셔도 좋습니다.
114.백준 4386 : 별자리 만들기 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제입니다. 문제에서 별자리들의 $X$ , $Y$ 좌표만 주어졌기 때문에 먼저 모든 노드들 사이의 거리를 구해준 다음에 크루스칼 알고리즘과 프림 알고리즘을 사용하여 풀었습니다.
115.백준 1774 : 우주신과의 교감 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 전형적인 최소 스패닝 트리 문제입니다. 백준 4386번 과 비슷하게 구현해주시면됩니다. 다만 이미 존재하는 통로에 대해서는 크루스칼 알고리즘은 미리 두 정점을 $Union$ 을 해주고 프림 알고리즘에서는 이미 존재하는 통로애 대해서 가중치를 $0$ 으로 추가했습니...
116.백준 6497 : 전력난 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 이론 문제입니다. 그냥 크루스칼 알고리즘과 프림 알고리즘을 구현한 다음에 문제에서 주어지는 전체 가중치의 값 - 최소 가중치의 값 을 구하면 절약할 수 있는 값이 나옵니다.
117.백준 17472 : 다리만들기 2 (Python)
본문 링크 > 📌 어떻게 탐색할 것인가? 일단 3 가지 작업을 수행했습니다. 모든 인접한 섬에 대해 번호 붙이기 모든 각각의 섬에 대해서 서로 거리를 구하기 유니온 파인드를 사용해서 서로 연결했는지 찾기 $DFS$ 와 $Union$-$Find$ 알고리즘을 사용했습니다. $N,M$ 의 범위가 $1 ≤ N, M ≤ 10$ 이기 때문에 다양하게 풀어도 ...
118.백준 2887 : 행성 터널 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 두 행성 $A(xA, yA, zA)$ 와 $B(xB, yB, zB)$ 를 터널로 연결할 때 드는 비용은 $min(|xA-xB|, |yA-yB|, |zA-zB|)$ 이다. 이 문제의 가장 핵심이 되는 부분입니다. 절대값이 작아야 한다는 것은 두 수가 비슷해야한다는 점입니다. 즉 , $X$, $Y$ , $Z$...
119.백준 1647 : 도시 분할 계획 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제입니다. 저는 크루스칼 알고리즘을 통해 풀었습니다. 문제에서 중요한 것은 도시를 두 마을로 나누어서 간선의 비용이 최소가 되려고 한다. 즉 도시를 두 마을로 연결하는 것입니다. 크루스칼 알고리즘은 모든 노드들을 연결하는 알고리즘이기 때문에 생각을 해봐야합니다. 간단하게 모든 간선들을...
120.백준 1922 : 네트워크 연결 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 기초 문제입니다. 크루스칼과 프림 알고리즘을 이용하여 풀었습니다. 그대로 구현해주시면 됩니다. 다만 프림 알고리즘 사용시 첫 노드의 번호는 1 이기 때문에 $(0,1)$ 을 넣어주셔야합니다.
121.백준 16398 : 행성 연결 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 처음에 입력이 헷갈렸는데 그냥 모든 정점들에 대해서 연결해주면 됩니다. 다만 좌표들의 위치가 2차원 좌표로 주어지므로 프림 알고리즘보다 간선만 생각하면 되는 크루스칼 알고리즘을 사용했습니다.
122.백준 13905 : 세부 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 알고리즘인 크루스칼을 통해 풀었습니다. 그냥 크루스칼을 구현하지만 , 가중치가 최대가 되어야 하므로 오름차순이 아니라 내림차순으로 정렬해줍시다. 그리고 if Find(S)==Find(E) 즉 , $S$ 에서 $E$ 로 가는 간선이 생기면 그때의 value 값을 저장합니다. 처음에는 변수 ...
123.백준 21924 : 도시 건설 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제입니다. 그대로 구현해주면 되지만 문제에서 주의해야할 점은 모든 노드가 연결되어있는지 판별해주어야 합니다. 크루스칼 알고리즘에서는 집합이 2개이상으로 분리되어있는지 체크를 통해 판별가능합니다. 프림은 visit 배열을 사용하면서 False ...
124.백준 14621 : 나만 안되는 연애 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 일반적인 최소 스패닝 트리이지만 한가지 조건이 추가되었습니다. 같은 색깔(대학) 은 서로 연결 할 수 없습니다. 따라서 크루스칼 알고리즘에서는 if School[x-1]!=School[y-1] 라는 조건을 한번 체크 해주고 간선을 연결하고 연결할수 있는지 없는지에...
125.백준 16202 : MST 게임 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 문제는 간단합니다. 입력으로 서로 연결되어있는 정점이 주어집니다. 이때 입력으로 주어지는 순서에 따라 가중치가 1씩 증가합니다. 그리고 가장 가중치가 낮은 , 즉 가장 먼저 받은 간선들을 잘라서 $MST$ 가 완성되는지 확인하고 , 가능하다면 가중치의 합의 최소값...
126.백준 13418 : 학교 탐방하기 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제입니다. 간단하게 정렬을 통해서 내리막길을 먼저 연결해주는 방법과 오르막길을 먼저 연결해주는 스패닝 트리를 만들어 주었습니다. 이때 피로도 계산은 오르막길일때만 생각해주면 되고 입력을 받을때 $M$ 번이 아니라 총 $M+1$ 번을 받아야합니다...
127.백준 14950 : 정복자 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 기초 문제입니다. 크루스칼과 프림 알고리즘을 구현해주면 되는데 매번 땅을 정복할때마다 비용에 $T$ 증가하므로 count 변수를 통해 땅을 정복한 개수를 세주고 모든 노드를 연결한 후에 반복문을 통해서 T×1 , T×2 , T×3 ... 연산을...
128.백준 1414 : 불우이웃돕기 (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제이므로 크루스칼과 프림 알고리즘을 사용했습니다. 처음에 문제를 이해하지 못했는데 그래프가 주어지면 $i$,$j$ 값의 좌표가 $K$ 라면 $i$ 번째 노드와 $j$ 번째 노드는 가중치가 $K$ 인 간선으로 연결되어있다는 말이었습니다. 따라...
129.백준 2406 : 안정적인 네트워크 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제를 잘 읽어야한다. 본사의 컴퓨터는 항상 $1$ 번이고 , 본사는 다른 컴퓨터 전체와 연결되어있다. 따라서 본사컴퓨터인 $1$ 번 노드를 제외하고 최소 스패닝 트리를 구성하면 된다. 따라서 edge 에 노드와 가중치를 입력받을때 i==0 or j==0 인 경우는 입력을 받지않는다. 나머지 부분은 크루스...
130.백준 9344 : 도로 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 처음에 문제가 이해가 되지않았는데 잘 읽어보면 엔지니어가 일단 모든 간선을 연결하려고 한다. 이때 정점을 연결할때 사이클이 생기지 않으면서 $P$ 와 $Q$ 를 연결하는 간선이 있는지 확인해주면 된다. 즉 사이클이 생기지 않는지가 찾아주는것이 핵심이다.
131.백준 10723 : 판게아 1 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 이해하는데 좀 오래걸렸다. 문제 입력도 까다롭게 써놓았고 구하라는것도 애매하게 설명되어있다. 자세하게 알아보자. 일단 예제 입력부터 보자 1 3 3 0 5 1 3 0 2 4 0 1 2 0 0 2 첫번째 값 1 은 테스트 케이스 개수다. 두번째는 $N$ 와 $M$ 이 주어진다. 그리고 $N-1$ 줄에 이...
132.백준 18769 : 그리드 네트워크 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제 입력받는게 좀 까다로웠다. 1 2 3 4 5 6 7 8 9 위 형식으로 노드 번호를 만들었고 서로 연결되는 간선을 입력받았습니다. 이후 그냥 크루스칼 알고리즘을 통해서 최소스패닝 트리를 만들어 주었습니다. 입력만 잘 받으면 쉽게 풀리는 문제입니다.
133.백준 1833 : 고속철도 설계하기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 최소 스패닝 트리 문제 입니다. 크루스칼 알고리즘을 통해 구현했습니다. 이미 설치된 도시에 대해서는 전부다 연결을 해주고 그다음에 나머지 간선들을 정렬해서 연결해줍니다. 이때 연결된 노드를 저장하고 마지막에 출력해줘야 합니다.
134.백준 7044 : Bad Cowtractors (Python)
본문 링크 📌 크루스칼 알고리즘 📌 프림 알고리즘 > 📌 어떻게 접근할 것인가? 문제에서 요구하는 것은 최대 스패닝 트리입니다. 두 노드와 연결된 간선의 가중치가 주어졌을때 트리를 연결하면서 가중치의 합이 최대로 만들면 됩니다. 이는 최소 스패닝 트리 알고리즘을 사용하였습니다. 크루스칼 알고리즘에서는 간선의 가중치를 오름차순이 아니라 내림...
135.백준 1753 : 최단경로 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 아주 기본적인 다익스트라 문제입니다. dp 배열에 INF 값을 넣은후에 heap 자료구조를 써서 간선의 비용이 적은 노드부터 탐색해주고 노드들의 이동거리의 최소값을 매번 갱신해주었습니다. 이때 경로가 존재하지 않을 수 있기 때문에 dp 배열의 초기값과 같다면 INF 를 출력해주고 그렇지 않다면 배열의 값을 출...
136.백준 1504 : 특정한 최단 경로 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 응용 문제입니다. 아주 중요하다고 생각되는 문제입니다. 문제에서 요구하는 바는 최단경로를 구하는 것이지만 , 이때 특정 두 노드를 꼭 방문해야 합니다. 따라서 1부터 $N$ 까지 간다고 했을때 $A$ 와 $B$ 라는 정점을 지나야 한다면 1 - $A$ - $B$ - $N$ 1 - $B$ - $A...
137.백준 13549 : 숨바꼭질 3 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? $BFS$ 로도 풀수 있지만 다익스트라를 이용해 풀었습니다. heapq 라이브러리를 불러와주고 dp 배열을 INF 로 초기화 해주었습니다. 그리고 이동가능한 정점중에 가중치가 더 적은 지점이 있다면 그 노드로 이동해줍니다. 이후 문제에서 원하는 K 번째 노드의 값 , 즉 이동횟수를 출력해줍니다.
138.백준 1238 : 파티 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 응용 문제입니다. 일단 문제에 요구하는 것을 보면 $N$ 이 먼저 주어집니다. 이때 1,2,3...$N$ 과 같이 1번부터 $N$ 번째 마을에 학생이 한명이 존재한다는 뜻입니다. 이후 파티가 열리는 $X$ 입니다. 문제에서 주어지는 간선을 통해서 파티의 장소에 도착해야합니다. 이때 3 4 5 ...
139.백준 9370 : 미확인 도착지 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제 내용이 좀 어렵게 되어있는데 풀이자체는 간단합니다. 일단 시작점은 회색 노드입니다. 그리고 원하는 목적지는 검은 노드입니다. 이때 반드시 최단 경로로 이동해야합니다. 문제에서 원하는 것은 회색노드에서 검은노드로 이동했을때 점선을 지나는가? 입니다. 2번노드에서 6번노드의 최단경로는 2 - 1 - ...
140.백준 1916 : 최소비용 구하기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 기초 문제입니다. 다만 1번노드부터 $N$ 번노드까지의 최단경로가 아니라 문제에서 주어지는 두 노드에 대한 최단경로를 구하는 것이기 때문에 함수의 매개변수를 활용해서 시작점을 입력값으로 정해준뒤에 그곳부터 출발하여서 최단경로를 구하였습니다. 백준 1753 : 최단경로 와 유사한 문제입니다.
141.백준 1261 : 알고스팟 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 이용해 풀었습니다. 그래프의 x 와 y 좌표를 저장하고 heapq 를 통해 그래프의 값이 0 인 지점을 우선적으로 넣어주었습니다. 그리고 이동가능한 모든 정점에 대해서 매번 최소값을 갱신해주면서 이동을 하고 마지막에 dpM-1 을 출력하면 답이 됩니다.
142.백준 4485 : 녹색 옷 입은 애가 젤다지? (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 기초 문제입니다. graph 를 입력받고 $(0,0)$ 부터 시작해서 $(N-1,N-1)$ 로 가는 최단경로를 구해주면 됩니다. 다익스트라를 그대로 구현해주면 되는데 주의해줘야 할점은 처음 시작점은 graph0 값을 가지고 시작하기 때문에 값을 체크할때 dp 의 값과 graph 값의 합이 value...
143.백준 18352 : 특정 거리의 도시 찾기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 알고리즘을 사용하였습니다. 모든 간선의 가중치가 1 이기 때문에 가중치는 1로 고정하고 단방향으로 이동하기 때문에 노드를 한방향으로만 추가해줍니다. 이후 최단경로를 찾으면서 만약 가중치의 합이 $K$ 인 지점이 발생하면 그때 Answer 리스트에 노드를 추가합니다. 단 이때 최단경로로 이동했을때 ...
144.백준 11779 : 최소비용 구하기 2 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 최소비용 구하기 1 문제에서 다익스트라로 최단경로를 구했을때 어떤경로를 이동했는지를 찾는 문제입니다. visit=[0]*(N+1) 로 배열을 만들어 준 다음에 만약 이동이 가능한 지점이 나타나면 이동할 지점에 현재 노드번호를 저장합니다. 그리고 다익스트라가 끝난후에 도착점을 tmp 로 잡으면 이전에 이동했...
145.백준 13913 : 숨바꼭질 4 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 기존의 숨바꼭질 3 문제를 살짝변형시켰습니다. $-1$ , $1$ , $2$배 이동 가능하며 이동할때 드는 가중치는 $+1$ 입니다. 다익스트라로 구현했고 경로를 역추적 하기 위해서 visit 배열을 선언했습니다. 이때 이동가능한 경로가 존재하면 visit 배열에 이동할 지점에 현재 노드값을 저장합니다. ...
146.백준 2665 : 미로만들기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 이용해 문제를 풀었습니다. 문제에서 이동가능한 노드의 번호가 1 이기 때문에 0 으로 바꿔준 후에 0 인지점을 우선적으로 탐색해줍니다. 다익스트라를 통해서 $(1,1)$ 부터 $(N,N)$ 까지 최단경로를 구할 수 있습니다.
147.백준 14938 : 서강그라운드 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 문제에서 주어진 것은 임의의 노드에 떨어졌을때 수색가능한 범위중 가질수 있는 아이템의 최대 개수를 구하는 것이다. 따라서 시작 노드를 정하고 다른 노드로 가는 최단 경로를 구해준다. 이때 다른노드로 가는 최단경로가 수색범위 내에 있을때 , 아이템을 얻을 수 있다. 그리고 문제에서는 시작노드를 정해주었지 않았...
148.백준 10282 : 해킹 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 응용 문제입니다. 시작노드에서 모든 노드들에 대해 최단경로를 구해줍니다. 이후 최단경로를 모두 구했다면 그것을 담은 배열을 정렬해줍니다. 문제에서 요구하는 바는 가능한 모든 컴퓨터들을 해킹했을때 그때의 개수와 시간이므로 정렬을 해서 뒤에서부터 dp 의 값이 INF 가 아닐때까지 찾습니다. 즉 해킹을...
149.백준 22116 : 창영이와 퇴근 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 처음에는 $MST$ 로 풀었습니다. 크루스칼 알고리즘을 사용하니 이동가능한 간선의 개수가 대부분의 노드마다 상하좌우로 이동가능하다보니 시간초과가 났습니다. 그래서 프림알고리즘으로 해봤는데 잘 안풀려서 다익스트라 알고리즘을 사용했습니다. 이동가능한 정점에 대해서 절대값을 구한뒤에 최단경로로 이동했습니다. 하...
150.백준 6087 : 레이저 통신 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 이용해 구했습니다. 상하좌우로 이동했을때의 정보를 담아서 다음번에 상하좌우로 이동할때 이전에 이동했던 방향과 일치하다면 그냥 이동하고 그렇지 않으면 값을 +1 추가해서 이동해줍니다. 이때 이동가능한 모든 경로를 찾아야 하기 때문에 if direction==i and value<dpnx: if d...
151.백준 1854 : K번째 최단경로 찾기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라 알고리즘을 사용했습니다. 문제에서 구하고자 하는 것은 $K$ 번째 최단경로 입니다. 기존에 사용하던 dp 배열 , 즉 최단경로를 담는 배열을 2차원 배열로 만들어 주고 최대 힙으로 구성하였습니다. 이렇게 한 이유는 그냥 $K$번째 최단 경로를 일반적인 다익스트라로 구현했을때 꼭 $K$ 번째 최단경...
152.백준 1517 : 버블 소트 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용하였습니다. L2 라는 새로운 배열을 만들고 배열의 값과 인덱스 값을 넣었습니다. 이후 배열의 값에 따라 정렬해주면 인덱스 값이 섞이게 됩니다. query 함수를 호출해서 섞인 인덱스 값을 매개변수로 넣고 그 값에 따른 구간에 정렬되지 않은 원소가 몇개인지 합을 구합니다. ks1ksi님...
153.백준 9345 : 디지털 비디오 디스크 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 두가지 쿼리가 주어집니다. $A$ 와 $B$ 번의 값을 바꾼다. $A$ 부터 $B$ 번까지 범위에서 $DVD$ 가 $A$부터 $B$까지 모두 포함하는가? 세그먼트 트리를 사용했습니다. 먼저 tree 를 2차원 배열로 구성해줍니다. tree 에서 우리가 저장할 값은 최대값과 최소값 입니다. $A$ 번 ...
154.백준 16975 : 수열과 쿼리 21 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 그냥 세그먼트 트리를 사용했습니다. update 함수를 통해서 범위안에있으면 value 를 더해주고 query 함수를 통해서 범위안에있는 합을 전부 더해서 return 하였습니다. 주의해야할 점은 저는 0번째 인덱스 부터 시작하였기 때문에 인덱스값에 전부 -1 를 해줘야 합니다.
155.백준 1275 : 커피숍2 (Python)
본분 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용했습니다. 처음 init 함수를 통해서 리스트 입력받은 값에 따라 초기 값을 할당해줍니다. 누적합 문제이기 때문에 tree[node]=tree[node2]+tree[node2+1] 를 해줍니다. update 함수는 만약 범위를 포함하고 있다면 tree[node]=value 로 값을 변경해...
156.백준 2268 : 수들의 합 7 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용해서 풀었습니다. 초기값은 전부다 $0$ 이므로 굳이 init 함수를 따로 만들어서 초기화 할 필요는 없습니다. 값을 변경하는 함수와 합을 구하는 함수를 만들어 주었습니다. 이때 주의해야할 점은 Sum 을 구할때 A,B 의 값이 꼭 오름차순이 아닐 수 있기 때문에 정렬해주었습니다. 값을...
157.백준 14438 : 수열과 쿼리 17 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용하여 풀었습니다. 문제에서 주어지는 대로 update 함수는 값을 변경하도록 만들었고 query 는 찾고자 하는 값이 최소값이므로 return 값을 최소값으로 반환하였습니다. $0$ 번째 인덱스 부터 시작하였기 때문에 변수를 인덱스로 사용할 경우 -1 를 추가하였습니다.
158.백준 5676 : 음주 코딩 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용했습니다. 쿼리는 2개 입니다. 특정인덱스의 값을 바꾸는것 , 그리고 특정범위내의 곱의 음수인지 양수인지 0 인지 판단하는것. 값을 바꾸는것은 그냥 구현하면 되는데 이때 특정 구간의 전체 곱을 그대로 구해버리면 수가 너무 커지기 때문에 시간초과가 발생합니다. 구하고자 하는것은 양수 , ...
159.백준 14428 : 수열과 쿼리 16 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 이용해 풀었습니다. 쿼리는 2개 입니다. 값을 변경하는 것과 특정 구간에서 가장 값이 작은 수의 인덱스를 구하라. 따라서 세그먼트 트리를 2차원 배열로 만들었습니다. 배열에 배열의 값과 인덱스 값을 넣었으며 배열의 값에 따라서 값을 더 작은쪽을 저장했습니다. 이때 중요한 것은 배열의 값이...
160.백준 12837 : 가계부 (Hard) (Python)
본문 링크 >📌 어떻게 접근할 것인가? 세그먼트 트리를 사용해서 풀었습니다. 쿼리를 2가지 입니다. 특정 인덱스의 값을 바꾸는 것과 특정 구간의 합을 구하는것 update 함수를 통해 특정 인덱스의 값을 변경하였고 query 함수를 통해 특정 구간의 합을 반환하도록 하였습니다. 인덱스는 0 부터 시작하기 때문에 쿼리에서 주어지는 변수를 인덱스로 ...
161.백준 14427 : 수열과 쿼리 15 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 세그먼트 트리를 사용해서 풀었습니다. 수열과 쿼리 16 문제와 아주 비슷하기 때문에 코드를 살짝만 수정했습니다. 두번째 쿼리인 특정 범위의 가장작은 값의 인덱스를 구하는 것인데 이 문제는 모든 배열에서의 가장 작은값의 인덱스를 구해야합니다. 따라서 입력을 살짝 바꾸어 주고 query 함수의 호출 범위를 매번 ...
162.백준 18436 : 수열과 쿼리 37 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 세그먼트 트리를 사용해 풀었습니다. 2차원 배열로 만들어 주었습니다. 파이썬에서 배열을 생성하는 과정에서 맞왜틀을 자주 했는데 처음에 배열을 이렇게 생성했습니다. 하지만 이렇게 해버리면 2차원 배열은 절대 이렇게 만들어서 안됩니다. 2차원 배열은 무조건 컴프리헨션을 사용해야합니다. 컴프리핸선을 사용하지...
163.백준 2211 : 네트워크 복구 (Python)
본문 링크 > 📌 아떻게 접근할 것인가? 다익스트라를 통해 풀었습니다. 모든 정점을 연결해야 하므로 연결해야하는 간선의 개수는 항상 $N-1$ 개 입니다. 또한 역추적을 하기 위해서 check[next_node]=node 와 같이 다음노드에 이전노드의 값을 저장해서 반복문을 통해 역추적한 결과를 출력해줍니다. 순서는 상관없습니다.
164.백준 1719 : 택배 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 통해 풀었습니다. 문제에서 원하는 것은 특정 노드에서 다른 노드로 이동할때 최단경로로 이동했을때 가장 먼저 방문하는 노드를 찾는 것입니다. 역추적을 하기 위해서 Route 라는 배열을 만들어 주고 Route[next_node]=node 다음 이동할 노드에 이전의 노드 번호를 저장합니다. 이후 ...
165.백준 1162 : 도로포장 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 통해 풀었습니다. 이때 dp 배열을 2차원으로 선언해서 K 개의 포장도로를 만드는 최소값을 항상 갱신해주어야 합니다. 만약 도로를 포장하는 것이 가능하고 그때 값이 더 줄어들 수 있다면 dp 배열에 기존의 값을 그대로 넣어줍니다. dpx 라고 할때 x 는 포장한 도로의 개수 , y 는 지금까지 이...
166.백준 1446 : 지름길 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 다익스트라를 통해 풀었습니다. 일단 예제부터 보겠습니다. 5 150 0 50 10 0 50 20 50 100 10 100 151 10 110 140 90 목표는 0 지점에서 150 지점으로 가는것입니다. 이때 한 칸 이동할때마다 거리가 1씩증가합니다. 다만 지름길을 통해 간다면 0-50-100 으로 1...
167.백준 1182 : 부분수열의 합 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해서 접근하였습니다. 중복되지 않은 원소들을 visit 배열로 체크해준후 똑같은 값을 넣지 않았다면 원소를 넣고 재귀함수를 들어갑니다. 그리고 만약 원소의 길이가 0 이상이고 합이 $S$ 일때 total+=1 을 해줍니다. 중요한것은 5 0 0 0 0 0 0 위의 답은 31 입니다. 하지만...
168.백준 16922 : 로마 숫자 만들기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 반복문이나 조합 라이브러리 써서 풀수도있지만 백트래킹 연습중이라 백트래킹으로 풀었습니다. 백트래킹보다는 사실 재귀에 가깝네요. 재귀함수를 통해서 매번 깊이를 1 씩 증가시키고 깊이가 $N$ 이라면 , 즉 문자열의 길이가 $N$ 이라면 그때 방문체크배열 visit 값에 따라서 Answer 을 증가시킵니다. ...
169.백준 18429 : 근손실 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해 접근했습니다. 문제에서 매일 $K$ 만큼 근 손실이 일어나고 리스트의 값만큼 운동을 해서 값이 증가합니다. 이때 근육량이 한번이라도 300미만으로 떨어지면 제외해야 합니다. 위와 같은 조건을 사용하였습니다. 만약 총 $N$ 일동안 근육이 300 미만으로 한번도 떨어지지 않는다면 경우의 ...
170.백준 2293 : 스도쿠 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해 풀었습니다. set 을 사용해서 가로 , 세로 , 3 × 3 사각형에 대해 값이 존재하지 않는지 체크후에 모두 다 값이 존재하지 않다면 작은 숫자부터 넣어줍니다. 이후 재귀가 끝나면 원레 graph 값을 0 으로 되돌려놓고 set 의 원소를 삭제 해줍니다. 또한 처음 그래프를 입력받을때도...
171.백준 10971 : 외판원 순회2 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해서 모든 경로를 탐색했습니다 visit 배열은 더 효율적으로 탐색하기 위해서 1차원 배열로 사용하였습니다. 문제에서 외판원 순회는 , 시작지점에서 출발하여 똑같은 지점을 방문하지 않고 단 한번씩만 방문해서 마지막 도착지점이 시작지점과 동일한지 판별하는 문제입니다. ` 이는 위와 같이 판별했습...
172.백준 2529 : 부등호 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해 풀었습니다. 재귀로 특정 문자열을 만들었을때 최대 최소를 저장할 문자열을 선언해줍니다. 0부터 9 까지 처음수를 잡아주고 재귀를 실행합니다. 백트래킹의 핵심이 되는 부분입니다. 첫번째 반복문의start 를 통해서 이전에 썼던 부등호는 안쓰도록 처리해줍니다. 부등호가 > 일때의 조건만 보...
173.백준 2961 : 도영이가 만든 맛있는 음식 (Python)
본문 링크 >📌 어떻게 접근할 것인가? 모든 경우의 수를 탐색하기 위해서 백트래킹을 사용했습니다. 반복문을 통해서 선택하지 않은 음식에 대해서 재귀를 수행하고 매번 차이의 최소값을 갱신해줍니다. 또한 음식은 한개당 한번만 사용해야 하므로 함수의 매개변수에 start 를 넣음으로써 똑같은것을 선택하지 않도록 했습니다. visit 배열을 통해서 방문...
174.백준 16198 : 에너지 모으기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 모든 경우의 수를 탐색할 수 있는 백트래킹을 사용해 풀었습니다. 리스트의 길이가 $3$ 이상일때 , 시작과 끝을 제외한 나머지 원소들에 대해 반복문으로 탐색을 시작합니다. 왼쪽원소와 오른쪽원소의 곱을 저장하고 , check 변수에 원소를 지울려는 인덱스와 , 그때의 값을 저장합니다. 이후 del L[i]...
175.백준 16987 : 계란으로 계란치기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해 접근하였습니다. 종료조건이라던지 확인해야할 부분이 많이 있었는데 , 그런구부븐 그냥 if 문을 따로 써줘서 return 을 해주는게 복잡성을 줄일 수 있는 방법인것 같습니다. 만약 마지막까지 도착했다면 지금까지 깨진 계란의 수를 저장합니다. 만약 지금들고있는 계란이 깨졌다면 start+1...
176.백준 18290 : NM과 K (1) (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 백트래킹을 사용해서 풀었습니다. 처음에 방문처리 체크 배열을 이렇게 만들었는데 , 이렇게 할시 제대로 탐식이 안됩니다. False False False False True True True False True True True True True False # 여기서 탐색을 해버림. False False...
177.백준 2836 : 수상 택시 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? 스위핑을 통해 풀었습니다. 문제에서 원하는 것은 $0$ 부터 $M$ 으로 이동할때 , $A$ 에 위치하는 사람이 $B$ 로 이동을 원해서 모두 옮겨주고 $M$ 으로 도착하는 최단경로를 구하는 문제입니다. 가만히 생각해보면 $AB$ 일 때 입니다. 즉 왔던길을 다시 되돌아 가야하는경우 인데 , 이 부분도 ...
178.백준 1786 : 찾기 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? KMP 기초 문제입니다. getline 을 통해 공백을 포함하여 한줄을 입력받습니다. 이후 maketable 이라는 실패함수를 만들어 주고 KMP 함수에서 실패 함수를 활용하여 $O(N+M)$ 의 시간복잡도로 두 문자열을 비교해주었습니다. KMP 에 대한 자세한 내용은 나동빈 - KMP 강의 의 사...
179.백준 1305 : 광고 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? KMP 응용 문제입니다. 문제를 좀 이해하는데 오래 걸렸습니다. 현재 광고판에 보이는 문자열이 cabcab 라고 가정해봅시다. 광고판은 매번 가장 오른쪽 문자가 왼쪽 문자로 이동합니다. 구하고자 하는 것은 최소 몇개의 문자열로 저 광고판을 만들수 있는가? 입니다. 이때 답은 abc , 즉 3가 됩니다....
180.백준 1701 : Cubeditor (C++)
본문 링크 > 📌 어떻게 접근할 것인가? KMP 응용 문제입니다. 실패함수를 응용해야합니다. 문제에서 원하는 것은 두번 이상 나오는 부분문자열의 최대 길이입니다. 실패함수란 , 접두사와 접미사가 같은 최대 길이를 저장하는 함수입니다. 즉 실패함수에 aba 라는 값이 있다면 0 0 1 이 나올것이고 1 이라는 값은 이전에 문자열에 a 라는 똑같은 ...
181.백준 4354 : 문자열 제곱 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? KMP 응용문제입니다. 그냥 문제에서 원하는 것은 간단하게 말해서 문자열이 있을때 특정한 부분문자열을 반복해서 전체문자열을 만들 수 있는가? 를 묻습니다. 예를 들면 ababab 가 있을때 ab 를 3번 사용해서 전체 문자열을 만들 수 있습니다. 문제에서 원하는 것은 $N$ 의 최대값이므로 가장 짧은 ...
182.백준 10266 : 시계 사진들 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? 정말 좋은 문제라고 생각합니다. 일단 KMP 를 사용해서 풀었습니다. KMP 태그가 있는 문제들을 풀고있는 중이었는데 , 만약 KMP 태그가 있다는걸 몰랐으면 정말 정말 접근하기 어려운 문제라고 생각합니다. 물론 다양한 풀이법이 있겠지만 이 문제를 보고 KMP 를 사용한다고 발상하기에는 아주 까다롭다고 생각...
183.백준 11585 : 속타는 저녁 메뉴 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? KMP 를 사용해서 풀었습니다. 룰렛은 원형이기 때문에 기존의 문자열에서 2배를 해주고 마지막 뒤에 값 하나를 빼줍니다. 문제에서 원하는 바는 원형 룰렛을 돌렸을 때 오늘 저녁으로 고기를 선택하게 되는 확률 입니다. 6 A A B A A B B A A B A A 위와 같은 룰렛이 있을때 현재 상태의 룰렛의...
184.백준 2213 : 트리의 독립집합 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? 트리에서 다이나믹 프로그래밍을 적용해 풀었습니다. 1949 - 우수마을 이 문제를 먼저 푸는것을 추천합니다. 간단하게 문제에서 원하는 것은 서로 인접하지 않는 노드들을 선택해서 최대값을 만드는 것 입니다. 하지만 하나 더 추가로 해야할 것은 최대값을 선택할 때의 선택한 노드들도 구하는 것입니다. 자신이...
185.백준 14267 : 회사 문화 1 (C++)
본문 링크 > 📌 어떻게 접근할 것인가? 재귀를 통해 풀었습니다. 원래 아래에서 위로 올라가면서 가장 위에 도달했을때 함수 뒤에 dp 값을 갱신해줄려 했는데 그냥 위에서 아래로 내려가는동안 dp 값을 매번 갱신해주었습니다. 처음 dp 값을 설정해줄때 칭찬을 같은 사람이 할 수 있으므로 위와 같이 갱신해주어야 합니다. 이외에는 딱히 특별한 점은 ...
186.백준 10828 : 스택 (Java)
본문 링크 > 📌 어떻게 접근할 것인가? 자료구조의 기본인 스택 기초 문제입니다. push 를 입력받을때는 정수도 입력받아야 하기 때문에 str 을 한 줄 입력받고 str.contains("push") 를 통해 push 문자가 있는지 체크 후에 위와같이 공백을 기준으로 push 문자와 정수를 분리한 후에 정수를 push 해주었습니다. 나머지 부...
187.백준 15586 : MooTube (Gold) (Python)
본문 링크 > ✅ 어떻게 풀것인가? 유니온파인드와 오프라인 쿼리를 사용했습니다. 먼저 그래프를 입력받은후 가중치에 대해 내림차순 으로 정렬해줍니다. 쿼리 또한 $K$ 값에 따라 내림차순 으로 정렬해줍니다. 그리고 정렬하기 전에 쿼리를 미리 Query 배열에 복사해줍니다. disjoint 배열을 통해 분리집합을 구할 배열을 만들어 줍니다. 이후 정렬...
188.14499 : 주사위 굴리기 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 삼성문제집에있는 문제입니다. 또한 순수구현문제입니다. 주사위 도면을 생각해서 가로길이 배열 3개 , 세로길이 배열 4개를 덱으로 만들고 풀었습니다. 북쪽과 남쪽으로 가는건 쉽습니다. 위코드처럼 하면됩니다. 다만 동쪽과 서쪽으로 갈때는 직접 그림을 그리면서 어떤 원리로 이동하는지 확인해야합니다. 위와같은...
189.백준 23288 : 주사위 굴리기 2 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 어제 주사위굴리기 문제를 풀고 보니깐 2번째 시리즈 문제도 있어서 오늘 풀었습니다. 다만 다른점은 주사위의 밑면과 윗면이 바뀌었다는 점이고 문제내용이 많이 다릅니다. 처음에는 예제가 정말 이해안됬는데 , 처음 오른쪽으로
190.백준 14500 : 테트로미노 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 테트로미노의 5개의 도형을 그래프에 두었을때 그때의 값의 합에 최대값을 구하면 됩니다. 딱히 어려운건없고 그저 인덱스관리만 잘해주면서 구현해주면됩니다. 저는 이렇게 직접 그려가면서 구현했습니다. 상하좌우 , 대칭했을때의 경우의 수를 모두 구현해주면됩니다.
191.백준 14503 : 로봇 청소기 (Python)
본문 링크 > ✅ 어떻게 접근할 것인가? 삼성문제집에 있는 구현문제입니다. 문제에서 주어지는대로 그대로 구현하면되는데 주의해야할 점은 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 있는 경우 회전을 먼저하고 이동을 해야합니다. 또한 visit 방문처리 배열을 통해 빈칸 , 청소한칸 을 구분했습니다. 기본적으로 빈칸은 전부다 청소가 되지않은 상태이지만...
192.백준 15684 : 사다리 조작 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 오랜만에 푸는데 엄청 오래걸린 문제였습니다. 6시간정도 푼것같습니다. 이 문제를 풀면서 새로얻은 지식도 많은것같네요. 좋은문제인것같습니다. 문제는 간단합니다. 사다리에 다리를 3개까지 놓아서 $N$ 번째 사다리에서 출발해서 $N$번지점에 도착하도록 만드는 것입니다. 일단 $N$ , $M$ , $H$ 라는...
193.백준 15685 : 드래곤 커브 (Python)
본문 링크 > 📌 어떻게 접근할 것인가? 엄청 어려웠던 문제였습니다. 조금만 더 접근을 달리했으면 쉽게 풀었을텐데 아쉽네요. 크게 2가지 방법이 있습니다. 0 세대를 기준으로 탐색하는 방법 , 1세대를 기준으로 탐색하는 방법입니다. 일단 더 간단한 0 세대를
194.백준 15686 : 치킨 배달 (Python)
본문 링크📌 어떻게 풀것인가?$combination$ 과 $BFS$ 를 통해 풀었습니다.chicken 리스트에서 치킨의 위치에 대한 좌표값을 모두 넣어주었습니다. 그리고 $combination$ 을 사용해서 치킨의 지점 개수에서 $M$ 개를 뽑았습니다. 최대 $M$
195.백준 16235 : 나무 제테크 (Python)
본문 링크📌 어떻게 풀 것인가?구현자체는 굉장히 쉬운문제입니다. 다만 코드의 효율성을 극한으로 끌어올려야합니다. python,java 언어라면 자칫하면 시간초과받기 쉬운문제입니다.일단 나무를 담을 배열을 저는 from collections import defaultd
196.백준 17144 : 미세먼지 안녕! (Python)
본문 링크📌 어떻게 풀 것인가?그냥 구현하면 되는 문제입니다. 딱히 어려운 부분은 없습니다.첫번째로 미세먼지 확산을 할때 주의해야할 점이 있습니다.미세먼지가 확산된다. 확산은 미세먼지가 있는 모든 칸에서 동시에 일어난다.만약 이런 공유하는 칸을 가졌을때 5 에서 미세
197.백준 17143 : 낚시왕 (Python)
본문 링크 > 📌 어떻게 풀것인가? 문제는 엄청 간단합니다. 개인적으로 골드4~5 정도의 수준이라고 생각합니다. 문제에서 주의해야할 점이 있습니다. 매번 오른쪽으로 이동하면서 낚시를 통해 잡을 수 있는 상어의 개수는 최대 1 개 입니다. 따라서 만약 낚시를 통해서 상어를 잡았다면 바로 함수를 종료시켜야 합니다. 이동하는 부분도 이동한 후에 인덱스...
198.백준 9465 : 스티커 (Python)
본문 링크 > 📌 어떻게 풀것인가? 다이나믹 프로그래밍 기법을 활용했습니다. 오랜만에 $dp$ 문제를 풀려고 하니 좀 많이 어려웠습니다. 점화식 부터 하나씩 봅시다. dp1 = max(L1 + L2 + dp1 , dp1 , L1 + dp2 ) L1 + L
199.백준 17353 : 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 (Java)
본문 링크📌 사용 알고리즘 : Segment tree , 2차원 lazy Propagation문제에서 원하는 쿼리는 다음과 같다.1 $L$ $R$: $L$, $R$에 별이 떨어진다. (1 ≤ $L$ ≤ $R$ ≤ $N$)2 $X$: 점 X에 떨어진 별의 개수의 합을
200.백준 1049 : 기타줄 (Python)
문제 링크📌 사용알고리즘 : DP원래는 그리디로 풀수있을꺼같았지만 dp 연습할겸 dp 로 풀었습니다.그리디로 풀자면 1개 가격과 6개 가격 상품을 오름차순으로 정렬해서 각각 최소값을 구한후에1개로 N 개를 전부 구매하는법과 6개와 1개 상품을 섞어서 N 개를 구매했을
201.백준 1051 : 숫자 정사각형 ( Python )
본문 링크📌 사용 알고리즘 : implementation모든 정점에 대해 정사각형이 같은지 확인해줍니다.시간복잡도는 $O(NM×min(N,M))$ 입니다.(i,j) 번째 정점에 대해 K×K 크기의 정사각형을 판단하기 위해서는(i+K-1,j) , (i,j+K-1) ,
202.백준 1052 : 물병 ( Python )
문제 링크📌 사용 알고리즘 : bitmask , greedy , bruteforcing완전탐색으로 푸는 방법부터 알아봅시다.초기에는 물병이 1 L 씩 들어있습니다. 그리고 2개를 합치면 2 L 짜리 1개의 물병이 생깁니다.절반씩 줄어드므로 물병을 합치는 과정은 $O(
203.백준 1080 : 행렬 ( Python )
문제 링크📌 사용 알고리즘 : Greedy , implementation행렬 A 를 행렬 B 로 바꾸는데 필요한 최소값을 구하는 문제입니다.이때 3×3 크기에 한해서 뒤집을 수 있습니다.몇번 시뮬레이션을 돌려보면 뒤집는 순서는 결과에 영향을 미치지 않습니다.따라서 최
204.백준 1141 : 접두사 ( Python )
문제 링크📌 사용 알고리즘 : bruteForcing정렬과 그리디를 사용해서 푸는 방법도있지만 완전탐색을 통해 풀었습니다.접두사 X 집합이 되기 위해서는 어떤 한 단어가 다른단어의 접두어가 되어서는 안됩니다.만약 a 라는 단어가 있다면 a 로 시작하는 모든 단어는 같
205.백준 1057 : 토너먼트 ( Python )
문제 링크📌 사용 알고리즘 : bitmasking , bruteforcing두명의 선수가 토너먼트를 할 시 몇번째 경기에서 만날지 구하는 문제입니다.Naive 하게 탐색한다면 1~2 구간 , 3~4 구간 , ••• , N-1 ~ N 구간 까지 살핀후에 두 사람이 같은
206.백준 1058 : 친구 ( Python )
문제 링크📌 사용 알고리즘 : brute forcingN 범위가 작기 때문에 브루트포스로 해결 가능합니다.문제에서 주어지는 입력은 행렬 형식이고 i 번째 사람이 j 번째 사람과 친구가 되기 위해서 graph\[i]\[j]==graph\[j]\[i]=='Y' 이어야 합
207.백준 1059 : 좋은 구간 ( Python )
문제 링크📌 사용 알고리즘 : 정렬 , brute forcingN 을 포함하는 특정 구간의 개수를 구하면 되는 문제입니다.먼저 입력받은 리스트를 오름차순으로 정렬한다음에이 조건에 맞는 식을 구해주면 됩니다.공식을 유도해서도 풀 수 있지만 모든 구간의 경우의 수를 직접
208.백준 1166 : 선물 ( Python )
문제 링크📌 사용 알고리즘 : binary search이분탐색을 공부할때 꼭 풀어보면 좋겠다고 생각되었던 문제였습니다.식을 구하는것은 크게 어렵지 않습니다.위 조건일때 start 값을 증가시키고 그렇지 않을때는 end 값을 감소시키면 됩니다.다만 실수오차가 매우 엄격
209.백준 1120 : 문자열 ( Python )
문제 링크📌 사용 알고리즘 : brute forcingA,B 두개의 문자열이 주어집니다. 이때 문자열의 길이는 항상 B 가 크거나 같습니다.이때 문자열 A 에 앞 또는 뒤에 문자 하나를 넣을 수 있습니다.이때 A,B 두개의 문자중에 서로 다른 문자를 최소화하는 것이
210.백준 1205 : 등수 구하기 ( Python )
문제 링크📌 사용 알고리즘 : implementation순수 구현문제입니다.점수가 100, 90, 90, 80 일때는 등수가 1,2,2,4 등입니다.즉 같은 점수는 같은 등수로 처리해주면됩니다.4 10 1020 20 20 20주의할것은 위 입력이 답이 2등이 아니라
211.백준 11000 : 강의실 배정 ( Python )
문제 링크📌 사용 알고리즘 : priority queue , 정렬문제는 간단합니다. 수업을 진행할것인데 최소강의실로 모든 수업을 해야합니다.다만 1~2 와 2~3 일때는 강의실 하나면 됩니다.41 202 43 94 5이런 입력을 생각해봅시다. 답은 일단 3 입니다.일
212.백준 2109 : 순회강연 ( Python )
문제 링크📌 사용 알고리즘 : priority queue , 작은 집합에서 큰 집합으로 합치는 테크닉처음엔 N 이 10000 이라서 O(N^2) 은 파이썬으로 애매할꺼같아서 O(Nlog^2(N)) 풀이법만 생각했습니다.📌 첫번째 풀이풀고보니 O(N^2) 풀이도 아슬
213.백준 2138 : 전구와 스위치 ( Python )
문제 링크📌 사용 알고리즘 : greedy , dynamic programming1차원 배열 형태의 전구가 있을때 스위치를 적절하게 끄면서 원하는 형태로 만들기 위한 최소값을 구하는 문제입니다.이때 스위치는 i-1,i,i+1 번째가 동시에 반전되고 1번째와 N번째 스
214.백준 11497 : 통나무 건너뛰기 ( Python )
문제 링크📌 사용알고리즘 : 정렬두가지 풀이법이 있습니다. 먼저 첫번째 풀이부터 봅시다.숫자를 적절히 섞어서 양옆의 차이가 최소로 되도록 만들어 주어야 합니다.원래라면 정렬한 상태가 답이겠지만 첫번째 값과 마지막 값이 연결되어있습니다.차이를 최소로 할려면 가장 큰 값