문제https://www.acmicpc.net/problem/6593시간 제한메모리 제한solved.ac 티어1초128MB골드 5풀이 밀린 문제 정리하기이다. 짬짬히 정리하는 나 자신. 이대로만 가자. 문제만 읽어봐도 이 문제는 그래프 탐색문제임을 알 수 있다. 거기에 최단경로를 찾아야 하기 때문에 bfs를 쓰면 될 것이다. 특이한 점은 이 문제는 3차원 bfs라는 것이다. 2차원에서 시작점과 출구를 잇는 최단 경로를 찾는 것이 아닌, 3차원 공간에서 시작점과 출구를 이어야 하기 때문에, 위치정보를 저장하고 이동하는데 유의해야 한다.코드#include #define endl '\n'using namespace std;int l, r, c;vector> building;tuple st;void input..
문제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 원래라면 해당 쿼리를 처리하기 위해서 다음의 영역의 각 숫자들을 더해야 할 것이다...
Happy New Year!24년 8월에 블로그를 다시쓰겠다던 다짐을 한지 어언 5개월이 지났다. 정말 유감스럽게도 그 뒤로 블로그를 쓰질 않았다.구차하고 추하지만 또또또 변명이나 해보도록 하자. 이번엔 또 왜 블로그를 안썼는가? 회사 출퇴근을 하는 삶이 그렇게 힘들줄은 몰랐다. 어른, 선배들이 회사가 학교랑은 비교도 할 수 없을 정도로 힘들다고 한게 이해가 갔다. 필자는 24년 8월 19일부터 10월 11일까지 약 2달간 회사에서 QA(테스터)업무를 담당했다. 사실 알바느낌으로 들어간거였고, 개발 회사가 어떤 식으로 돌아가는지 경험하기 위해 운 좋게 기연을 얻었으니 말이다. 내가 사는 곳과는 거리가 있어 출퇴근 시간이 1시간 반정도 걸렸으며, 8시반 to 5시반 이라는 근무시간은 정말 개인공부를 하기가..
