Scat

yongmin's dev blog

[BOJ] 2606번 바이러스 - C++

"DFS와 BFS"

문제 바이러스 풀이 DFS와 BFS 중의 하나를 사용해서 function call이 몇번 일어났는지 count하면 되는 문제이다. DFS를 이용했다. 소스 코드 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 #include <iostr...

Posted by Yongmin on July 16, 2021

[BOJ] 1260번 DFS와 BFS - C++

"DFS와 BFS"

문제 DFS와 BFS 풀이 기본적인 DFS와 BFS를 구현하는 문제였다. 인접행렬을 만드는 법, 방문을 기억하는 visit함수와 함께 재귀를 이용한 DFS, 큐를 이용한 BFS 구현방법을 익힌 문제였다. 소스 코드 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 15, 2021

[BOJ] 7579번 앱 - C++

"동적 계획법2"

문제 앱 풀이 냅색 문제이다. 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ...

Posted by Yongmin on July 13, 2021

[BOJ] 2629번 양팔저울 - C++

"동적 계획법2"

문제 양팔저울 풀이 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 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 5...

Posted by Yongmin on July 12, 2021

[BOJ] 10942번 팰린드롬? - C++

"동적 계획법2"

문제 팰린드롬? 풀이 팰린드롬 : 왼쪽에서 읽었을 때랑, 오른쪽에서 읽었을 때랑 똑같은 숫자 배열을 의미한다. 단순하게 맨끝에서부터 중간까지 일일이 비교하며 팰린드롬이 true인지 false인지 판단하는 것은 시간초과가 일어난다. 그래서 다이나믹 프로그래밍을 사용하는데, dp[i][j] = i~j까지 팰린드롬인가(=1), 아닌가(=0)인지 담은 배열...

Posted by Yongmin on July 8, 2021

[BOJ] 2293번 동전 1 - C++

"동적 계획법 2"

문제 동전 1 풀이 1번째 동전으로만 1~M까지 만들 수 있는 경우의 수들을 체크, 1~2번째 두개의 동전으로만 1~M까지 만들 수 있는 경우의 수들을 체크해 나가며, 1~N번째의 동전으로 M을 만들 수 있는 경우의 수를 확인하는 문제이다. i번째까지 동전으로 M을 만들 수 있는 경우의 수는 i-1번째까지 동전으로 M을 만들 수 있는 경우의 수 + ...

Posted by Yongmin on July 7, 2021

[BOJ] 2261번 가장 가까운 두 점 - C++

"정렬"

문제 가장 가까운 두 점 풀이 Reference에서 코드를 가지고 왔다. 알고리즘이 상당히 복잡하다. 먼저, O(N^2)으로 하면 시간초과가 나는 문제이다. 시간초과를 면하기 위해서 알고리즘들이 추가가 되는데 알고리즘은 다음과 같다. x축으로 정렬된 값 중 start와 end의 중간값인 mid를 기준으로 왼쪽 오른쪽 구간으로 나눈다. 이 구간에...

Posted by Yongmin on July 6, 2021

[BOJ] 6549번 히스토그램에서 가장 큰 직사각형 - C++

"분할정복"

문제 히스토그램에서 가장 큰 직사각형 풀이 Reference를 참조하였다. O(N^2)으로 문제를 풀었지만, 시간초과로 인해 실패하였다. 시간초과를 면하기 위한 알고리즘은 분할정복 + 세그먼트트리를 이용한 알고리즘이다. 0 ~ N-1구간에서 높이의 최솟값인 index를 찾고 그 index를 통해 넓이를 구해 나가 최대 넓이를 찾는 문제이다. 세그먼트...

Posted by Yongmin on July 5, 2021

[BOJ] 11066번 파일 합치기 - C++

"동적 계획법 2"

문제 파일 합치기 풀이 동적계획법 문제이다. DP[i][j] = i부터 j까지의 합치는데 필요한 최소 비용 으로 정의한다. for문 제일 바깥쪽 i는 페이지를 합치는 사이즈 - 1 을 의미한다. 즉, i = 1이면 두개를 서로 합치는 것이다. for문 중간에 위치한 j는 합치는 것을 진행하는 시작점이다. for문 제일 안쪽 k는 중간에 분리하는 지점...

Posted by Yongmin on July 4, 2021

[BOJ] 1655번 가운데를 말해요 - C++

"우선순위 큐"

문제 가운데를 말해요 풀이 우선순위큐, 트리의 이해가 필요한 듯 하다. 아래 코드는 Reference를 참조하였다. 중간값을 구하기 위한 알고리즘은 다음과 같다. maxheap과 minheap을 만든다. testcase의 수들을 maxheap과 minheap을 번갈아서 넣어서(maxheap부터 넣기 시작.) maxheap.size() &...

Posted by Yongmin on July 3, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구