Scat

yongmin's dev blog

[BOJ] 1786번 찾기 - Python

"문자열 알고리즘 1"

문제 찾기 풀이 이중 for문을 통해서 하나하나씩 비교해가는 것은 O(NM) 시간복잡도를 가져 매우 비효율적이다. 위 문제는 O(N+M) 시간복잡도를 가지는 전형적인 KMP 알고리즘 문제이다. 탐색으로 얻은 정보를 최대한으로 활용하여 빠르게 일치하는 것을 확인하는 알고리즘이다. 먼저 접두사(prefix)와 접미사(suffix)에 대한 이해가 필요하...

Posted by Yongmin on September 22, 2021

Algorithm

"Algorithm"

목록 String KMP

Posted by Yongmin on September 22, 2021

[BOJ] 2357번 최솟값과 최댓값 - C++

"세그먼트 트리"

문제 최솟값과 최댓값 풀이 세그먼트 트리를 이용한 최솟값, 최댓값 구하기 문제이다. 파이썬 언어를 이용하였다. 기존 세그먼트 트리에서 구간에 대한 최솟값, 최댓값들을 저장해놓는다. 그 이후 왼쪽과 오른쪽을 비교하면서 최솟값, 최댓값을 구하면 되는 문제이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1...

Posted by Yongmin on September 21, 2021

[BOJ] 11659번 구간 합 구하기 - C++

"세그먼트 트리"

문제 구간 합 구하기 풀이 기본적인 세그먼트 트리를 활용한 구간합 문제이다. 세그먼트 트리를 구성하여, 구간에 맞는 값을 탐색해주면 되는 문제이다. 세그먼트 트리에 대한 자세한 설명은 Reference에서 너무 자세히 설명해주셨다. +) 세그먼트 트리에서의 특정 idx값 변경 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 void c...

Posted by Yongmin on September 16, 2021

[BOJ] 11505번 구간 곱 구하기 - C++

"세그먼트 트리"

문제 구간 곱 구하기 풀이 구간 합 문제에서 구간 곱으로 바뀐 것이다. +를 x로 바꾸었고, 모듈러 연산을 고려해준다. change를 해야되는 경우는, 0이라는 숫자 때문에 맨 끝 노드까지 새로 다시 연산을 하는 식으로 change가 되었다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2...

Posted by Yongmin on September 16, 2021

[BOJ] 2482번 색상환 - C++

"동적 계획법 3"

문제 색상환 풀이 dp문제이다. dp는 아직 많이 어려운 것 같다. dp[N][M] = N개의 색깔 중 인접하지 않게 M개를 칠하는 경우의 수를 의미한다. dp[i][j]는 i번째를 j번째 색깔로 칠하는 경우와 칠하지 않는 경우로 나뉜다. 칠하는 경우는, i번째가 j번째로 칠해져 있기 때문에 dp[i-2][j-1]의 경우의 수(i-2번째에 j-1번...

Posted by Yongmin on September 15, 2021

[BOJ] 1086번 박성원 - C++

"동적 계획법 3"

문제 박성원 풀이 모든 경우의 수를 탐색하는 경우 O(N!)로 시간초과, 메모리초과로 인해 실패했다. 모든 경우의 수를 확인한 시간 복잡도 O(N!)의 실패 코드 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 September 15, 2021

[BOJ] 17404번 RGB거리 2 - C++

"동적 계획법 3"

문제 RGB거리 2 풀이 dp를 활용한 문제로, 조건이 길게 적혀있긴 하지만, 다음의 도시는 이전 도시와 색깔이 같지 않게끔, 그리고 첫번째와 마지막 도시의 색깔이 같지 않으면 되는 문제이다. 첫번째 도시를 가장 바깥 loop에서 정해주고, N-1번째 도시까지 각각 그 전 최소값에 R, G, B 색상을 칠했을 때의 경우를 다 구한다. 그 이후 최솟...

Posted by Yongmin on September 14, 2021

[BOJ] 1311번 할 일 정하기 - C++

"동적 계획법 3"

문제 할 일 정하기 풀이 비트마스크 활용 문제이다. 비트마스크를 이용한 dp로 완전탐색을 하는 문제로서 많이 출제되는 문제이다. 먼저 pow(2,N)개의 dp배열을 선언한다. 이 dp배열은 N개의 일들이 각각 행해졌는지 그렇지 않은지의 정보를 담은 배열이다. 예를 들어, N이 3일 때, 011은 2번째 일은 행해지지 않고, 나머지 0, 1번째 일은...

Posted by Yongmin on September 13, 2021

C++ string split - C++

"Format"

용도 입력이 예를 들어 “hello world”라고 주어졌을 때, hello와 wolrd를 따로 입력을 받고 싶을 때 사용하는 코드이다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include<iostream> #include<string> #include&l...

Posted by Yongmin on September 13, 2021

FEATURED TAGS
Format BOJ C++ Python Algorithm
ABOUT ME

짱구