https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net - 다이나믹 알고리즘(DP). 알고리즘 v[a][b] = a에서 b까지의 문자열의 팰린드롬 여부(a부터 b까지 문자열이 팰린드롬이라면 true, 아니라면 false) 팰린드롬이 될 조건 - a == b 라면 항상 팰린드롬. - arr[a] == arr[b]인 경우에 팰린드롬. - v[a+1][b-1] = true && arr[a]==arr[b]인 경우에 팰린드롬. 예외 조건 b-a == 1 , arr[b]==arr[a]라면 팰린드롬이다..

https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼�� www.acmicpc.net - 브루트 포스 문제. 알고리즘 1. 목표로 하는 채널을 기준으로 두고 1씩 내려가거나 1씩 올린다. 2. 1씩 올리거나 내린 수들이 망가진 키를 포함하지 않는지 검사한다. 3. 망가진 키를 포함한다면 다시 1번으로, 망가진 키를 포함하지않는다면, 100에서 무식하게 올리는 거랑 비교해서 작은 횟수를 출력한다. 예외 조건 1. 100에서 무식하게 올리거나 내린것이 더 적은 이동..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net - 다이내믹 프로그래밍 문제 알고리즘 현재 칸이 가장 왼쪽 위치인 경우 -> dp [1][0]=max(dp [0][0],dp[0][1])+ map[0] 현재 칸이 중간 위치인 경우 -> dp[1][1] = max(dp[0][0],dp[0][1],dp[0][2])+map[1] 현재 칸이 가장 오른쪽 위치 -> dp[1][2] = max(dp[0][1],dp[0][2])+map[2] 시간 복잡도 총 n번(n>num..

https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net - 백트래킹을 이용한 dp문제. 알고리즘 1. dp배열에 마지막 칸을 1로, 나머지는 0으로 초기화한다. 2. 백트래킹을 활용한 dfs를 사용..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 100)이 주어지고 둘째 줄에는 버스의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 버스의 정보는 버스의 시작 도시 a, 도착 도시 b, 한 번 타는데 필요한 비용 c로 이루어져 있다. 시작 도시와 도착 도시가 같은 경우는 없다. 비용은 100,000보다 작거나 같은 자연수이다. 시작 www.acmicpc.net - 플로이드 와샬 문제 - 알고리즘 - 1. 플로이드 와샬 알고리즘을 통해 모든 도시로 가는데 필요한 비용의 최솟값을 구한다. (플로..

https://www.acmicpc.net/problem/13458 13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net - 그냥 구현하는 문제. 문제 조건대로 풀면 된다. -시간 복잡도- O(n) - 예외 조건 - 1. 사람이 기준치에 미치지 못하여도 감독관이 들어가야 한다. -소스 코드- 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 #include using namespace std;..

- dfs와 이분 탐색이 혼합된 문제. 반복문과 vector 배열 같은 다양한 문법을 연습할 수 있어서 좋은 문제였다고 생각한다. - 알고리즘 - 1. 를 쌍으로 가지는 벡터 배열을 입력받아서 배열 인덱스를 from, 첫 번째 int를 to, 두 번째 int를 cost로 놓는다. 2. dfs를 사용해서 갈 수 있는지 없는지를 판단한다. 3. 갈 수 있다면, left=mid+1로, 갈수 없다면, right=mid-1으로 놓고 이진 탐색을 돌린다. - 예외 조건 - 1. 그래프가 쌍방향임을 잊지말자. 처음에 vector에 넣어줄 때 양방향으로 넣어주어야 한다. -소스 코드- 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 ..

vector를 사용하면서 for(auto &p: arr) 이런 식의 반복문 문법을 자주 쓰는 편인데 dev c++로 알고리즘 문제를 풀다 보니 지원하지 않는 경우가 발생했다. range-based 'for' loops are not allowed in c++98 mode 위와 같은 에러를 띄우고 프로그램을 종료되었다. 문제 해결을 위해 구글링을 해보니, stackoverflow에 해결 방법이 있어서 공유하고자 한다. 위와 같은 에러는 dev-c++의 문법이 std-98을 기반으로 하고있기 때문에 뜬다고 생각된다. 그때는 반복문에 대한 문법이 완벽하지 않았나 보다. Tools -> Compiler Options -> "Compiler" tab로 들어간다. 여기서 Add the following comman..