[Python] 백준 알고리즘 1874번 : 스택 수열
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 👩💻문제 이해 위에 있는 숫자들을 무시한 채 밑에 깔린 숫자를 먼저 출력하는 것은 불가능하기 때문에 가장 위쪽의 숫자(TOP)가 입력된 숫자와 같지 않을 경우 스택을 만들 수 없다. 따라서 반복문 안에서 li.pop() != int(input()) 일 경우 -> NO 출력! 👩💻재귀함수를 사용한 코드 : 성공🌈 ..
[Python] 백준 알고리즘 10994번 : 별 찍기 - 19
https://www.acmicpc.net/problem/10994 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net 👩💻문제 이해 재귀함수를 이용한 문제는 패턴을 파악하는게 가장 중요하다. 하지만 아직 문제를 보자마자 패턴을 파악하는게 쉽진 않다. 나름대로 재귀함수 문제를 풀 때 로직을 조금 더 쉽게 알아차릴 수 있는 방법을 생각해봤는데, 대부분의 재귀함수는 정의된 함수의 변수를 n이라고 할 때 (n-1)을 변수로 가지는 함수를 호출한다. 따라서 n 일때와 n-1 일 때의 출력을 비교하며 로직을 찾으면 좀 더 쉽게 찾을 수 있을 것이다. n이 4일 때의 출력을 예로 들어보자면 가장 바깥 쪽의 라인(n) -> 행과 열이 (4*n -3)개 -..
[Python] ⭐️백준 알고리즘 11729번 : 하노이 탑 이동 순서
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 👩💻문제 이해 재귀함수 알고리즘을 이용해 하노이 탑 이동순서를 출력하고 이동 횟수를 구하는 문제이다. 재귀함수는 어떤 패턴이 반복되는지 찾아내는 게 중요하다 1번지점에서 3번지점으로 탑을 옮기기 위해선 위 그림과 같은 3개의 단계가 반복된다. 1단계 : n-1개의 원판을 1 -> 2 이동 2단계 : 남은 한 개의 원판을 1 -> 3 이동 3단계 : n-1개의 원판을 2 -> 3 이동..
[Python] 백준 알고리즘 2805번 : 나무 자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 👩💻문제 이해 항상 그렇듯 이분탐색 알고리즘에서는 무엇을 변수로 둘지와 조건을 어떻게 줄지가 가장 중요하다. (조건) 위 문제에서는 가지고 가려 하는 나무의 길이가 M으로 정해져 있기 때문에 이걸 조건으로 두면 된다. 즉, 주어진 배열 각각의 원소들을 구하고자 하는 값(target)으로 뺀 값의 합이 M이 되는 것이 조건이다. 그리고 이 때 절단기 높이의 ..
[Python] 백준 알고리즘 2776번 : 암기왕
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 👩💻문제 이해 이해하기에 어려운 문제는 아니다. N개의 정수가 주어진 '수첩1'의 배열을 정렬한 후 '수첩2'에 들어있는 각각의 정수들을 이분탐색 알고리즘으로 '수첩1'에도 있는지 없는지를 판단하면 된다. 👩💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 별도 구현) : 성공🌈 def binary(arr, target): start = 0 end = len(arr) - 1 while start
[Python] 백준 알고리즘 1654번 : 랜선 자르기
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 👩💻문제 이해 만들 수 있는 랜선의 길이 (target) 이 [1,2,3, ..., 주어진 랜선의 최대값] 배열을 이분탐색을 이용해 (주어진 랜선 길이 // 배열의 중간값)의 합이 K와 같아질 때 까지 반복하면 된다. 정렬된 배열에서 각각의 (주어진 랜선 길이 // start와 end의 중간값(mid)) 의 합(= cnt)이 k와 같아질 때까지 이분탐색 알고리즘을 반..