본문 바로가기

분류 전체보기

 (208)
[ 백준 / C++ ] 2138 : 전구와 스위치 [ 문제 ] 2138번: 전구와 스위치 [ 접근방법 ] i(1 전구를 왼쪽부터 비교해가면서 진행해 나간다고 하자.즉, 스위치를 왼쪽부터 순서대로 누른다고 하자. (일단 1번 스위치 스킵), 만약 1번 전구 상태를 바꿔야 한다면, 유일하게 바꿀 수 있는 2번 스위치를 눌러야 한다.2번 스위치를 누른 후에, 만약 2번 전구 상태를 바꿔야 한다면, 유일하게 바꿀 수 있는 3번 스위치를 눌러야 한다. 이런식으로 진행하면 O(N)만에 답을 구할 수 있다. 여기서 문제는 0번 전구가 없기 때문에 1번 스위치는 예외 처리를 해주어야 한다.1번 스위치를 눌렀을 때와 아닐 때 두 경우에 대해 위의 과정을 진행해주면 마찬가지로 O(N)만에 답을 구할 수 있다. [ 소스코드 ] #include using namespace..
[ 백준 / C++ ] 4900 : 7 더하기 [ 문제 ] 4900번: 7 더하기 [ 접근방법 ] 각 숫자에 해당하는 코드값을 code 배열에 저장하고,역으로 코드값을 보고 숫자를 빠르게 구하기 위해 decode라는 unordered_map을 정의한다. unordered_map을 사용하면 hash를 기반으로 평균 O(1)만에 빠르게 값을 찾을 수 있다.물론 map을 사용하여도 O(logn) 만에 찾을 수 있긴하다. 입력 문자열을 3문자씩 끊어 아래와 같은 과정을 통해 해석한다. 1. substr 함수를 활용하여 3문자씩 끊는다.2. stoi 함수를 활용하여 끊은 문자열을 정수(코드값)로 변환한다.3. decode를 활용하여 코드값에 맞는 숫자를 구한다.4. isFirst 변수를 활용하여 A, B를 구별하여 적용한다. A+B를 구하면 아래와 같은 과정..
[ 백준 / C++ ] 13172 : Σ [ 문제 ] 13172번: Σ [ 접근방법 ] 모듈러 곱셈에 대한 역원을 구하기 위해서는 거듭제곱을 계산해야 한다.소수 모듈러에서 곱셈에 대한 역원은 페르마의 소정리에 의해 계산할 수 있다.소수 x에 대해 (x - 2) 제곱을 수행하면 가능하다. 모듈러로 1,000,000,007 를 사용하기 때문에 곱셈에 대한 역원을 계산하려면 1,000,000,005 제곱을 계산해야 한다.거듭제곱을 고속으로 계산하기 위해 비트를 활용한 분할정복을 사용하였다. 예를 들어 (x ^ 22) 를 계산한다고 하자.22 = 2 + 4 + 16 이므로(x ^ 22) = (x ^ 2) * (x ^ 4) * (x ^ 16) 으로 분할할 수 있다. [ 소스코드 ] #include using namespace std;const int m..
[ 백준 / C++ ] 30805 : 사전 순 최대 공통 부분 수열 [ 문제 ] 30805번: 사전 순 최대 공통 부분 수열 [ 접근방법 ] 수열의 길이와는 상관없이 큰 수가 앞에 존재하는 것이 사전 순으로 나중이기에 중요하다. 큰 수를 찾기 위해 매 루프마다 수열 A, B를 전부 탐색한다. N과 M이 최대 100 이므로 O(N³) 으로 충분하다. [ 소스코드 ] #include using namespace std;int n, m, a[105], b[105], aidx, bidx, c[105], k;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n; for(int i = 0; i > a[i]; cin >> m; for(int i = 0; i > b[i]; while(aidx ma..
[ 백준 / C++ ] 4811 : 알약 [ 문제 ] 4811번: 알약 [ 접근방법 ] DP를 활용하여 모든 경우의 수를 미리 계산한다. dp[ i ][ j ] = 조건을 만족하며 W를 i번, H를 j번 사용한 문자열의 개수. 하나의 문자열을 완성해나가는 모든 과정에서 조건(W ≥ H)을 만족해야 한다.왜냐하면, 약 한 조각을 꺼낸만큼 반 조각을 꺼낼 수 있기 때문에 W ≥ H를 지켜야 한다. 그래서 dp[ i ][ j ]를 계산한다고 하면, 1. i ≥ j 확인2. dp[ i - 1 ][ j ] 뒤에 W 추가3. dp[ i ][ j - 1 ] 뒤에 H 추가 dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ] ( i ≥ j ) [ 소스코드 ] #include using namespace std;lo..
[ 백준 / C++ ] 1865 : 웜홀 [ 문제 ] 1865번: 웜홀 [ 접근방법 ] 문제를 간단히 요약하면 음의 사이클 존재 여부를 판단하면 된다. 음의 사이클 존재 여부는 벨만-포드 알고리즘을 통해 쉽게 판단할 수 있다. 벨만-포드 알고리즘은 그래프에서 최단경로를 찾기 위한 알고리즘으로,각 노드의 임시 최단거리와 인접한 노드를 거쳤을 때의 최단거리를 비교하면서 최단 거리를 갱신한다. 시작 노드 start 로부터 노드 i 로의 최단거리를 dist[ i ]라고 하면 다음과 같다.dist[ i ] = min{ d[ j ] + e.cost | 경로 e = ( j → i ) } 보통 시작점을 s라고 하면 dist[ s ] = 0, 나머지 dist[] = INF 로 초기화하고 루프마다 위 과정을 모든 노드에서 진행한다. 만약 음의 사이클이 존재하지 ..
[ 백준 / C++ ] 2638 : 치즈 [ 문제 ] 2638번: 치즈 [ 접근방법 ] 모눈종이 위에 치즈가 다 사라질 때까지 반복문을 시행한다. 첫째, 모눈종이 가장자리는 무조건 외부 공기이므로 (0, 0) 에서 bfs를 시작하여 외부 공기 위치를 최신화한다.둘째, 외부 공기와 2변 이상 접촉한 치즈를 체크하여 제거한다.셋째, chz 배열에서 외부 공기 관련 정보를 초기화한다. chz[ i ][ j ] = 1 : (i, j) 위치에 치즈.chz[ i ][ j ] = -1 : (i, j) 위치에 외부 공기.chz[ i ][ j ] = 0 : (i, j) 위치에 치즈x. [ 소스코드 ] #include #include using namespace std;int n, m, chz[105][105], sum, ans;int dx[4] = {-1,..
[ 백준 / C++ ] 14938 : 서강그라운드 [ 문제 ] 14938번: 서강그라운드 [ 접근방법 ] 시작 지역을 기준으로 거리가 m 이하인 지역에 존재하는 아이템 수의 합을 구해야 한다. 모든 지역이 시작 지점이 될 수 있기에 플로이드-워셜 알고리즘을 활용하여 모든 최단 거리를 구하였다. n ≤ 100 이므로 플로이드-워셜 알고리즘을 사용하더라도 시간은 충분하다. O(N^3) [ 소스코드 ] #include #include using namespace std;int n, m, r, t[105], d[105][105], INF = 10000;int main(){ ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m >> r; for(int i = 1; i > t[i]; for(i..

티스토리툴바