jmmm_25

이 문제는 앞 뒤에 임의의 알파벳 문자를 추가하여 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의 범위 조건을 잘 맞춰주면 ..

문제에서 주어진 조건처럼 미로 중에 '0'인 곳은 지나갈 수 없고, '1'인 곳만 지나갈 수 있다.그러므로 (1,1) 부터 (N,M) 인 (4,6)까지 BFS 탐색을 하면 된다. BFS 개념만 알고 있다면 단순한 문제이다.소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#includeusing namespace std; struct Info{ int x; int y; int cnt;}; int N, M;int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};char map[10..

7568번 덩치 문제는 조건만 잘 이해하면 되는 문제이다.A (x, y) 와 B (p,q)의 덩치를 비교하는데 있어, 조건식은 x > p && y > q 이면 A가 B보다 덩치가 크다고 할 수 있다. 우선 순서대로 (몸무게, 키)를 번호로 지정할 수 있게 벡터에 저장시킨다. 여기서 구조체의 개념이 들어간다.그 후에, i번째 (몸무게, 키)를 나머지 i번 째를 제외한 나머지(몸무게, 키) 와 비교를 한다.만약 비교하였을 때, i 번째 (몸무게, 키)의 덩치가 작다면 미리 만들어 놓은 ranked[i]의 값을 +1 해준다. ranked[i]++ 는 나보다 덩치가 큰 사람이 늘어난다는 것이다. 그 후에, 문제의 조건에서 "만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다." ..

6603번 로또 문제는 부분 집합을 구할 수만 있다면 쉽게 해결할 수 있다.더 간단한 방법이 있겠지만, 문제를 풀 때 vector에 부분 집합을 넣은 후, 사이즈가 6이 되는 것만 출력하게끔 했다.다음에 다른 사람들은 어떻게 문제를 풀었는지, 조금 더 나은 방법이 있는지 확인 해야겠다.문제의 출력과 순서가 동일하게 나와야 맞았습니다가 뜨는 것 같다.같이 푼 친구는 flag 없이 비트 연산으로 부분집합을 구해서 풀었는데, 순서만 나와 다르게 나왔다.순서 때문에 틀린 것인지, 아니면 잘못푼 것인진 잘 모르겠다. 소스는 아래와 같다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#i..