104%

기본 BFS문제에서 약간 생각을 좀 더 해야되서 난이도를 중으로 채택했다. 해설 4 6110110110110111111 111101이런 미로가 있다고 치자. 기본 bfs의 동작 방식은 큐에 다음 방문해야할 곳을 저장해 놓고 큐에서 하나하나 꺼내면서 그 위치에 방문해가면서 방문했을때 문제 조건에 맞는 어떤 처리를 해준다. 이 행동을 큐가 완전히 빌때까지 무한 반복 하는것이다. 하지만 여기서는 bfs를 해 나가면서 현재 내가 방문한 곳이 시작점으로부터 얼마나 떨어져있는지를 기록해 놓아야 한다. 그러기 위해서 나는 2차원 memo라는 배열을 하나 더 선언했고, 이곳에 현재 방문한 곳부터 시작점까지의 거리를 기록해나갔다. while(xdeq.size() != 0) { int x = xdeq.front(); in..

해설 처음부터 끝까지 검색을 시작한다. 검색을 해 나가면서 현재 검색하고 있는 문자가 j,=,-이면 그전 문자가 어떤거였는지를 체크한다.또한 검색을 해 나가면서 단어의 개수를 세기 위해서 count를 하나씩 늘려준다 ljes=njak라는 문자열이 있을때 l을 검색할때 count ++ 되고그다음 j를 검색하게 되면 마찬가지로 count가 1 증가되서 count는 2인 상태에서 그 앞의 문자를 보니 l이다 따라서 lj는 크로아티아 문자이므로 다시 1을 빼줘서 count가 1이되게끔 만든다. 그다음 e를만나면 count=3s를 만나서 count =4=을 만나서 count=5인 상태에서 =을 만났으므로 앞의 문자까지 포함해서 보면 s=이다. 따라서 count를 1빼줘서 4가 되게끔하고 마찬가지로 검색을 쭉 하다..

어떻게 풀어야 될지 감이 잘 안와서 구글링을 해서 풀었다.. 1원짜리 5원짜리 12원짜리 동전이 있고 15원을 만드려고 할때 최소의 동전개수로 만드는 문제이다.이문제는 동전교환 문제라고 알려진 유명한 문제이다 맨 위의 굵은 숫자들은 몇원이냐를 말하는것이다. 1원,2원,3원...을 만들기 위해 필요한 최소의 동전의 개수가 저장된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 2 3 4 5 6 7 8 9 10 11 12 13 14 15 =>동전이 1원짜리만 있다고 가정 1 2 3 4 5 2 3 4 5 6 3 => 1원짜리와 5원짜리가 있다고 가정 1 2 3 3 => 1원,5원,12원짜리가 있다고 가정했을때 필요한 최소 동전의 개수해서 답은 총 3개의 동전이 필요하다위의 숫자들은 dp[..

간단한 다이나믹 프로그래밍 문제이다. 예제에 나온걸 예로 들면 6 10 13 9 까지만 있다고 쳤을때 x x o x o o 연속해서 세잔을 마실 수가 없으므로 세가지 경우가 나타날 수 있다. 1.마지막 잔을 마시지 않고 그전 잔만 있다고 생각했을때 최대 마실수 있는양2.마지막 잔을 + 그전전 잔까지만 있다고 생각했을때 최대 마실수 있는양3. 마지막 잔과 그 전 잔 + 그전전 까지의 포도주의 최대 시식량 이 세가지 경우중에 최대가 되는것을 택하면 6 10 13 9 의 양을 가진 포도주잔들이 있을때 마실수 있는 포도주의 최대 양을 구할 수 있게 된다. 12345678910111213141516171819202122232425262728#include#includeusing namespace std;int i..

dfs로 푼 문제 1,1 부터 n,n까지 검색하면서 1인곳부터 dfs를 시작한다 dfs를 시작후 깊이 들어가면서 1이라고 표시된곳을 0으로 고치고 1을 더해줌으로써 한 동의 몇개의 세대가 있는지를 체크한다. 알고리즘 자체는 오류가 없었으나 정적배열의 크기를 25*25로 잡고 int형으로 했더니 오류가 났던 문제 bool 26*26으로 수정했더니 잘 동작했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include#include#include using namespace std;bool W[26][26];bool visited[26][26];int diffx[4]..

수가 10의 1만승까지 가능하므로 현존하는 정수형 자료형으로는 절대 이 숫자들을 표현할 수 없다.그렇기 때문에 문자열로 처리를 해야한다. 해결방법stirng 2개에 각각 숫자로된 문자열을 입력받고나서 맨마지막수부터 더해가면서 올림수(carry)와 결과값(remain)을 구분하면서 계속 더해간다. 두 숫자의 자리수를 맞춰줘야 하므로 자리수가 더 적은쪽의 빈공간을 0으로 채웠다예를들어 9999와 1을 더하게되면9999와 0001을 더하게끔 만들었다 . 이렇게 표현해야 반복문을 좀더 쉽게 할 수 있었다. 12345678910111213141516171819202122232425262728293031323334353637using namespace std;#include#includeint main(){ str..

이 문제는 LIS(Longest increasing subsequence) 기본 문제이다 문제를 푸는 방법은 현재 인덱스를 검사할때 그 전에 인덱스를 하나하나 살펴보면서 현재 인덱스에 있는 숫자 보다 작은 것의 인덱스 중에 가장 큰 dp값(가장 긴 부분증가수열)을 택하고 그것에 1을 더하면 현재 인덱스에서 가장 긴 부분 증가 수열을 구하게 된다. 예를 하나 들면 10 20 10 30 20 50 이 있을때 30에서 가장 긴 부분 증가수열을 구하려면(dp[3]에 들어가는 값) 30과 10 20 10 을 차례대로 비교를 해 나간다 그중에 10,20,10모두 30보다 작으므로 후보가 될 수 있다. 이 세 숫자 중에서 dp[0],dp[1],dp[2]에 저장된 값중에 가장 큰 것에 1을 더해주게되면 30에서의 가장..

간단한 문제일 줄 알았으나, 은근 어려웠던 문제 우선 딱 봤을때 떠오르는 방법은 틀린 방법일 확률이 높은 문제이다. 왜냐하면 제한시간이 1초인데 문자열의 길이는 백만 까지 가능하다. 보통 비교연산을 1억번 정도 하는데 1초정도가 걸린다고 한다. 그런데 만약 빅오가 엔제곱인 알고리즘으로 이문제를 푼다면 백만곱하기 백만 이기때문에 1초로는 어림도 없다. 그래서 처음에 시간초과가 떴었다. 이 문제는 빅오가 엔인 알고리즘으로 풀어야만 문제를 풀 수 있다. 즉 문자열을 검사해 가면서 동시에 문자열을 바꿔야만 하기때문에 조금 까다로운 문제이다. 풀이방법-> 문자열을 검색해가면서 C4중 4를 만날때까지 검색을 한다.현재 검색한 문자가 4가 아니라면 스택(배열로 표현됨)에 그 숫자를 넣는다. 4를 만났다면 거꾸로 내려..