[ 문제링크 ]https://www.acmicpc.net/problem/11286 🚩 조건연산의 개수 N(1≤N≤100,000)이 주어지면, 다음 N개의 줄에 연산에 대한 정보를 나타내는 정수 x가 주어짐.x가 0이 아니라면 배열에 x라는 값을 넣는 연산임x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 연산임입력되는 x는 -2^31보다 크고, 2^31보다 작음입력에서 0이 주어진 횟수만큼 답을 출력해라. 배열이 비어있는데 0이 입력되면 0을 출력해라.  🚩 접근우선순위 큐를 사용하고 절댓값을 우선순위로 두면 되지 않을까?  🚩 시행착오- 우선순위 큐 구현우선순위 큐는 힙이라는 자료구조를 통해 구현할 수 있다.힙은 완전 이진 트리 모양을 가지며, 부모 노드의 값이 ..

[ 문제링크 ]https://school.programmers.co.kr/learn/courses/30/lessons/12939 🚩 조건문자열 s에 공백으로 구분된 숫자들이 저장되어 있음s에 나오는 숫자 중 최솟값과 최댓값을 찾아 공백으로 구분된 문자열 형태로 반환해라s에는 둘 이상의 정수가 공백으로 구분되어 있음   🚩 접근문자열 s -> split()을 이용하여 각 숫자를 list에 저장하고, 이를 int로 바꾸자최대 최소 -> 내장함수 max() min() 이용해서 구하자  🚩 시행착오처음에 slist = list(s.split()) 로 작성했는데, 이러면 각 숫자가 문자열 형태로 저장되어서 음수를 제대로 처리하지 못한다. 그래서 int로 변환해야 함!  💻 코드 (Python3)def so..

[ 문제링크 ]https://school.programmers.co.kr/learn/courses/30/lessons/178871 🚩 조건해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부름선수들의 이름이 1등부터 현재 등수부터 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어지면, 경기가 끝났을 때 등수 순서대로 배열에 담아 return해라  🚩 접근그냥 단순히 swap 형태로 구현하면..?  🚩 시행착오def solution(players, callings): #answer = [] for name in callings: found = players.index(name) ..

[ 문제링크 ]https://www.acmicpc.net/problem/1676 🚩 조건0 ≤ N ≤ 500 인 N이 주어짐N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구해라  🚩 접근N!를 구해나가는 과정에서 나오는 수의 0이 아닌 마지막 자리만 보면 된다고 생각했다.만약 맨 마지막 자리가 0이 된다면, 그 자리는 항상 0일 것이고, 그럼 answer++ 후 고려할 마지막 자리를 앞으로 한 칸 옮기면 된다고 생각했다.근데 이렇게 구현했더니 맞는 것 같은데 틀렸습니다가 나와서 반례를 찾아봤더니, 아래 케이스에서 결과가 달랐다.입력 > 25출력 > 5정답 > 6  🚩 시행착오결론 먼저 말하자면, 맨 뒷자리만 관리하면 안 된다. 이렇게 생각한 사람들이 꽤 많나보다..ㅎhttps:..

[ 문제링크 ]https://www.acmicpc.net/problem/1929  🚩 조건입력으로 M과 N이 들어옴M이상 N이하의 소수를 모두 출력해라  🚩 접근, 시행착오일단 2가 아닌 짝수이면 배제하고.. 홀수는 3부터 나눠가면서 소수인지 직접 확인?이런 단순한 생각을 했는데 당연히 시간초과가 날 것 같았다..그래서 결국 풀이를 찾아봤는데, 에라토스테네스의 체 알고리즘을 통해 소수를 구하는 문제였다. 에라토스테네스의 체는 어떤 정수 이하의 소수를 찾기 위해서, 소수를 찾는 것이 아니라 합성수를 제거하는 접근방식을 사용한다. 1. 정수 n이 주어지면, 2부터 n까지의 모든 수가 소수가 될 수 있다고 가정한다.# 정답 출력 시 좀 더 편하게 하기 위해, 0과 1에 대해서 False로 설정함is_pri..

[ 문제링크 ]https://www.acmicpc.net/problem/12865 🚩 조건첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어짐 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어짐 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력해라  🚩 접근0/1 Knapsack 문제.. 어떻게 푸는 거였더라...  🚩 시행착오처음엔 Branch and Bound로 시도해보려 하다가 그래프를 어떻게 정의해야 할지 감이 안와서.. 포기알고리즘 시간에 배운 기억으로는 DP로 푸는 게 최악의 경우 시간복잡도가 Brute Force와 같아진다고 했는..

[ 문제링크 ]https://www.acmicpc.net/problem/10844 🚩 조건계단 수는 45656처럼 인접한 모든 자리의 차이가 1인 수를 뜻함N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해라그걸 1,000,000,000으로 나눈 나머지를 출력해라  🚩 접근현재 자리의 수가 1이면, 뒤에 올 수 있는 수는 0과 2이다. 0과 9라는 예외가 있지만 0~9까지의 수는 모두 비슷한 양상을 띈다. 그래서 점화식을 세울 수 있지 않을까? -> DP  🚩 시행착오 점화식을 찾아내는 데 굉장히 많은 시간을 들였다.. D[i]를 i 뒤에 나올 수 있는 수 개수로 놔둬보기도 하고, F[i]는 길이가 i인 0으로 시작하는 것도 포함한 계단 수/D[i]는 0으로 시작하는 계단 수 로 놔둬서..

[ 문제링크 ]https://www.acmicpc.net/problem/11727 🚩 조건2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구해라1 ≤ n ≤ 1,000   🚩 접근이전에 풀었던 2xn 타일링과 유사하게 DP로 풀 수 있음  🚩 시행착오.  💻 코드 (C++)#include using namespace std;int D[1001]; //1-indexedint main(){ int n; cin>>n; D[0]=1; D[1]=1; for(int i=2;i

[ 문제링크 ]https://www.acmicpc.net/problem/1932 🚩 조건첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어짐맨 위층에서 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구해라아래층에 있는 수를 선택할 땐 현재 층에서 선택된 수의 왼쪽 대각선 또는 오른쪽 대각선에 있는 것만 가능함  🚩 접근각 층마다 제일 큰 수를 선택할 수 없음각각의 수에게 주어진 선택지는 왼쪽 대각선을 선택하거나, 오른쪽 대각선을 선택하거나로 같음아래층부터 살펴보며 두 선택지 중 큰 수가 있는 선택지를 고르고, 자기자신을 (자기자신+그 수)로 업데이트하자 : DP  🚩 시..

[ 문제링크 ]https://www.acmicpc.net/problem/1003  🚩 조건피보나치 수를 구하는 함수 fibonacci(N)이 주어짐fibonacci(N)을 호출했을 때 0과 1이 각각 몇 번 출력되는지 구해라 ( N은 40보다 작거나 같은 자연수 또는 0 )  🚩 접근시간제한이 0.25초인 문제 -> DP로 풀어야 할 듯 N이 주어지면 0과 1에 대해 피보나치 수를 DP로 풀듯이 식을 세울 수 있다. + 0과 1의 출력횟수를 나열해보면 아래와 같다.0의 출력횟수 : 1, 0, 1, 1, 2, 3, ... => [1]부터 0으로 시작하는 피보나치 수열1의 출력횟수 : 0, 1, 1, 1, 2, 5, ... => [0]부터 0으로 시작하는 피보나치 수열따라서 문제에서 주어진 피보나치 함수..