Scat

yongmin's dev blog

[BOJ] 12852번 1로 만들기 2 - C++

"동적 계획법과 최단거리 역추적"

문제 1로 만들기 2 풀이 top-down(bfs) 방식으로 구현하다가, bottom-up 방식으로 바꿔 풀었다. n까지 도달하기 위해 걸린 cnt를 저장하고 있는 dp배열을 이용하여 1부터 시작하여, 기존 값과 비교하여, 새로 구한 값이 더 작으면 dp값에 넣는 식으로 코드가 진행된다. 이 때, before함수를 통해 그 전의 값들이 먼지 역추적...

Posted by Yongmin on August 7, 2021

[BOJ] 1644번 소수의 연속합 - C++

"투 포인터"

문제 소수 구하기 풀이 에라토스테네스의 체를 이용하여 범위 내의 소수들을 찾은 뒤, 그 소수들의 배열 중 부분배열의 합이 N이 되는 것들을 체크하면 되는 문제이다. 직접 짠 코드는 97%에서 out of bounds로 인한 문제가 생겨, Reference에서 가져온 코드를 첨부한다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 1...

Posted by Yongmin on August 4, 2021

[BOJ] 1929번 소수 구하기 - C++

"기본 수학2"

문제 소수 구하기 풀이 특정 범위내의 소수를 찾을 수 있는 빠른 방법 중 하나이다. 소수가 아닌 수들을 거르는 논리인데, 2부터 시작하여, 2의 배수들을 다 제거하고, 3의 배수들을 다 제거… i*i<=최대범위값을 만족하는 i의 배수들은 소수가 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1...

Posted by Yongmin on August 4, 2021

[BOJ] 1806번 부분합 - C++

"투 포인터"

문제 부분합 풀이 S이상인 부분합 중 가장 배열의 크기가 작은 값을 출력하는 문제이다. start와 end사이의 모든 값을 다 더하도록 설정한다. start, end를 0으로 시작하여, start가 end를 넘겼을 때, end가 N을 넘겼을 때 while문은 종료된다. while문 안에서는 sum이 S보다 작다면, end를 늘려 값을 추가하여 su...

Posted by Yongmin on August 4, 2021

[BOJ] 2470번 두 용액 - C++

"투 포인터"

문제 두 용액 풀이 sort를 통해 주어진 수들을 오름차순으로 정렬한 뒤, start = 0, end = testcase.size()-1로 시작하여, 양쪽을 좁혀 나가며 조건에 맞는 것들을 탐색해낸다. 0에 가까운 수를 찾는 것이므로, sum이 음수이면, start를 키우고, sum이 양수이면 end를 줄여 0으로 가깝게 만든다. 소스 코드 1...

Posted by Yongmin on August 3, 2021

[BOJ] 3273번 운동 - C++

"투 포인터"

문제 두수의 합 풀이 sort를 통해 주어진 수들을 오름차순으로 정렬한 뒤, start = 0, end = testcase.size()-1로 시작하여, 양쪽을 좁혀 나가며 조건에 맞는 것들을 탐색해낸다. 같으면, cont++를 한 뒤, start++, end–를 하고, 합이 x보다 값이 크다면 end– 를 하여 값을 줄여보고, 합이 x보다 값이 작...

Posted by Yongmin on August 3, 2021

[BOJ] 1956번 운동 - C++

"최단경로"

문제 운동 풀이 플로이드=와샬 알고리즘을 이용해 풀었다. 기본 플로이드-와샬과 크게 다를 것이 없다. 문제의 원하는 답인 start에서 시작해서 start로 끝나는 거리 중 최소 거리를 찾으면 된다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 ...

Posted by Yongmin on July 31, 2021

[BOJ] 10217번 KCM Travel - C++

"최단경로"

문제 KCM Travel 풀이 다익스트라 응용 문제이다. 기존에 출발지, 도착지, 거리만 존재하던 경우에서 비용까지 고려하는 문제로 확장된 것이다. 기존에 i번째까지 도달하는데 가장 짧은 시간을 의미하는 dist[i]에서 dist[i][j] 는 i에 도달할 때 j비용으로 도달할 수 있는 최소 시간을 의미로 2차원으로 확장해서 풀어지는 문제이다. ...

Posted by Yongmin on July 31, 2021

[BOJ] 11404번 플로이드 - C++

"최단경로"

문제 플로이드 풀이 플로이드 와샬(시간복잡도 : O(V^3) 알고리즘 문제이다. 음의 가중치가 없기에, 다익스트라 알고리즘으로도 풀 수 있는 문제인데, 다익스트라 알고리즘의 시간복잡도는 인접리스트를 사용했을 시 O(ElogV)로 간선(E)가 너무 많다면 시간복잡도에서 불리할 수 있다. 플로이드 와샬은 from에서 to로 곧장 가는 경우와 경유지를...

Posted by Yongmin on July 28, 2021

[BOJ] 11657번 타임머신 - C++

"최단경로"

문제 타임머신 풀이 벨만-포드 알고리즘에 대한 문제이다. 다익스트라는 가중치가 양수로만 이루어져있을때 사용 가능한 반면, 시간 복잡도 O(|V| X |E|)인 벨만 - 포드는 음수일때도 사용이 가능하다. 벨만포드 알고리즘은 정점 갯수 N이 주어졌을 때, N-1번동안 모든 간선을 이동할 때마다 최저값을 갱신해나가는 것을 시작으로 하여, 그 이후 한...

Posted by Yongmin on July 27, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구