문제https://www.acmicpc.net/problem/15650 시간 제한메모리 제한solved.ac 티어1초512MB실버 3풀이이 문제를 무작정 중첩반복문으로 풀기에는 어려워보인다. 중첩반복문을 쓰게되면 시간복잡도의 문제도 생기지만, 그 전에 몇번 중첩해야할지가 애매해진다. 숫자를 M개를 선택해야하는데, 이는 단순하게 생각해서 M중첩 반복문이 필요하다는 뜻이 될테니 말이다. 따라서 반복문만 사용하는 것이 아닌, 재귀함수와 섞어, 어떤 숫자를 선택했을때, 그 뒤의 숫자부터 다시 탐색하도록 작성하였다. 그러기 위해 제일 최근에 선택한 숫자가 무엇인지, 지금 몇개를 선택했는지를 재귀하면서 넘겨주고, 항상 이전에 선택한 숫자보다 더 큰 숫자부터 다시 탐색을 하는 방식을 선택하였다. 답을 출력하기 용이하..
문제 시간 제한메모리 제한solved.ac 티어1초256MB골드 3풀이이번에도 밀린 문제 정리하기다. 저번에는 두 용액이었지만, 이번엔 세 용액이다. 두 용액에 대한 문제는 다음 글을 참고하자.https://codejin.tistory.com/270 백준 2470번 C++ 풀이문제https://www.acmicpc.net/problem/2470 시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이밀린 문제 정리하기 2탄이다. 이번 문제는 투포인터 문제이다. 직관적으로 떠올릴 수 있는 방법은 중첩반복codejin.tistory.com 용액이 세개로 늘어났다고 해서 쫄 필요가 없다. 이 문제도 투포인터로 풀이가 가능하다. 이 문제를 브루트포스로 푼다면 O(N^3)이 나올 것이다. 5000^3은 ..
문제https://www.acmicpc.net/problem/2470 시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이이번에도 밀린 문제 정리하기이다. 이번 문제는 투포인터 문제이다. 직관적으로 떠올릴 수 있는 방법은 중첩반복문을 통해 브루트포스를 하는 것이지만, 시간복잡도가 O(N^2)가 나오고, N은 최대 10만이기 때문에 불가능한 방법이다. 따라서 투포인터를 통해 O(N)의 시간복잡도로 탐색하면 될 것이다. 용액의 특성값을 오름차순으로 정렬하고, 포인터를 각각 맨 앞과 맨 뒤에 둔다. 입력은 세가지 경우로 나뉜다. 모두 양수인 경우모두 음수인 경우음수 양수 섞인 경우어떻던 간에 모두 양수라면 오른쪽 포인터(맨 뒤에 있던 포인터)를 왼쪽으로 당겨올수록 0에 가까워 질 것이고, 모두 음..
문제https://www.acmicpc.net/problem/1019시간 제한메모리 제한solved.ac 티어2초128MB플래티넘 5풀이밀린 문제 정리하기의 첫 단추를 끼울 문제이다. 이 문제는 사실 알고리즘이라기보단 수학적인 규칙을 찾는 문제에 가까웠다. 아는 지인이 이걸 풀었길래 나도 시도해봤다가 며칠동안 고민했던 문제이다. 이 문제를 이해하기 위해 예제를 하나씩 분석해보자. 예제입력 2부터 보자. 입력이 7이다. 페이지를 나열하면 다음과 같을 것이다.1, 2, 3, 4, 5, 6, 71~7까지 모두 1번씩 나왔기 때문에 답은 0 1 1 1 1 1 1 1 0 0이 될 것이다. 여기까지만 보면 잘 모르겠다. 예제입력 3을 보자. 입력은 19이다. 나열해보면1, 2, 3, 4, 5, 6, 7, 8, 9,..
문제https://www.acmicpc.net/problem/16953시간 제한메모리 제한solved.ac 티어2초512MB실버 2 풀이1이 문제는 정말 생각할 수 있는 부분이 많은 좋은 문제라고 생각한다. 일단 문제를 보고 바로 든 생각은 그래프 문제구나 싶었다. 실제로 두 과정을 통해 a를 b로 만드는 최소 연산 횟수 + 1(a에서 b로 이동하는 최단경로)을 구하는 것이기 때문이다. a, b의 최댓값이 10^9로 약 2^30에 근접하고, 두 연산이 모두 곱하거나(2x), 곱하고 더하는 연산(10x + 1)이기 때문에 아무리 큰 케이스를 주더라도 연산은 30번에 근접할 것이다. 그리고, 나름의 최적화를 시도하여 큰 값부터 우선 처리하면, 더 빠르게 구할 수 있을거라고 생각하여 우선순위큐를 사용하여 bf..
문제https://www.acmicpc.net/problem/11660(25.01.14 현재 백준사이트의 미리보기 블록이 만들어지지 않는다.) 시간 제한메모리 제한solved.ac 티어1초256MB실버 1풀이본래 구간 합 구하기 문제들은 세그먼트 트리를 사용하는 문제들이 꽤 있는데, 이번 문제는 누적 합 알고리즘을 사용하는 것 만으로도 충분한 문제이다. 각 행에 대해 누적합 배열로 변경한 후, 입력받는 쿼리에 대해 누적합 배열을 이용하면 시간복잡도 안에 끝낼 수 있을 것이다. 문제의 표를 누적합 배열로 바꾸면 다음과 같을 것이다.1361025914371218491522 예제입력1의 첫번째 쿼리는 다음과 같다.2 2 3 4 원래라면 해당 쿼리를 처리하기 위해서 다음의 영역의 각 숫자들을 더해야 할 것이다...
회사생활을 하니 정말 개인시간이라는걸 찾아볼수가 없는 것 같다. 직장인분들 정말 존경합니다. 너무 하위문제에 발목잡혀있던 것 같다. 정작 나한테 필요한 내용은 볼 시간도 없이, 하위 문제를 수십개씩 계속 풀다보니, 시간만 버린 듯 하다. 코드트리라는 좋은 서비스를 제대로 이용하지 못한 것 같다. 나중에 또 열리면 그때가선 제대로 써봐야겠다. 각설하고 몇문제 정리나 해보자. Novice Mid정렬https://www.codetree.ai/missions/5/problems/line-up-students-2?&utm_source=clipboard&utm_medium=text더보기#include #define ALL(X) X.begin(), X.end()#define endl '\n'using namespac..
본인은 5주차 화요일인 8/13부터 시작했기 때문에, 5주차부터 적는다. 최대한 매일 적어보겠다. 자잘한 문제는 적기 귀찮기도 하고, 테스트문제가 앞의 연습문제들의 총망라이기 때문에, 테스트 문제만 적는다. Novice Mid1. 함수 - 값을 반환하지 않는 함수https://www.codetree.ai/missions/5/problems/find-the-least-common-multiple?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.www.codetree.ai 문제 풀이더보기from math import ..
