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

- 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..

그리디 알고리즘 3의 배수일 조건 : 각 자릿수의 합이 3의 배수여야 한다. 10의 배수일 조건 : 1의 자릿수가 0이어야 한다. 30의 배수일 조건 : 3의 배수이면서 10의 배수이어야 한다. -문제 풀이 1. 예외 조건을 처리한다. 2. 예외 조건에 걸리지 않는다면 맨 뒷자리에 0을 놓고 나머지를 정렬한다. -예외 조건 1. 주어진 숫자에 0이 포함되지 않을때. 2. 각자리수 합이 3의 배수가 아닐 때. -소스 코드 #include #include using namespace std; int main() { int hap=0; //3의 배수인지 아닌지 판단하기 위한 변수 int arr[1000001]; string a; cin>>a; for(int i=0;i

그리디 알고리즘 -결정해야 할때 그 순간 가장 좋다고 생각하는 것을 선택하면서 답을 찾아가는 알고리즘. -거스름돈 문제가 대표적인 문제지만, 모든 문제가 그런것은 아니다. -그리디 알고리즘은 증명이 어렵다 관련문제 : 11047번(동전 0) a[i]가 a[i-1]의 배수이므로 그리디 알고리즘을 사용하여도 문제가 없다. 다만 배수라는 조건이 없다면 다이나믹 프로그래밍을 통해서 해결하는 것이 옳다. cost[i]= cost[i-coint[k]]+1 1931번 (회의실 배정) 정렬하는 문제. 가장 빨리 끝나고 가장 빨리 시작하는 순서대로 정렬하면 편하다 11399번 (atm) 증명으로 가능 pf ) i번째 사람이 일을 보는데 시간을 p(i)라고 하면 i번째 사람이 기다려야 하는 시간은 시그마(1 각 자리수를 ..

#include using namespace std; int main() { int width,height; cin>>height>>width; if(height ==1){ cout