기술 블로그

https://www.acmicpc.net/problem/3197 # 시간 초과 # 복습 # bfs # 이분 탐색 # 생각 # 아이디어 # queue # 팁 tip 깨달은 점 : 행과 열이 100 이상이면 퍼져나가는 시점을 기록하는 방법을 써보자. 얼음을 한 번 녹일 때마다, bfs로 탐색해서 검사하는 것은 시간 초과가 발생한다. 그래서 시간을 줄이려면 queue를 여러 개 사용해서 구현하거나 약간의 아이디어가 필요하다. 우선 내 코드에서의 핵심은 Map[행][열] 배열이다. 1. 우선 'L'이나 '.'를 melt_queue에 push하여, 최대로 얼음을 녹이는 시점을 구한다.(모든 얼음이 다 녹는 시점)2. 위에서 최대 시점을 구할 때, Map[행][열] 배열에 각 위치에 맞는 얼음이 녹이는 시점을 기..

https://www.acmicpc.net/problem/16957 # 시간초과 # 복습 # 구현 # 생각 # 아이디어 # 유니온 # 파인드 # Find # 경로 # 압축 # Union 처음 구현했을 때, 시간 초과가 발생했다. 이 문제의 핵심은 경로 압축(Path Compression)이다. 간단하게 말하자면, 30에서 계속 최솟값을 통해 가다가 2로 도착하였다면, 또 다른 숫자인 50에서 출발하여 최솟값을 통해 계속 진행하다가 30을 만나면 더이상 진행할 필요가 없다는 뜻이다. 즉, 30에서 이미 2로 도착하였기 때문이다. 이 문제는 Union-Find에서 Find를 활용하는 문제이다. 예제 1로 설명을 하겠다. 우선 예제 1을 1 3 45 6 78 9 2 이렇게 접근하지 말고, 아래와 같이 접근을 ..

https://codeforces.com/blog/entry/63533 Exchange arguments (sorting with dp) Greedy그리디탐욕

https://www.acmicpc.net/problem/18511 복습 코테 백트래킹 dfs backtracking 추천 필수 코딩 처음에 dfs 구현할 때 숫자 비교를 string으로(stoi()) 하려다가 생각해보니 num과 ten 변수를 활용하여 n과 비교할 숫자를 만들 수 있었다. num = 0, ten = 1로 시작하면 n과 비교할 숫자를 만들 수 있다. 1234567891011121314151617181920212223242526272829303132333435363738#include using namespace std; int n, k, ans;vector v; void dfs(int num, int ten){ if (num > n) { return; } ans = max(ans, num..

https://www.acmicpc.net/problem/16958 다익스트라 : https://hsdevelopment.tistory.com/389 # jh05013 # 복습 # 구현 # 생각 # 필수 # 아이디어 # 맨하탄 # 맨하튼 # 거리복습 필수 다익스트라 플로이드 코테 코딩 추천 bfs로 풀려다가, visit 방문 처리가 복잡할 것 같아서 다익스트라로 풀었다. vector p하고 우선순위 큐인 pq의 first, next 구분을 잘 하자. 또한, 무작정 텔레포트 시간을 넣는 것이 아니라 실질적인 거리와의 비교를 통해 더 작은 것을 넣어야 한다. 그런데, 다익스트라로 푸니 시간이 무려 1132ms나 걸렸다. 플로이드 와샬도 868ms나 걸렸다. 하지만 채점 현황을 보니 0ms 코드도 있었다. 더..

https://www.acmicpc.net/problem/16954 # 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각 3차원 방문 visit 배열을 활용하는 문제이다. 주의할 점은 현재 위치에 서 있을 때는 방문 처리 여부와는 상관 없이 무조건 queue에 넣어야 한다. 이유는 어떠 한 경우에서 (r, c)에서 현재 위치에 서 있었을 때, 방문 처리를 하면, 다른 경우에서 (r, c)에 대해 그 자리에 있을 수 없다. 이 외에는 방문 처리를 이동 방향에 따라 표시해준다. visit[행][열][이동 방향] = 어느 방향에서 (행, 열)로 왔는지 방문 처리 123456789101112131415161718192021222324252627282930313233343536373839404..

https://www.acmicpc.net/problem/18291 https://www.acmicpc.net/problem/1629 n이 4일 경우, 1001110110111111 이렇게 4개를 생각할 수 있다. 여기에서 시작과 끝을 제외하면, 00100111 이고, 이것은 bit 연산을 생각할 수 있다. 즉, bit가 2일 때, 나올 수 있는 총 경우의 수는 2^2이고, 2^(n-2)이 답임을 알 수있다. (예시)000100010001011110101111비트 수 = 3, 총 개수 = 2^3 하지만 숫자가 워낙 클 경우 단순히 2^(n-2)의 작업을 할 때, Stack Over Flow나 O(n)의 시간이 걸리게 된다. 하지만, 나머지를 적용할 수 있고, O(log n)의 알고리즘이 있다. 여기에서 ..

https://www.acmicpc.net/problem/11967 # 복습 # 추천 # bfs # 필수 # 코딩 # 코테 # 구현 # 생각 처음에는 단순히 현재 위치(x, y)에서 킬 수 있는 방을 모두 키고, 모두 방문하는 식으로 구현하였으나, 틀렸다. 왜냐하면, 불을 켜도 방문할 수 없는 방이 있기 때문이다.(상, 하, 좌, 우로만 이동) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104..