728x90 프로그래밍/알고리즘 문제 풀이11 [백준 시리즈] 2812번 : 크게 만들기 - 골드3 / Python 2812번 : 크게 만들기출처 : 백준 / 2812번: 크게 만들기 (acmicpc.net) 사용 알고리즘 : 스택, 그리디 문제 설명N자리 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 제한시간 제한 : 1초 / 메모리 제한 : 128MB1 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N이 50만이므로 O(NlogN) 이하의 알고리즘이 필요하다. 2단계 : naive하게 해결해보자횟수를 모두 사용하더라도 맨 앞자리에 제일 큰 숫자를 배치하는 것이 이득이다. i번째 숫자가 i+1번째 숫자보다 크면 남기고 작으면 지워야한다는 점에서 스택이 연상된다. 3단계 : 핵심 아이디어는 무엇인가넣을 숫자보다 작은 숫자를 K번 이하로 지우면서 스택에 삽입한다. 모든 숫자를 스택에 다 넣었음에도.. 2024. 9. 23. [백준 시리즈] 2666번 : 벽장문의 이동 - 골드5 / Python 2666번 : 벽장문의 이동출처 : 백준 / https://www.acmicpc.net/problem/2666사용 알고리즘 : 브루트 포스 문제 설명1. 항상 2개의 문이 열려있는 벽장 N개가 있다.2. 문을 열 벽장의 순서에 따라서 벽장문 이동 횟수의 최솟값을 구하라.3. 벽장문은 옆 벽장이 비어있어야 이동가능하다. 제한시간제한 : 1초 / 메모리 제한 : 128 MBN (3 문을 열 벽장의 개수는 최대 20개이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?모든 경우의 수를 고려하는 브루트포스로 문제를 해결했을 때, 최악의 경우에도 20*2^20번의 연산만이 수행되기 때문에 브루트포스 알고리즘으로 해결할 수 있다. 2단계 : naive 하게 생각해 보자현재 더 가까운 쪽의 벽장문을 열더라도 그.. 2024. 9. 21. [백준 시리즈] 21318번 : 피아노 체조 - 실버 1 / Python 21318번 : 피아노 체조출처 : 백준 / 21318번: 피아노 체조 (acmicpc.net) 사용 알고리즘 : 누적 합 문제 설명1. Q번의 쿼리에 대해 x번부터 y번까지 악보를 연주할 때 실수하는 곡이 몇 곡인지 찾아라.2. 각 악보마다 난이도가 주어지며 숫자가 높을수록 높은 난이도이다.3. 현재 연주하는 악보가 다음에 연주할 악보보다 어려우면 실수하며, 마지막 곡은 무조건 실수하지 않는다. 제한시간 제한 : 0.5초 / 메모리 제한 : 1024MB N(1 ≤ N ≤ 100,000) Q(1 ≤ Q ≤ 100,000) x, y(1 ≤ x ≤ y ≤ N) 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?O(QlogN) 2단계 : naive하게 해결해보자x번부터 y번까지 실수의 총합을 구하는 문제이.. 2024. 9. 17. [백준 시리즈] 1024번 : 수열의 합 - 실버 2 / Python 1024번 : 수열의 합 - 실버 2 / Python출처 : 백준 / 1024번: 수열의 합 (acmicpc.net) 사용 알고리즘 : 수학 문제 설명N과 L이 주어질 때, 합이 N이면서 길이가 적어도 L인 가장 짧은 연속된 음이 아닌 정수 리스트를 구하시오. 제한시간 제한 : 2초 / 메모리 제한 : 128MBN은 1,000,000,000 이하의 자연수이다.L은 2이상 100이하인 자연수이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?시간복잡도를 가늠하기 어렵다. N을 기준으로 시간복잡도를 구성한다면, O(logN) 이하의 알고리즘이 필요하다. 2단계 : Naive하게 풀어보자배열의 요소는 1~N까지 순차적이므로 등차 수열의 합 공식을 이용하여 순서쌍을 선택하는 문제로 변경할 수 있다. 배열이.. 2024. 9. 17. [백준 시리즈] 2012번 : 실버3 - 등수 매기기 / Python 제목 : 등수 매기기출처 : 백준 / 2012번: 등수 매기기 (acmicpc.net) 사용 자료구조&알고리즘 : 그리디, 정렬 문제 설명1. 모든 학생의 시험 정보를 날려 1등부터 N등까지 동석차 없이 등수를 임의로 매겨야 한다. 2. 예상 등수와 결과 등수의 차를 불만도라고 할 때, 불만도의 합의 최소가 되도록 등수를 매기려고 한다.3. 불만도 합의 최솟값을 구해라. 제한시간 제한 : 2초메모리 제한 : 256 MBN (1예상 등수는 500,000 이하의 자연수이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 10,000 이상이기 때문에 O(NlogN) 이하 시간복잡도가 요구된다. 2단계 : 핵심 아이디어는 무엇인가?예상 등수를 정렬하고 정렬된 등수대로 실제 등수를 부여하여 불만도를.. 2024. 9. 11. [백준 시리즈] 13900번 : 실버4 - 순서쌍의 곱의 합 / Python 제목 : 순서쌍의 곱의 합출처 : 백준 / 13900번: 순서쌍의 곱의 합 (acmicpc.net) 사용 자료구조&알고리즘 : 수학 문제 설명N개의 정수 중 서로 다른 위치의 두 수를 뽑는 모든 경우의 두 수의 곱의 합을 구하라. 제한시간 제한 : 1초메모리 제한 : 256 MBN (2입력 받는 각 수는 0이상 10,000 이하의 정수이다. 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 100000 이하이기 때문에 O(NlogN) 이하의 시간복잡도가 요구된다. 2단계 : naive하게 생각해보자.이중 반복문을 이용해 모든 두 수를 뽑고 곱하고 더하면 시간복잡도가 $O(N^2)$이다. 시간 초과가 발생하며 다른 방법을 생각해내야한다. 3단계 : 핵심 아이디어는 무엇인가?완전 제곱식을 이용한다.. 2024. 9. 10. [백준 시리즈] 21756번 : 브론즈2 - 지우개 / Python 제목 : 지우개출처 : 백준 / 21756번: 지우개 (acmicpc.net) 사용 자료구조&알고리즘 : 수학, 시뮬레이션 문제 설명 1. N (12. 다음 작업을 수가 정확히 하나가 남을 때까지 반복한다.홀수번 칸의 수들을 모두 지운다.남은 수들을 왼쪽으로 모은다.3. 마지막으로 남은 수를 계산해라. 제한시간 제한 : 1초메모리 제한 : 512 MB 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?N의 크기가 100 이하이기 때문에 시간 복잡도 제한이 없다. 2단계 : 핵심 아이디어는 무엇인가?문제에서 제시된 기능들을 정직하게 구현하면 되는 문제이다.홀수 또는 짝수번 칸의 수만 남으므로 각 숫자의 새로운 위치는 '현재 위치 / 2'이다.$log_2N$번만 실행하면 무조건 답이 나온다.정답 코드impor.. 2024. 9. 10. [백준 시리즈] 19638번 : 실버 1 - 센티와 마법의 뿅망치 / Python 제목 : 센티와 마법의 뿅망치출처 : 백준 / https://www.acmicpc.net/problem/19638사용 자료구조&알고리즘 : 힙 문제 설명1. 횟수 제한이 있는 뿅망치를 전략대로 이용하여 모든 거인이 센티보다 키가 작도록 만들 수 있는지 구한다.2. 전략은 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.3. 키가 1인 경우를 제외하고, 뿅망치에 맞은 거인은 키가 floor(맞은 사람의 키 / 2)가 된다.4. 전략이 먹히는 경우 YES와 최소 뿅망치 횟수를 출력하고, 전략이 먹히지 않는 경우 NO와 가장 큰 거인의 키를 출력한다. 제한시간 제한 : 1초 (최대 약 2000만번의 연산)메모리 제한 : 1024 MB인구수 N (1센티의 키 H (1뿅망치 횟수 T (1 문제 풀이1단계 .. 2024. 9. 9. [백준 시리즈] 14430번 : 실버 2 - 자원 캐기 / Python 제목 : 자원 캐기출처 : 백준 / https://www.acmicpc.net/problem/14430사용 알고리즘 : 다이나믹 프로그래밍 문제 설명1. (1, 1) 부터 (N, M)까지 자원을 탐색하여 얻을 수 있는 자원의 최대 숫자를 구해라2. 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있다. 제한시간 제한 : 2초메모리 제한 : 256 MBN(1 문제 풀이1단계 : 최대 시간복잡도는 얼마인가?최대 요소의 개수는 90000개이므로 O(NlogN) 이하의 알고리즘이 필요하다. 2단계 : 핵심적인 아이디어는 무엇인가?모든 칸에 대해 도달하였을 때의 자원의 최댓값을 구하고, 마지막 줄에서 최종적으로 최댓값을 구한다.(i, j)번째 요소에 도달하기 위해선 이전 위치가 (i, j)의 왼쪽 또는 위쪽이.. 2024. 9. 9. 이전 1 2 다음 728x90
