Scat

yongmin's dev blog

[BOJ] 11725번 트리의 부모 찾기 - C++

"트리"

문제 트리의 부모 찾기 풀이 트리의 부모를 찾는 문제이다. 인접리스트에서 dfs방식으로 부모와 자식 노드들을 result 배열에 담아 출력하였다. 소스 코드 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 29 30 31 32 33 34 35 36 37 38 ...

Posted by Yongmin on August 17, 2021

[BOJ] 11780번 플로이드2 - C++

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

문제 플로이드2 풀이 플로이드-와샬 : O(N^3) 알고리즘을 이용한 문제이다. 역추적을 위해서 경유지인 k를 저장해놓고, 그 start와 k, 그리고 k와 end들의 경유지를 찾아내는 재귀함수꼴로 역추적을 진행한다. 예를 들어, 2에서 3으로 갈 때, 경유지 5를 지난다면 2에서 5로 갈 때 경유지가 있는지 체크, 5에서 3으로 갈 때 경유지가...

Posted by Yongmin on August 16, 2021

[BOJ] 11779번 최소비용 구하기 2 - C++

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

문제 최소비용 구하기 2 풀이 다익스트라 문제이다. 기본 다익스트라에서 크게 다를게 없다. Reference에서 코드를 가져왔다. 직접 작성한 코드는 시간초과가 계속 일어나는걸 보아, 다른 성공한 코드에서는 while문 안에서 continue를 통해 시간 절약을 해주는 것이 차이가 있는 것 같다. 소스 코드 1 2 3 4 5 6 7 8 9 10...

Posted by Yongmin on August 13, 2021

[BOJ] 9019번 DSLR - C++

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

문제 DSLR 풀이 BFS를 이용한 문제이다. 값들과 string을 pair로 하여 queue에 저장하는 식으로 문제를 접근하였다. Reference에서 코드를 가져왔다. 네 자리수를 왼쪽과 오른쪽으로 이동하는 방법을 기억해두면 좋을 것 같다. 왼쪽으로 이동 : nx = (x % 1000) * 10 + (x / 1000); 오른쪽으로 이동 : ...

Posted by Yongmin on August 13, 2021

[BOJ] 13913번 숨바꼭질 4 - C++

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

문제 숨바꼭질 4 풀이 단순 BFS의 경로 역추적 문제이다. Before 함수를 통해 그 전 경로들을 계속 저장해나가는 방식으로 풀이하였다. Reference 코드를 첨부한다. 소스 코드 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 29 30 31 32 3...

Posted by Yongmin on August 12, 2021

[BOJ] 2618번 경찰차 - C++

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

문제 경찰차 풀이 DFS, DP를 이용한 최단거리 확인과 역추적 문제이다. 처음에는 그리디하게 매 경우때마다 최소 거리를 더하면 되는 코드를 작성했지만, 이는 결과적으로 전체 사건을 해결하였을 때 최소 거리라는것을 보장하지 못한다. Reference에서 코드를 가져왔다. DP[i][j]는 경찰차 1이 i번째 사건을, 경찰차 2가 j번째 사건을 해결...

Posted by Yongmin on August 12, 2021

[BOJ] 9252번 LCS 2 - C++

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

문제 LCS 2 풀이 기존 LCS 문제에서 역추적이 추가된 문제이다. 역으로, 끝에서부터 시작하여, 해당 index에서 위와 왼쪽 값들을 비교하여, 큰 곳으로 이동하고, 만약 위와 왼쪽 값과 해당 인덱스의 값이 모두 다를 때에는 반대로 왼쪽 대각선 위로 올라서 string에 추가를 하여 결과를 도출한다. 코드는 Reference에서 참조하였다. ...

Posted by Yongmin on August 9, 2021

[BOJ] 14003번 가장 긴 증가하는 부분 수열 5 - C++

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

문제 가장 긴 증가하는 부분 수열 5 풀이 12015번에서 최대 부분 수열을 출력하는게 추가된 문제이다. 12015번에서는 최대 길이만을 보장할 뿐, result 배열의 값이 최대 부분 수열이라는 것을 의미하는 것은 아니다. 그래서 추적을 하기 위해서 index를 labeling하여 최대 부분 수열을 출력하게끔 한다. 코드는 Reference에서 ...

Posted by Yongmin on August 9, 2021

[BOJ] 14022번 가장 긴 증가하는 부분 수열 4 - C++

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

문제 가장 긴 증가하는 부분 수열 4 풀이 dp를 이용한 기존 가장 긴 증가하는 부분 수열에 부분 수열을 출력하는 내용이 추가된 문제이다. dp의 최댓값에서 1씩 빼가면서 수열의 값들을 출력함으로써 역추적을 진행하였다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2...

Posted by Yongmin on August 8, 2021

[BOJ] 1450번 냅색문제 - C++

"투 포인터"

문제 냅색문제 풀이 난이도가 있는 문제이다. Reference에서 참조한 코드를 첨부한다. 이 문제는 물건의 개수 N이 30이여서, 전체 물건들을 넣고 안넣고의 경우의 수 2^30의 연산 횟수가 필요하다. 이는 시간 초과로 이어져 이를 해결하기 위해 투 포인터를 이용해 해결한다. 먼저, A그룹(0~N/2-1), B그룹(N/2~N) 두 그룹으로 물건...

Posted by Yongmin on August 7, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구