목록2020/02/28 (3)

기술 블로그

16957번 체스판 위의 공

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 이렇게 접근하지 말고, 아래와 같이 접근을 ..
알고리즘 문제/BOJ 2020. 2. 28. 18:59
Exchange arguments (sorting with dp)

https://codeforces.com/blog/entry/63533 Exchange arguments (sorting with dp) Greedy그리디탐욕
알고리즘 2020. 2. 28. 17:06
18511번 큰 수 구성하기

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..
알고리즘 문제/BOJ 2020. 2. 28. 12:49
이전 Prev 1 Next 다음