jmmm_25

너무나도 단순하게 짜면은 시간 초과가 뜨기 때문에 틀릴 수 있는 문제이다. jump 라는 변수를 이용하여 탐색의 횟수를 줄여나가 시간 초과 문제를 해결할 수 있었다. 소스는 아래와 같다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #define MAX_INF 1000000using namespace std; int n;int number[20];int main(int argc, char const *argv[]) { cin >> n; long long num = 1; if (n == 0) { cout

이 문제는 DFS 알고리즘으로 해결하였다. 탐색 가능하면 계속 탐색하고, 그렇지 않으면 탐색했던 곳의 알파벳의 Check를 false로 바꿔주어야 한다. 처음에 이걸 생각 못해서 계속 틀렸었다. 그리고 바보같이 방문을 했는지 체크하는 배열을 만들어서 한 번 방문했던 곳을 방문하지 못하게 했다. 그래서 계속 틀렸었다. 질문 검색을 해보니, 몇개의 예제가 있었는데 그 예제를 통해서 결국 답을 맞출 수 있었다. DFS 알고리즘에 약간 응용인 문제인 것 같다. 위에서 말했던 것처럼 이상한 짓을 해가지고 시간이 좀 걸렸다. 나중에 다시 한번 보면 좋을 문제. 알파벳을 체크하는 방식이 있을텐데, 나는 그냥 벡터를 만들어서 for문을 돌려서 소스가 지저분하다. 다른 사람들은 어떻게 이 부분을 체크했는지 알아봐야할 것..

이번 문제는 BFS 문제이다. 문제는 촌수 계산이지만, 노드의 Level을 출력하라는 문제와 동일하다.만약 노드끼리 연결되어 있지 않다면 -1을 출력하면 된다.노드간의 연결이므로 인접 리스트로 문제를 해결하였다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include using namespace std; vector adj(101);bool isVisited[101];int n, m; int bfs(int x, int y) { queue q; isVisited[x] = true; q.push(x); int l..

이 문제는 앞 뒤에 임의의 알파벳 문자를 추가하여 A와 B의 차이를 최소화하는 문제이다.알파벳 추가는 신경 쓰지 않아도 된다. a ~ z의 임의의 문자를 추가하면 되기 때문이다. 여기서 중요한 것은, 문자가 앞 또는 뒤에 추가되었다고 가정하고 기존의 문자열끼리의 차이를 최소화 되는 값을 찾으면 되는 것이다. i 가 0일 때에는 A[ j ] != B[ j + i ] 이므로, j 값과 j+i의 값은 같다.i 가 1일 때에는 j 와 j+i 의 값이 같지 않다. 이는 A 문자열 맨 앞에 임의의 알파벳 문자가 추가된 것임을 알 수 있다. A[0] 과 B[1] 비교A[1] 과 B[2] 비교...A[5] 과 B[6]의 비교 이렇게 되기 때문이다. 따라서 ? a d a a b ca a b a b b c (여기서 ?는 ..

체스에서 나이트는 위의 문제의 그림처럼 움직일 수 있다.이 나이트의 움직임을 BFS로 구현하면 쉽게 풀리는 문제이다. 앞서 풀었던 BFS 문제 중에서 상하좌우로 움직이는 문제들이 많았을 것이다.그 상하좌우로 움직이는 것들을 응용하면 되겠다. 나이트는 총 8개의 방법으로 움직일 수 있다.Line 17 ~ 18에 그 답이 있다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include using namespace std; class Info{public: int x, y, cnt; ..

isChecked 배열의 true / false를 이용하여 가능한 순열을 출력하면 되는 문제이다.순열 문제는 익숙치 않으니, 다시 한번 더 풀어보도록 해야겠다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435#include using namespace std; int number[10];bool isChecked[10]; void dfs(int num, int pos, int n) { number[pos] = num; if (pos == n) { for (int i = 1; i

1051번 숫자 정사각형 문제의 유형은 브루트 포스이다. 이 문제는 이중 포문을 잘 이용하면 쉽게 풀린다.N, M이 50보다 작은 수라고 했으니, len을 50까지 늘려가면서 정사각형이 만들어질 수 있는지를 확인하면 된다. 이중 포문의 해당 좌표를 이용하여 좌표에 + len을 해주면서 정사각형인지 아닌지를 확인하면 된다.정사각형은 꼭지점만 같은 숫자이면 된다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include #define MAX_RANGE 50using namespace std; int n, m;int map[5..

개인적으로 굉장히 어려웠던 문제였다. 계속 틀리고, 내가 짠 소스가 틀린 소스가 되버리고 조건을 너무 여러개를 생각해서 이것 저것 더 구현하려고 하니 소스만 복잡해지고, 구현도 어려웠다. 결국에는 질문과 구글링의 힘을 빌렸고 문제를 해결할 수 있었다. 다시 한번 꼭 풀어봐야할 문제이다. 0 return 11번 버튼 고장, 2번 버튼 정상 -> return 1두 버튼 다 고장 -> return -1 이런 식으로, 버튼을 누르는 횟수를 리턴한다. 그 후, sol() 함수에서 현재 버튼에서 +, -로 이동하는 횟수인 abs(n - i) 와 btn_cnt_chk에서 반환 된 값을 둘이 더하면 된다. 그 후, 처음에 계산한 값과 sol() 함수의 return 값 중에 최솟값을 찾아 출력시키면 되는 문제이다. 12..

7576번 토마토 문제는 BFS로 해결하였다. 구현이 어려운 문제는 아니지만, 반례가 많아서 정답을 맞추기가 어려웠다. 정답률이 24%인 이유를 알 것 같다. 나도 엄청 틀렸기 때문이다.우선, 다 구현해놓고 틀렸던 점은 조건이 부족했기 때문이다. 처음에, 모든 토마토가 다 익어있으면 0을 출력해야하는 부분에서 한 가지 조건이 있다.토마토 저장소가 모두 -1 즉, 비어있을 경우에도 모두 다 익어있는 상태로 생각하여 0을 출력해야 한다.이 부분을 알지 못해서 많이 틀렸었다. 그리고, 이중 for문을 돌려 하나 하나 bfs를 돌렸었는데, 그렇게 하는 것이 아니라익은 토마토가 있는 위치를 모두 큐에 push 하여 BFS 탐색을 하는 것이었다. 이렇게 고치니 문제를 해결할 수 있었다. 이 문제의 질문 검색을 하면..

1697번 숨바꼭질 문제는 BFS 알고리즘으로 분류되어 있다.이 문제는 런타임 에러가 계속 나서 까다로운 문제였다.아마도 pos * 2를 하는데 있어 isVisited의 배열의 크기를 초과하기 때문인 것 같다. 5 -> 17 로 가는 방법은 여러가지 방법이 있다.그래서 나는 그 방법을 하나씩 다 해봤다. 5 에서 출발하게 된다면 걷기 2가지 / 순간이동 1가지, 총 3방식으로 갈 수 있다. 5 + 1 = 65 - 1 = 45 * 2 = 10 이렇게 움직일 수가 있다는 것이다. 여기서 6, 4, 10을 큐에 저장시켜 두고, 같은 방식을 계속 이어나가면 된다.주의할 점은 런타임 에러가 뜬다는 것이다. 해결을 위해서는 if문 조건에서 pos - 1 , pos + 1, pos * 2의 범위 조건을 잘 맞춰주면 ..