poksul_log

관련 알고리즘 : 배열 문제 링크 : https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 문제 풀이 시간복잡도를 계산하는 능력이 타 친구들에 비해 현저하게(...) 떨어지는 것 같아 관련 문제를 들고왔다. 처음에는 내가 평소에 짜던 것처럼 이중for문을 돌며 모든 경우를 검사하게 했지만 역시나! 시간 초과 오류가 뜨게 되었다. 어찌보면 당연하다. 수의 범위가 (1 ≤ n ≤ 100000, 1 ..

관련 알고리즘 : DP 문제 링크 : https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 n자리 숫자 중 계단수(각 자릿수마다 있는 수의 차이가 1인 수)의 개수를 구하는 문제이다. '일의 자리 숫자가 무엇인가' 와 'n(자리수)'를 기준으로 dp 식을 세우면 문제를 해결할 수 있다. n=2인 경우를 예를 들어 생각해보자. 일의 자리 십의 자리 개수 0 1 1 1 2 1 2 1, 3 2 3 2, 4 2 4 3, 5 2 5 4, 6 2 6 5, 7 2 7 6, 8 2 8 7, 9 2 9 8 1 십의 자리 숫자가 일의 자리 숫자가 무엇이느냐에 따라 영향을..

📍 다이나믹 프로그래밍이란? 여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 컴퓨터는 연산 속도와 메모리 공간에 한계가 있기 때문에, 이를 최대한으로 활용해야 한다. 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수가 있는데, 이를 이용한 방법이 바로 DP이다. 📍 다이나믹 프로그래밍이 쓰이기 위한 조건 큰 문제가 작은 문제로 나눠질 수 있어야 한다. 작은 문제에서 구한 정답은 이를 포함하는 큰 문제에서도 동일하다. 다이나믹 프로그래밍은 1번 조건에 의해 분할 정복과도 비슷한 성질을 지니고 있지만, 분할 정복과 달리 문제들이 서로에게 영향을 끼친다. 📍 피보나치 수열 문제를 통해 알아보는 DP 다이나믹 프로그래밍의 대표적 예로 피보나치 수열 문제..

📍백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘 즉, 해를 찾을 때 중간에 해가 아니어서 막힐 경우, 이전 단계로 되돌아가 해를 다시 찾는 기법 📍백트래킹의 쓰임 최적화 및 조합, 결정 문제를 풀 때 쓰인다. 주로 DFS(깊이 우선 탐색)와 묶여서 잘 쓰이는데, DFS는 가능한 모든 경로를 탐색한다. 따라서, n이 큰 경우 경우의 수를 줄여야 할 필요성이 있다. → 이 때 백트래킹을 사용하여 불필요하거나 불가능한 경로를 사전에 차단하는 것을 통해 경우의 수를 줄일 수 있다. 즉, 가지치기를 할 수 있다는 것 ! ▶ DFS와 쓰일 때 흐름은 다음과 같다. DFS로 모든 경우의 수를 탐색할 때, 조건문을 걸어 불가능한 경우를 정의하고, 해당 상황일 때 탐색을 중지 이후 ..

관련 알고리즘 : BFS 문제 링크 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 지도를 모두 돌며 연결되어 있는 단지의 개수와 단지 당 집 개수를 찾아야 하므로 bfs(너비우선탐색)을 이용한다. 플로우는 다음과 같다. 더보기 string을 통해 입력 처리 map 완전탐색을 통해 아직 방문하지 않고 & 좌표값이 1인 경우(집이 있는 경우) 부터 bfs 시작 상하좌우 탐색 이후, 지도 밖의 범위일 경우 반복문 탈출 이미 방문한 곳일..

관련 알고리즘 : BFS 문제 링크 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 문제 풀이 며칠이 지나면 토마토들이 익는 지 "최소 일수"를 구해야 하므로 bfs를 사용한다. 토마토들의 상태(-1, 0, 1)을 배열에 저장 익은 토마토들을 큐에 넣기 익은 토마토들 상하좌우 토마토들 방문 여부 확인 안 익은 토마토가 존재 시, day++ 하여 날짜를 증가시키고 익었다 처리 해당 토마토를 큐에 넣기 위의 과정 반복 C++ 코..

관련 알고리즘 : BFS 문제 링크 : https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 문제 풀이 한 박스 : 맥주 20개 최대 ( 맥주마시기 ) => 50미터 O 빈 병 버리고 새 맥주병( 맥주병 최대 20개 ) 테스트 케이스 개수 t ( t 두 좌표 사이의 거리가 1000m 이하면 이동 가능 1000m 거리 내 편의점 있음 => queue에 추가 queue가 empty => sad 출력 C++ 코드 #include #include us..

가장 작은 것을 선택하여 제일 앞으로 보내는 정렬 방법 ▶ 흐름은 다음과 같다. 1. 맨 앞에서부터 차례로 돌며 가장 작은 수 찾기 2. 가장 작은 수 맨 앞에 있는 수 3. 2번째 수부터 차례로 돌며 2번째로 작은 수 찾기 4. 2번째 수 2번째로 작은 수 5. 위의 과정을 n번째까지 반복 ▶ C++ 코드 #include int main(){ int i, j, min, index, temp; int array[10] = { 1, 10, 8, 7, 5, 4, 6, 3, 2, 9}; for(i=0; i 2번째까지 제외한 8개 살펴보기 ... >> 10+9+...+1 = (10*11)/2 - n(n+1)/2 >> O(n^2)

관련 알고리즘 : 구현, 그래프 탐색 문제 링크 : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 풀이 문제의 조건을 보면, 2차원 배열의 행(N, 3 n >> m; for (int i = 0; i > map[i][j]; } } } void BFS(int a, int b) { queue Q; Q.push(make_pair(a, b)); visit[a..

관련 알고리즘 : 그래프 탐색, 백트래킹 문제 링크 : https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 문제 풀이 문제의 조건을 보면, NxM 크기의 보드 동전 2개 ( 서로 다른 빈 칸에 존재) 각 보드의 칸에 동전 / 벽 / 혹은 빈 칸 존재 상, 하, 좌, 우 이동 가능한 4개의 버튼 버튼으로 동전 2개 동시조작 ( 동전은 동시에 같이 이동 ) 이동하려는 칸이 벽일 시 => 동전 이동 X 이동하려는 칸이 없을 시 => 동전 떨어짐 두 동..