PS/PS Log
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
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)에 구하기 정리.
22.07.12. 풀었던 문제들
백준 단계별 19 스택 10828 스택 10773 Zero That Out 9012 Parenthesis 4949 The Balance of the World 1874 스택 수열 17298 오큰수 백준 단계별 20 큐, 덱 18258 큐 2 2164 카드2 11866 요세푸스 문제 0 1966 Printer Queue 10866 덱 1021 회전하는 큐 5430 Interger Lists
22.07.11. 풀었던 문제들
Codeforces #787 Div. 3 Upsolving F 백준 단계별 18 greedy 11047 동전 0 1931 회의실 배정 11399 ATM 1541 잃어버린 괄호 13305 주유소
22.07.10. 풀었던 문제들
BOJ 단계별 17 누적합 11659 구간 합 구하기 4 2559 수열 - partial sum으로 해도 되고, sliding window로 풀어도 된다. 근데 문제 특성상 k가 주어지기 때문에 sliding window로 푸는 게 더 쉬울 듯. 16139 인간-컴퓨터 상호작용 - 알파벳 별로 누적합을 만들어야 했음 10986 나머지 합 - 흥미로운 문제. psum을 구할 때 % 연산을 하고, 해당 값이 몇 번 나왔는지를 기록한다. 그리고 모든 %값의 개수에 대해, combination 2를 택해주고(% M이 같은 두 구간을 뺀다면 그 구간은 M의 배수이다. 이 구간 중 순서 상관없이 2개를 택하는 경우의 수), 마지막으로 0이 나온 횟수(첫번째부터 i까지 %K == 0이라는 의미)를 더해주면 된다. i..
22.07.09. 풀었던 문제들 - Codeforces #787 Div. 3 4/7 *** euler tour, path, circuit
BOJ DP 11054 가장 긴 바이토닉 부분 수열 2565 전깃줄 9251 LCS 12865 평범한 배낭 9465 스티커 (DP) void solve(){ int n; cin>>n; vector stickers(2, vector(n)); for(int i = 0; istickers[i][j]; } } vector dp(2, vector(n, 0)); // dp[i][j] : i번째 row, j번째 col의 sticker를 선택했을 때 최댓값 dp[0][0] = stickers[0][0]; dp[1][0] = stickers[1][0]; if(n >= 2){ dp[0][1] = dp[1][0] + stickers[0][1]; dp[1][1] = dp[0][0] + stickers[1][1]; } for(..
22.07.07. 풀었던 문제들
BOJ 단계별 DP 1단계 1463 1로 만들기 10844 쉬운 계단 수 2156 포도주 - 이문제.. 빡세다 #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pis; int main(void) { cin.tie(0); cout.tie(0); std::ios_base::sync_with_stdio(0); ////////////////////// write your code below int n; cin>>n; vect..