Algorithm

[백준 16953번] A → B (C++)

https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net A → B 문제는 백트래킹으로 해결할 수 있습니다. 단, A와 B의 값이 최대 10억이고, 연산 적용시 21억을 초과할 수 있기 때문에 int형이 아닌 long long형을 사용해야합니다. 아래는 전체 코드입니다. #include using namespace std; long long a, b, ans = INT_MAX; void back(int th, long long n){ if(n == b){ ans = min(ans, (long long) th - 1); }else if(n < b){ back(th + 1, 2 *..

[백준 16928번] 뱀과 사다리 게임 (C++)

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 뱀과 사다리 게임은 1차원 배열, BFS를 이용하여 최단 거리를 계산하여 해결할 수 있습니다. 1번에서 시작하여 +6번까지를 방문합니다. 단, 사다리 또는 뱀이 있는 칸인 경우, 사다리 또는 뱀을 통해 이동한 칸도 방문해야 합니다. 아래는 전체 코드입니다. #include using namespace std; int board[101]; int vis..

[백준 5525번] IOIOI (C++)

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net P1 = 'IOI' P2 = 'IOIOI' P3 = 'IOIOIOI' P4 = 'IOIOIOIOI' Pn의 길이는 (2n + 1)입니다. I, O의 순서로 이루어진 길이 m의 문자열을 Sm라고 하면, Sm에 포함된 Pn의 개수는 1 + (m - (2n + 1))/2입니다. 예를 들어 길이가 11인 문자열 "IOIOIOIOIOI"에..

[백준 11403번] 경로 찾기 (C++)

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 경로 찾기 문제는 각각의 정점에 대해 BFS를 수행하여 해결할 수 있습니다. 단, 주대각선도 0이 될 수 있음을 주의해야합니다. 아래는 전체 코드입니다. #include using namespace std; int linked[100][100]; int adj[100][100]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 0; i < n; i+..

[백준 11659번] 구간 합 구하기 4

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 구간 합 문제는 누적 합 배열을 이용하여 해결할 수 있습니다. 예를 들어 [5, 4, 3, 2, 1]로 배열이 주어진 경우 (2, 4)는 4까지의 합 - 1까지의 합으로 나타낼 수 있습니다. ⚠️ 단, (1, 1)도 처리할 수 있어야 하기 때문에 첫 요소에 0을 넣어주어야 합니다. 아래는 전체 코드입니다. #include using namespace std; int main..

[백준 17219번] 비밀번호 찾기 (C++)

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 비밀번호 찾기 문제는 이분탐색을 이용하여 해결할 수 있습니다. N이 최대 100,000이 주어지기 때문에, 일반적인 탐색으로는 시간초과가 발생할 수 있습니다. 사이트의 주소와 비밀번호를 입력받고, 사이트의 주소를 기준으로 정렬해준다음, 이분탐색을 수행하면 비밀번호를 찾는 시간을 단축할 수 있습니다. 아래는 전체 코드입니다. #include using namespace..

[백준 17626번] Four Squares (C++)

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net Four Squares는 백트래킹과 메모이제이션을 이용하여 해결할 수 있습니다. HTML 삽입 미리보기할 수 없는 소스 따라서 해당 범위에서 숫자를 선택하고, 재귀 함수의 파라미터로 선택한 숫자의 제곱을 뺀 값을 전달해주면 됩니다. 또한 이미 계산한 값을 배열에 저장함으로써 시간을 단축시킬 수 있습니다. 아래는 전체 코드입니다. #include using nam..

[백준 18870번] 좌표 압축 (C++)

https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 좌표 압축 문제는 압축 전 좌표를 기준으로 정렬한 후, 각각의 좌표를 압축하고, 좌표를 입력 받은 순서대로 다시 정렬하면 해결할 수 있습니다. ⚠️ 단, 서로 다른 좌표의 개수를 구해야하므로, 단순히 정렬된 좌표의 인덱스만으로 압축된 좌표를 구할 수 없습니다. 좌표 정렬 후, 가장 작은 좌표부터 시작하여, 현재 좌표가 이전 좌표와 같을 경우 좌표를..