PS
22.08.24. 풀었던 문제
백준 단계별 28 DP와 최단거리 역추적 2618 경찰차 - top-down, bottom-up 둘 다 풀었음. 9019 DSLR 11779 최소비용 - dijkstra 할 때, 같은 edge이지만 cost가 다른 경우. ex) from 1 to 2 weight 10 / from 1 to 2 weight 20 이런 경우가 주어지면, 앞의 edge에 의해 update되고, 이게 최소임에도 불구하고 뒤의 edge에 의해 또 update 여부를 보기 때문에 조금 더 시간이 걸린다. 예외 사항 기억하자. 11780 플로이드 2 - 역시 역추적은 어렵다.
22.08.22. 풀었던 문제들
백준 단계별 28 DP와 역추적 14002 LIS 4 14003 LIS 5 - 이 2개는 예전에 푼 적 있었다. 12852 1로 만들기 2 - 답부터 거꾸로 찾아가면 됨. 말 그대로 역추적. void solve(){ int N; cin>>N; int INF = 987654321; vector dp(N+1, INF); vector prev(N+1); // prev[i] : i 이전에 온 수 dp[0] = 1; dp[1] = 0; for(int i = 2; i dp[i/2] + 1){ dp[i] = dp[i/2] + 1; prev[i] = i/2; } } if(i%3 == 0){ if(dp[i] > dp[i/3] + 1){ dp[i] = dp[i/3] + 1; prev[i] = i/3; } } } cout
Two Pointer, Sliding Window, Meet in the Middle ***TODO
two pointer 특 : 그냥 포인터 2개 움직이면 됨 sliding window 특 : 크기 고정한 two-pointer임. 주의할 점은 배열의 indexding. meet in the middle 특 : div&conquer인데 1번만 하는 경우임. 주어진 n으로 Brute-Force는 불가능 해 보이지만, n/2로 Brute-Force는 가능해 보일 때 사용하는 기법. 보통 n이 30~50정도일 때 쓸 수 있다. 앞 절반, 뒤 절반으로 나누고 앞 절반으로 뒤 절반을 탐색하면 된다. 그 절반을 정렬해도 $log2^{n/2} = log(n/2)$이기 때문에 $O(2^{n/2} * n/2)$에 풀린다.
2022 Google Kick Start Round E 참가 (22.08.20.)
1번은 간단한 직관으로 풀 수 있는 문제, n/5 + (n%5 == 0 ? 0 : 1)이었다. 2번은 binary search (upper bound)로 풀면 되는 문제였다. 다만 자기 자신이 나올 경우 예외처리를 해야 했었다. 3번은 palindrome matching 문제였다. 주어진 string에서 [0, 1~n/2]의 substring을 탐색해서 이게 palindrome이고 전체 반복된다면 이게 답이었다. n의 약수는 logn에 수렴하기 때문에 시간 내에 풀 수 있는 문제. 4번은 굉장히 복잡한 DFS 구현 문제였다. 조건이 [피자 배달 여부, 돈, 시간] 이렇게 3개였는데 상하좌우+제자리 대기 해서 각 탐색이 5^n이었고, DFS로 구현하면 안 되는 문제였다. 나중에 얘기 들어보니까 state를..
2022 군장병 코딩경진대회 참가 (22.08.19.)
1번 - 간단한 greedy + simulation 구현 문제 2번 - 문제 조건을 그대로 구현하면 되는 문제. map을 쓰면 되었다. 3번 - 아주 복잡했던 구현 문제. 4 by 4여서 전수탐색 DFS로 구현하면 되었는데, 구현하면서 신경 쓸 것이 너무 많아 결국 시간내에 풀지 못했다. 간단히 설명만 하자면 grid의 edge에서 dfs를 하면서, 사각형에는 n개의 edge개만 인접할 수 있는 조건이었는데 못 풀었다. 4번 - 3차원 DP 문제? 아마도. 아마 2솔한 것 같다.
2022 SCPC 1차 예선 참가 (22.07.15.)
1번 문제 건들다가, 증명을 못 해서 실패했다. 근데 내가 생각했던 직관이 맞았고 증명 과정에서 오류가 생긴 것이었음. 으악.
2022 UCPC 예선 참가 (22.07.02.)
뭔가 풀 수 있었던 것 같은데 못 풀었던 문제. 결과적으로 0솔이다... 추후에 upsolving하면서 풀었다. 25319 Twitch Plays VIIIbit Explorer - DFS로 푸는 문제였다.
22.08.20. 풀었던 문제들 - Codeforces #786 Div. 3 4/7
Codeforces #786 Div. 3 https://codeforces.com/contest/1674 Dashboard - Codeforces Round #786 (Div. 3) - Codeforces codeforces.com 결과 언제쯤 4/7의 벽을 통과할까. 그리고 C번 - 문제 이해를 잘못해서 뇌절을 좀 했다. D번도 직관으로 풀다가 틀려서 논리로 풀었고. 음.. 문제 풀 때, 완벽하게 증명된 경우에만 코드로 옮기는 걸 해야겠다. A번 문제에 낚였다. 주어진 조건이 10^9를 초과하지 않는 a, b를 구하라길래 sqrt 쓸 준비 하고 있었는데, x와 y가 둘 다 100보다 작다. 즉슨, a는 무조건 1로 두고 b는 y/x로 두면 된다는 말이다.... ll STANDARD = 100000000..
22.08.19. 풀었던 문제들
2022 군장병 코딩경진대회 총 4문제였다. 1번 문제는 greedy한 simulation 문제 2번 문제는 문제 조건을 그대로 구현하는 문제 3번은 DFS + 구현 문제였다. DFS 자체는 어렵지 않았는데 세부 구현이 너무 귀찮게 했다. 4번은 못풀었다.(보지도 못했다)
22.08.16. 풀었던 문제들
백준 단계별 26 Shortest Path 1753 최단경로 - dijkstra 문제 1504 특정한 최단 경로 - dijkstra 조금 응용 문제 11404 플로이드 - floyd-warshall 문제 11657 타임머신 - bellman-ford 문제 1956 운동 - floyd-warshall 문제 13549 숨바꼭질 3 - dijkstra 문제. max를 어리도 잡냐가 중요한 문제였다. 9370 미확인 도착지 - 1504와 비슷한 문제. 다만 처음에 문제를 잘못 이해해서 'route가 최소값인 target들'을 고르는 건줄 알았는데, 그게 아니라 's에서 target까지 shortest path weight == s -> g -> h(또는 h -> g) - target)의 weight가 같은 ta..
22.08.15. 풀었던 문제들 *** vector erase, remove
프로그래머스 코딩테스트 실전 대비 모의고사 3회 1번 주어진 대로 반복문을 써서 풀면 되는 문제. int solution(int give, int take, int cur) { int answer = 0; while(cur >= give){ // 현재 가지고 있는 게 주는 것보다 많으면 줄 수 이씅ㅁ int ret = (cur / give) * take; // 돌려받는 것 answer += ret; cur = cur - ((cur / give) * give) + ret; // 현재 개수 = 현재 개수 - 준 것 + 돌려받은 것 } return answer; } 2번 뒤에서 4개가 주어진 조건을 만족한다면, 그것을 빼고 추가하면 되는 문제. list를 쓸까 vector를 쓸까 고민하다가 결국 더 빠른 ve..
22.08.14. 풀었던 문제들
프로그래머스 코딩테스트 실전 대비 모의고사 2회 1번 3중포문으로 간단하게 풀면 되는 문제 int solution(vector number) { int answer = 0; int n = number.size(); for(int i = 0; i
22.08.13. 풀었던 문제들
Codeforces #805 Div. 3 Upsolving G번 빼고 했다.(아직 배우지 않은 lca) 프로그래머스 코딩테스트 실전 대비 모의고사 1회 1번 두 수에서 각 숫자의 개수를 xcnt, ycnt에 기록한 후 xcnt[i], ycnt[i] 중 작은 값 만큼 정답에 붙여넣으면 된다. 0은 special case기 때문에 따로 예외처리 해 주면 된다. #include #include using namespace std; string solution(string X, string Y) { vector xcnt(10, 0), ycnt(10, 0); for(char c : X){ xcnt[c-'0']++; } for(char c : Y){ ycnt[c-'0']++; } string answer = "";..
22.08.12. 풀었던 문제들 - Codeforces #805 Div. 3 4/7
백준 단계별 25 그래프와 순회 7562 Knight Moves 1697 Catch That Cow 2178 미로 탐색 1012 유기농 배추 2667 단지번호붙이기 1260 DFS와 BFS Codeforces #805 Div. 3 https://codeforces.com/contest/1702 Dashboard - Codeforces Round #805 (Div. 3) - Codeforces codeforces.com 결과 언제쯤 4/7의 벽을 통과할까. A번 주어진 수보다 작은 10^k 중 k의 최댓값을 찾으면 되는 문제다. void solve(){ int m; cin>>m; int value = 1000000000; vector rounds; while(value >= 1){ rounds.push_b..
22.08.11. 풀었던 문제들
백준 단계별 25 그래프와 순회 2606 바이러스 24445 알고리즘 수업 - 너비 우선 탐색 2 24444 알고리즘 수업 - 너비 우선 탐색 1 24480 알고리즘 수업 - 깊이 우선 탐색 2
22.08.10. 풀었던 문제들
백준 단계별 24 DP 2 2293 동전 1 dp[k] : k원 만드는 경우의 수라고 생각하면, 점화식은 dp[i] = dp[i] + dp[i - coin[j]]이 된다. 7579 앱 냅색 응용. 문제에서 주어진 대로라면 dp[i][j] = i번째 앱까지 봤을 때 memory j까지 사용했을 때 cost의 최솟값 이런 식으로 정의했겠지만, memory의 입력이 1천만, 앱의 종류가 100개기 때문에 두 개를 곱하면 1억이 넘어간다. 다른 방식으로 풀어야 한다. dp[i][j] = i번째 앱까지 봤을 때, cost j까지 사용했을 때 memory의 최댓값으로 생각하면 냅색과 같은 문제가 되고, "c - cost[a] >= 0 then dp[a-1][c-cost[a]] + memory[a]"의 점화식을 가지..
22.08.09. 풀었던 문제들
백준 단계별 24 DP 2 1520 내리막길 bottom-up dp로는 풀면 안 되는 게, 순서대로 채워나가면 역순으로 오는 예외가 있다. 따라서 무조건 top-down dp로 풀어야 한다. 사실상 DFS인데 이전에 구한 값을 memoization해서 사용해야 하는, DFS + DP이다. DFS 하는 것처럼 도착점에 다다르면 +1, 그렇지 않다면 다다르는 경우에 대해서만 그 경우의 수를 더해주었다. int dr[4] = {1, 0, -1, 0}; int dc[4] = {0, 1, 0, -1}; int board[501][501], dp[501][501]; int M, N; int search(int r, int c){ if(r == M-1 && c == N-1) return 1; if(dp[r][c] !..
22.08.08. 풀었던 문제들
백준 단계별 24 DP 2 오랜만에 보니까 정신이 혼미하군. DP 1은 대부분 1차원 array에서 해결할 수 있는 문제(+한 방향으로만 진행하면서 규칙을 찾으면 되는)였다면 DP 2는 대부분 2차원 array에서 해결할 수 있는 문제 같다. dp[i][j] = min{dp[i][m] + dp[m+1][j]}라던가, ... 11066 파일 합치기 dp[i][j] : index i부터 index j까지 합치는 데 필요한 cost 두 파일을 합칠 때 필요한 cost = 두 파일 크기의 합이다. 그러면 dp[i][i] = 0 dp[i][i+1] = files[i] + files[i+1]로 초기화 할 수 있고, 다음으로는 dp[i][i+2] = min{dp[i][i] + dp[i+1][i+2], dp[i][i+..
22.08.07. 풀었던 문제들
Codeforces #811 Div. 3 Upsolving D번 풀었고 G번 풀었음 F번은 내 수준으로 안 될 문제 같다. 오늘 안에 이거 끝내고 내일부턴 백준 다시 해야징~ 낮에는 업무한다고 바쁠거니까~으으윽
22.08.05. 풀었던 문제들 - Codeforces #811 Div. 3 4/7
Codeforces #811 Div. 3 https://codeforces.com/contest/1714 Dashboard - Codeforces Round #811 (Div. 3) - Codeforces codeforces.com 결과 많이 멀었군. A, B, C, E번은 시간 내에 풀고 제출했다. 7문제 중 4문제를 맞췄다. A번 주어진 시간인 H, M에 대해 입력 시간이 더 느리다면 그대로 두고, 더 빠르다면 24*60을 더한 후 [입력 시간 - 주어진 시간]의 최솟값을 구하는 손풀기 문제 int timeToInt(int H, int M){ return 60 * H + M; } pii intToTime(int t){ return {(t/60)%24, t%60}; } void solve(){ int ..
22.08.04. 풀었던 문제들
LIS 5 문제에 LIS 정리를 해 뒀고 pq 정렬 기준에 대한 정리도 해야 함(pq 첫 문제에 정리 해 둠) 22 binary search 12015 LIS 2 12738 LIS 3 14002 LIS 4 14003 LIS 5 23 priority queue 11279 최대 힙 1927 최소 힙 11286 절댓값 힙 1655 가운데를 말해요 상당히 재밌는 문제였다. pq 2개를 써서 가운데 값을 표현할 수 있다. [max heap] - middle value - [min heap]으로. 그러나 수가 짝수 개, 홀수 개일 때 middle value를 수정하는 것이 번거롭기 때문에 수가 짝수일 때는 max heap과 min heap의 크기를 동일하게 유지해서 max heap의 top을 middle value..
22.08.03. 풀었던 문제들
오랜만이다! 코로나19 (아마도) 확진 + 휴가로 인해 거의 2주 쉰 것 같다. 너무 오래 쉬니까 이렇게까지 오래 쉬어도 되나..?라는 생각밖에 들지 않는다. 전역 후에는 바로 취업할 수 있게(겨울학기에는 SES와 같은 겨울 인턴을 하지 싶다) 파이팅 하고, 학점도 열심히 들어서 포상휴가를 노려보자. 백준 단계별 22 이분 탐색 1920 수 찾기 10816 숫자 카드 2 1654 랜선 자르기 2805 EKO lower bound로 푸는 것보단 upper bound로 상한을 구한 후 거기서 -1을 하면 답이 된다. 2110 공유기 설치 '최대 설치 거리'를 binary search로 찾아가면 된다. '최대 설치 거리'를 기준으로 C개 설치 가불 여부를 따지면 O(n), 이걸 log n번 할 것이니 O(nl..
22.07.14. 풀었던 문제들
백준 단계별 21 분할 정복 11401 이항계수 3 - 페르마의 소정리 쉣... 페르마 그는 신인가? 풀이는 아래와 같다. 이항계수 $_{n}C_{k} = \tfrac{n!}{(n-K)! \cdot k!} = \tfrac{n \cdot (n-1)\cdots (n-k+1)}{k \cdot (k-1) \cdots 1}$이다. 편의를 위해 $A = n \cdot (n-1) \cdots (n-k+1), B = k \cdot (k-1) \cdots 1$라고 두자. 한편, 페르마의 소정리에 의해 나누는 값 1,000,000,007(p라고 두자)은 소수이므로 $a^{p-1} \equiv 1 \% p$이다. 그러면 이항계수를 $\tfrac{A}{B} \% p = (AB^{-1}) \% p = (AB^{-1} \time..
22.07.13. 풀었던 문제들
백준 단계별 21 분할 정복 2630 색종이 만들기 1992 쿼드트리 1780 종이의 개수 1629 곱셈 2740 행렬 곱셈 10830 행렬 제곱 11444 피보나치 수 6 행렬의 고속 거듭제곱, 이를 이용한 피보나치 수 O(logn)에 구하기 정리.