전체 글

오늘은 DP(다이나믹 프로그래밍) 유형인 백준 1463번 문제, 1로 만들기를 풀어보겠습니다! https://www.acmicpc.net/problem/1463📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정문제의 목표는 주어진 정수 N을 1로 만들기 위해 최소 몇 번의 연산이 필요한지 구하는 것입니다. 정수 N을 1로 만드는 과정을 거쳐야하며, 가능한 연산은 총 세 가지입니다>> 계산 횟수를 최대한 줄이기 위해서는 이전 숫자들의 최소 연산을 저장하여 더 큰 숫자에서도활용할 수 있을 것 입니다! 따라서, DP(다이나믹 프로그래밍)..

오늘은 조합 유형인 백준 1010번 문제, 다리 놓기를 풀어보겠습니다! https://www.acmicpc.net/problem/1010📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 해당 문제의 목표는 주어진 N개의 서쪽 사이트와 M개의 동쪽 사이트 간에최대 N개의 다리를 서로 겹치지 않게 연결하는 경우의 수를 구하는 것입니다. 필수 조건은 M(동쪽 사이트)은 N(서쪽 사이트) 이상이고, 한 사이트에서는 무조건 한 개의 다리만 연결이 가능합니다. 다리 놓기 문제를 읽자마자 떠오른 아이디어는 바로 조합입니다!조건에 맞는 사이트를..

오늘은 DP(다이나믹 프로그래밍) 유형인 백준 2775번 문제, 부녀회장이 될테야를 풀어보겠습니다! https://www.acmicpc.net/problem/2775📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정문제의 목표는 k층 n호에 몇 명이 살고 있는지를 출력하는 것입니다. 해당 아파트는 아주 신기한 규칙이 존재합니다.바로 "k층 n호에는 (k-1) 층 1호부터 n호까지의 사람 수의 합이 거주하고 있는 것"입니다. 아래 그림을 통해 k층 n호에 몇 명이 살고 있는지 확인해 보겠습니다.(단, 아파트는 0층부터 시작하고 왼쪽부..

오늘은 DP(다이나믹 프로그래밍) 유형인 백준 2748번 문제, 피보나치 수 2를 풀어보겠습니다! https://www.acmicpc.net/problem/2748📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 이 문제는 주어진 자연수 n에 대해, n번째 피보나치 수를 구하는 것이다. 피보나치 수열의 대표적인 수학적 정의이고 내용은 아래와 같습니다." F(0) = 0, F(1) = 1  /  F(n) = F(n-1) + F(n-2) (n ≥ 2) " 피보나치 수열의 구현 방법은 총 2가지로,바로 재귀적인 방법과 반복적 접근(동적..

오늘은 이분 탐색 유형인 백준 1654번 문제, 랜선 자르기를 풀어보겠습니다! https://www.acmicpc.net/problem/1654📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 주요 내용은 K개의 랜선을 잘라서 N개의 같은 길이의 랜선을 만들면서 그 길이의 최대값을구하는 것입니다. 이를 위해, 이분 탐색을 활용하여 가능한 최대 길이를 효율적으로 찾아냅니다. (모든 랜선은 정수 길이로 잘라야 하며, 랜선의 길이를 최대화) 즉, 랜선의 최소 길이인 1부터 최대 길이 까지의 중간 값을 탐색하면서,중간 값으로 잘라 N개의..

오늘은 이분 탐색 유형인 백준 7759번 문제, 먹을 것인가 먹힐 것인가를 풀어보겠습니다! https://www.acmicpc.net/problem/7795📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정두 생명체 A와 B의 크기가 주어졌을 때, A의 크기가 B보다 큰 쌍의 개수를 구하는 것으로A와 B의 각 원소로 만들 수 있는 모든 쌍을 계산하는 것은 시간복잡도가 높아지므로 비효율적입니다.따라서, 이를 개선하기 위해 이분 탐색을 활용하여 효율적으로 해결할 수 있습니다! A의 각 원소에 대해 B에서 그보다 작은 값들의 개수를 찾아..

오늘은 이분 탐색 유형인 백준 10816번 문제, 숫자 카드 2를 풀어보겠습니다! https://www.acmicpc.net/problem/10816📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 숫자 카드 2 문제는 총 2가지 방법으로 풀어보겠습니다!>> 1️⃣ 이분 탐색(binary search)검색 범위를 줄여나가며 특정 데이터를 검색하는 방식으로, 정렬된 정수의 리스트를 같은 크기의두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘입니다. 리스트 중간 부분에 찾는 원소가 있는지 확인..

오늘은 이분 탐색 유형인 백준 1920번 문제, 수 찾기를 풀어보겠습니다! https://www.acmicpc.net/problem/1920 📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 이 문제는 두 번째 줄에 입력한 배열A의 숫자를 기반으로 마지막 줄에 입력한 숫자들이포함되는지의 여부를 파악하는 문제입니다. 해당 숫자가 있는지 없는지를 파악하기위한 여러 가지 방법이 있지만그중 이분 탐색을 통해 배열A를 탐색해 보도록 하겠습니다! ✔️ 이분 탐색이란? 검색 범위를 줄여나가며 특정 데이터를 검색하는 방식으로, 정렬된 정수의 리..

오늘은 그리디 알고리즘 유형인 백준 2828번 문제, 사과 담기 게임을 풀어보겠습니다! https://www.acmicpc.net/problem/2828📌 문제 탐색하기 - 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정 사과 받기 게임을 할 스크린의 길이 N과 바구니의 길이 M을 입력받고,사과가 떨어지는 위치를 리스트에 저장하여 하나씩 바구니 속으로 받아내야 합니다. 바구니를 움직여야 한다면 양쪽 위치를 변수로 두어 움직이는 횟수를 구할 수 있습니다.바구니의 가장 왼쪽은 left, 가장 오른쪽은 right으로 선언합니다. 해당 문제를 해결하기 위해..