더블릿_더큰
쫌 고민을 많이 했다.
우선 문제를 간단히 정리하자면
1<= x <= 999999 의 숫자가 입력되면
이 수에 포함되어 있는 숫자들을 이용하여 만든 수들 중에 입력된 수보다 큰 최소수를 구하는 문제이다.
다소 문제 설명이 어렵지만,
156을 보자면 156이 포함되어 있는, 156의 자리수로 만들 수 있는 숫자는
156, 165, 516, 561, 615, 651 등등이 있다.
이 중 입력된 156보다 큰 최소 수는 165이다.
문제 풀이)
처음에는 어떻게 풀어야 되나 굉장히 고민을 많이 했다. 156의 자리수를 가지고 만들 수 있는 수들을 다 구한다음에 정렬하고,
입력받은 수 보다 큰 숫자를 출력해야 되나? 가 첫 번째 떠오른 방법이었다. 일단 1~999999이기 때문에 숫자를 만드는 방법에 대해서 어려운 점이 있었다.
한번 더 생각해보니까
1~999999까지 for문을 돌리면서 조건을 만족시키는 숫자를 캐치해내면 되겠다고 생각했다.
예를 들어 156이 입력되면
1) 156~999999까지 반복문을 수행한다.
2) 각 숫자들마다 자리 수에 있는 숫자들을 판별하여 1,5,6에 부합한지를 체크한다.
3) 만약 조건에 부합하면 바로 출력하고 프로그램을 끝낸다.
4) 조건에 부합하지 않으면 0을 출력한다.
더블릿_빙고
1)나의 빙고판을 입력받는다.
2)사회자가 부르는 번호를 입력받는다.
3) 사회자가 입력되는 순서대로 내 빙고를 체크해준다.
** 빙고를 판별하는 것은
// 대각선
[x][y] 좌표가 x == y일때와, x + y = 6일 때
// 가로
[x][y] 좌표가 x는 고정시키고 y를 1~5까지 순회
// 세로
[x][y]좌표가 y는 고정시키고 x를 1~5까지 순회
더블릿_wrap around
정말 느낀점이 많은 문제이다.
10*10 배열이 주어지고 상, 하, 좌, 우, 대각선의 5개의 합을 도출해내는 문제였다.
정말 쉽다고 생각했다.
현재 인덱스에서 +0, +1, +2, +3, +4 해주면서 그 값을 %10해주면 10을 넘어가도 인덱스가 순환할 수 있게 되어
원하는 답을 구할 수 있게 된다.
그런데 내가 음수가 되는 부분에 대해서 예외처리를 안해주었다. ㅜㅜ 근데 황당한 것은 비주얼 스튜디오에서는 쓰레기값에 대한 처리가 리눅스와 달라서 답이 제대로 나오는데 제출되는 컴파일러에서는 그렇지 않아서 문제점을 찾는데 애를 먹었다.
다시 한 번 말하지만 로직을 짜기 전에 한 번 손으로 그려보고 맞춰보는 형태가 정말 중요하다는 것을 알았다.
결국 인덱스를 좌로 가거나 상으로 가는 연산에서는 행에서 -1, -2, -3, -4해줄 때 원래 인덱스에서 10을 더해준다음에 연산을 수행해주면 아무 문제가 없다.
더블릿_폭탄게임
행, 열 정보가 주어진다. A는 폭탄을 어느 한점에 숨겨둔다.
B는 폭탄을 떨어뜨려 보면서 A가 놓은 폭탄의 위치를 알아맞추는 문제였다.
처음은 굉장히 간단한 문제라고 생각하면서 풀어보다가 낭패를 맛 보았따.
반드시 예제의 테스트케이스를 손으로 돌려보면서 내 로직이 정확한 답을 내놓는지를 검사해봐야
시간 낭비를 줄일 수 있다고 깨달았다.
처음에는 그냥 간단히 폭탄이 떨어지는 위치를 bool 배열을 이용해서 true false를 갱신해준 다음에 true인 배열의 개수를 통해
답이 도출되는 줄 알았따.
그런데 폭탄을 떨어뜨릴 때마다 가장 최신의 정보를 가지고 점점 폭탄의 범위를 좁혀나가야 하는 문제였다.
문제를 풀면서 몇 가지 이슈에 대해서 설명해 보자면
1) 폭탄의 범위를 설정하는 부분이다.
어느 한 점 x, y가 주어지고 폭탄의 범위는 p(홀수)가 주어진다.
손으로 대충 그려보니 폭탄의 범위를 설정해주기 위해서는
x - (p - 1) / 2 ~ x + (p - 1)/2 로 설정
y - (p - 1)/ 2 ~ y + (p - 1)/2로 설정
해주면 정확한 정사각형의 범위의 폭탄을 설정해줄 수 있다.
그리고 폭탄의 위치는 단 한개이므로 폭탄이 떨어질 때마다 그 값들을 점차 증가시켜주면서
마지막에 가장 많이 겹치는 부분을 답으로 도출해주었더니 답을 구할 수 있었다.
더블릿_계단오르기
문제정리)
계단은 한 칸 오를 수 있고, 두 칸을 오를 수 있다.
입력받은 계단까지 오르는 경우의 수를 출력하라
라는 것이 문제였다.
풀이정리)
재귀함수를 작성하는 것에 대한 좋은 연습문제였던 거 같다.
항상 재귀함수에 대해서 정확히 어떤 메커니즘을 가지는 것인가에 대해서 많은 생각을 해보게 된다.
좀 더 연습을 해야 겠지만 많은 문제를 풀어보면서 재귀에 대해서 알 필요가 있을 것 같다.
여태껏 느낀 것은 좋은 점화식을 통해서 답을 구해 낼 수 있다는 것이다.
입력의 4번째 계단까지 오르는 경우의 수를 간단히 생각해보면
4번째 계단까지 오르는 경우의 수는 3칸까지 올라와서 1칸을 오르는 경우와 2칸까지 올라와서 2칸을 오르는 경우의 합이다.
대충 손으로 그려봐도 정확한 점화식을 구하기가 어려웠는데 이 부분에 대해서는 좀 더 연습을 통해 명확한 매커니즘을
구축해야 될 필요가 있을 것 같다.
너무 전형적인 문제여서 생각도 하기 전에 답이 떠오르는 문제였다.
더블릿_비트패턴
재귀함수를 사용하는 문제에서는 언제나 어려움을 겪는다. 재귀적인 탐색방법에 대한 기본적인 개념이 부족한 듯하다.
재귀함수의 탈출 조건은 1을 k번만큼 썼을 때 출력하고 끝내게 했다.
아니면 현재의 인덱스가 n보다 크게 되면 탈출하게 했다.
그 외의 상황에서는 1또는0을 바꾸어가면서 재귀적인 수행을 하게끔 코딩해줬다.
풀고 나서도 어떻게 답을 도출해냈는지에 대해서 명확하게 설명을 하기가 애매한 상황이다.
이 부분은 반드시 다시 짚고 넘어가야 할 부분 같다. 패턴을 만들어내는 것이 내가 반드시 해야될 일인 듯하다.
다시 풀어볼 때 참고하기 위한 소스코드
#include <iostream> using namespace std; int arr[31]; int n, k; void bitpattern(int current_i, int use_one){ if (use_one == k){ for (int i = 1; i <= n; i++){ cout << arr[i]; } cout << endl; return; } if (current_i == n + 1) return; arr[current_i] = 1; bitpattern(current_i + 1, use_one + 1); arr[current_i] = 0; bitpattern(current_i + 1, use_one); } int main(){ cin >> n >> k; bitpattern(1, 0); return 0; } | cs |
더블릿_십자카드
엄청난 오류에 빠졌다. 요즘 왜 이렇게 문제에 대해서 잘 못 파악하고 시간을 낭비한 적이 많은지 모르겠다.
일단 무조건 문제에 주어지는 것을 고대로 코드로 옮기는 방법을 먼저 시도해야 된다고 생각한다. 그 동안은 자의적인 해석으로 더 좋은 방법으로 간단하게 풀고자 노력했었다. 하지만 이 것은 아닌 듯 싶다.
십자카드를 만족하는 수들이 a, b, c, d로 완전탐색을 하면서
이렇게 조건을 걸어 주었는데 =====>>>>> (a <= b && a <= c && c <= d)
이 것은 엄청 잘 못 된 방법이었다. 문제를 제대로 파악하지 못 한 케이스였다. ㅜㅜ
무조건 십자카드는 십자카드에 있는 순서대로 글자를 바꾸어가면서 최소값을 찾아봐야 하는데, 위의 로직은 그렇지가 않는다.
일단 처음에 몇 가지 숫자들을 써보니까 되길래 했는데 이 것이 낭패였다.
아무튼 숫자 네 개를 순서대로 돌려가면서 최소값을 찾는 과정을 반드시 해줘야 한다.
maketencard라는 함수를 사용해서 최소값을 구해주고 그 최소값이 완전탐색시의 a * 1000 + b * 100 + c * 10 + d와 일치하면 십자카드를 만족하는 수라고 판단하고 카운트를 올려주었다. 그리고 입력받은 수와 동일한 값이 나오면 빠져나오게 하고 카운트를 출력해주는 방식으로 구현했다.
