카테고리 없음
또 쉬게 될 것 같아 미리 적는 글
글 정리는 좀 대충했지만, 나름 열심히 했다고 생각한다. 하지만 지금 내 인생에 있어 아주 중요한 도전을 진행중이다. 그것은 최상위대학 편입이다. 그래서 한동안 블로그 글이 뜸해지지 않을까 싶다. 백준을 놓을 것은 아니지만, 문제만 풀고 정리를 미룰것 같다. 편입 성공하고 자랑스럽게 글을 적는 그날이 왔으면 좋겠다.
분류 전체보기
coding_test/BAEKJOON
백준 2230번 C++ 풀이
문제https://www.acmicpc.net/problem/2230시간 제한메모리 제한solved.ac 티어2초128MB골드 5풀이 밀린 문제 정리하기. 이 문제는 두가지 풀이가 존재한다. 첫번째 풀이는 투포인터이고, 두번째 풀이는 이분탐색이다. 사실 이 문제를 예전에 풀었을때에는 투포인터로 풀어냈고, 정리하려고 문제를 다시 봤을때에는 이분탐색으로 풀어냈다. 우선, 문제를 읽어보고 알 수 있지만, 수열의 원소의 순서는 크게 중요하지 않다. 따라서, 정렬을 해주었다. 투포인터가 됐던, 이분탐색이 됐던 정렬을 해주는게 용이하기 때문이다. 투포인터 풀이는 l, r 포인터를 모두 0에 위치시킨다. 두 원소의 차이가 m 이하라면 r 포인터를 오른쪽으로 한칸 옮긴다. m보다 크다면 l포인터를 오른쪽으로 옮긴다..
coding_test/BAEKJOON
백준 10942번 C++ 풀이
문제https://www.acmicpc.net/problem/10942시간 제한메모리 제한solved.ac 티어0.5초256MB골드 4풀이 문제를 보고 고민하다가 dp임을 깨달은 문제였다. 어떤 문자열이 회문이라면, 양 옆의 문자를 하나씩 떼어내도 회문이다. 예를 들어 12321라는 회문의 양 끝을 떼어보면 232로 회문임을 알 수 있다. 이를 통해 dp점화식을 세울 수 있다. 이 문제에서는 수열이기 때문에, 수열로 바꿔보면, 수열 seq에 대해dp[s][e] = seq[s] == seq[e] && dp[s+1][e-1] 이다. dp[s+1][e-1]은 재귀적으로 구할 수 있다. 또한, 길이 1의 부분수열은 항상 회문이기 때문에, dp[i][i]는 무조건 true이다. 이를 적용하여, [s, e] 구간을..
coding_test/BAEKJOON
백준 11693번 C++ 풀이
문제https://www.acmicpc.net/problem/11693시간 제한메모리 제한solved.ac 티어1초256MB골드 1풀이 역시 문제 날먹은 수학 이번 문제는 정수론 문제이다. 이 문제를 이해하기 위해서는 사전지식이 필요하다. 임의의 자연수 n에 대해 n이 다음과 같이 소인수분해된다고 해보자. 이때 n의 모든 약수의 합은 다음과 같이 나타낼 수 있다. 각 소인수에 대해 등비수열의 합을 구하고, 이 값들의 곱을 구하면 그것이 약수의 합이 된다. 해당 식을 전개하면 결국 n의 모든 약수들이 나오기 때문이다. 또한, 다음 성질이 성립한다는 것을 알 것이다. 이로 인해 n^m은 다음과 같이 나타낼 수 있다. 이제 이 모든걸 섞어보면 될 것이다. 결국 구해야하는 것은 다음 식이 된다. 각 항을 계..
coding_test/BAEKJOON
백준 1036번 python 풀이
문제https://www.acmicpc.net/problem/1036시간 제한메모리 제한solved.ac 티어2초128MB골드 2풀이 이 문제는 1339번을 풀어본 기억이 있어 쉽게 풀 수 있었다. 1339번 문제는 각 자릿수를 알파벳으로 바꾸고, n개의 숫자들을 더한 후, 알파벳에 숫자들을 매핑시켰을때의 최댓값을 구하는 문제이다. 자세한건, 문제 풀이한 글을 읽어보도록 하자. 백준 1339번 C++ 풀이https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있codejin.tistory.com 1339번 문제와 유사하게..
coding_test/BAEKJOON
백준 9177번 C++ 풀이
문제https://www.acmicpc.net/problem/9177시간 제한메모리 제한solved.ac 티어1초256MB골드 4풀이 dfs + dp로 풀었다. 첫번째 단어를 a, 두번째를 b, 세번째를 c라고 하자. c의 첫번째 글자은 a의 첫번째 글자이거나, b의 첫번째 글자일 것이다. 둘다일수도 있다. 현재 사용된 이 알파벳이 a일때와 b일때를 구분해서 계속 dfs로 들어가면서, 최종적으로 c를 만들 수 있는지를 판단한다. dfs를 하면서 지금 사용해야하는 a와 b, c의 인덱스를 인자로 넘겨준다. 이때, 재귀를 하면서 a, b의 같은 인덱스를 여러번 탐색할 수도 있다. 예를 들어, 다른 탐색에서 a와 b의 인덱스가 각각 1, 2일때 불가능함을 알았을때, 다른 경로로 1, 2에 다시 왔다면, 볼 이..
coding_test/BAEKJOON
백준 13511번 C++ 풀이
문제https://www.acmicpc.net/problem/13511시간 제한메모리 제한solved.ac 티어2초512MB플래티넘 3풀이 이 문제는 처음에 희소 테이블을 이용하는 문제인 줄 알았지만, 해보다보니 LCA를 응용해야하는 문제임을 알았다. (태그 까보고...) 임의의 두 노드 u, v에서 u -> v로 가는 경로라 함은 암묵적으로 최단경로를 의미한다. 그렇다면 u -> v의 경로는 LCA를 반드시 거칠 것이다. LCA를 구하기 위한 희소 테이블에 해당 조상으로 가기 위한 경로의 비용도 같이 저장한다. 이렇게 하면 LCA와 비용 모두 빠르게 구할 수 있다. 쿼리를 분석해보자. 1번 쿼리는 u -> v로 가는 경로의 비용을 출력하는 쿼리이다. u -> v의 경로는, u -> LCA_uv ->..
coding_test/BAEKJOON
백준 9019번 C++ 풀이
문제https://www.acmicpc.net/problem/9019시간 제한메모리 제한solved.ac 티어6초256MB골드 4풀이 진하게 나는 BFS의 냄새이다. DSLR 구현을 잘 해주고, 명령어 나열과 연산 후 숫자를 같이 큐에 넣어주면 답은 바로 나온다.코드#include #define endl '\n'using namespace std;int a, b;bool check[10001];int D(int n) { return (n * 2) % 10000;}int S(int n) { return (n + 9999) % 10000;}int L(int n) { int rot = n / 1000; n *= 10; n %= 10000; return n + rot;}int R(int n) { int rot ..
