J.Althea

https://www.acmicpc.net/problem/10610 Silver 5 라는 난이도 보다는 체감상 어려웠던 문제이다. 이 문제를 풀면서, 30의 배수를 어떻게 빠른 시간내에 판단할 수 있을까를 고민했다. 30의 배수는 3의 배수이면서 10의 배수인지를 판단하면 되는데,  10의 배수를 판단하는 방법은 0이 하나라도 있는지 보면 알 수 있어서 간단했다. 3의 배수가 관건이었는데, 3의 배수는 각 자릿수의 합을 다 더해도 3의 배수 꼴로 나타난다. 이렇게 주어진 수가 30의 배수임을 알게 되면, 내림차순으로 정렬해도 30의 배수가 된다. 추가적으로 이 문제를 풀면서, 각 자릿수의 합이 어떤 규칙을 갖는지 알아보았다. 3 6 9 12 15 18 21 24 27 30... 3 6 9 3 6 9 3 6 9... (각 자리수의 합이 3의 배수꼴로 나타남) 9 18 27 36 45 54 63 72 81 90... 162...  6147 9 9 9 9 9 9 9 9 9... (각 자리수의 합이 9의 배수꼴로 나타남) 3, 9 가 이러한 문제로 응용될 수 있겠다. 생각해보면, 90의 배수는 9의 배수와 10의 배수를 만족시켜야 한다. 그런데 9의 배수는 3의 배수이므로 저 문제에서 주어진 30이라는 수를 구했던 방법처럼 구할 수 있다. 이 방법 외에도 시간 내에 풀 수 있는 방법이 있는지 궁금하다.  :)

memset 함수를 사용하게 되면, 일반적인 for문을 이용하여 초기화할 때보다 속도상의 이점이 있기 때문에 배열을 초기화할 때 자주 사용하게 된다. 그런데, memset을 사용할 때 초기화할 값을 넣을 때는 조심해야한다. void   * memset (   void   * dest,  int  ch,  size_t  count  ) ; 값에 대한 타입이 int 형이지만, 기본적으로 내부에서 1byte 에 해당하는 단위로 초기화를 진행한다. 예를 들어서,  int n;  memset(&n, 1, sizeof(int)); cout << n; 위와 같이 사용한 경우, 출력 값이 16843009가 나온다. cout << (short)n; 위의 출력 값은 257이 나온다. 이 출력 값들을 이진수로 변환하여 분석해보자. 16843009 => 1000000010000000100000001 257 => 100000001 위를 최하위 비트부터 8개씩 끊으면, 1byte가 된다. 1    00000001    00000001    00000001 1    00000001 즉, 내부적으로 1byte에 해당하는 단위로 초기화를 진행하는 것을 볼 수 있다. 우리가 원했던 것은 int 형의 변수 n에 1이라는 정수형 값으로 초기화하는 것이다. 그런데 int 형은 4byte이므로, 4byte가 하나의 단위로 보고 최하위 비트에 1을 쓰고, 나머지 비트 31개를 0으로 초기화해야 하는데, memset 함수는 그러지 않고 1byte를 하나의 단위로 보고 초기화를 진행했던 것이다. 이러한 이유로 검색을 해보면, memset에 초기화할 때는 0을 쓰라고 권유 한다. 0의 경우에는 어떠한 단위로 진행해도, 모든 비트에 숫자가 0이기 때문에 올바른 결과가 나오기 때문이다. 그러나 0 이외에...

https://www.acmicpc.net/problem/20543 (혹시나 풀어보실 분들은 알고리즘 분류를 보지 않고 풀어보길 권장합니다.) 이 문제를 처음 보고, 간만에 신선하다는 느낌을 받았다. 어떤 알고리즘이나 자료구조를 알고 있으면,  흔히 많이 나오는 유형에 속하는 문제가 있는가 하면, 그렇지 않은 문제도 있다. 이 문제를 풀면서 규칙을 찾고 시간을 단축시켜 나가는 과정이 재미있었고, 예전에 수학에 매력을 느꼈을 때의 느낌과 비슷했다. 물론, 영문까지 포함한 많은 문제를 풀어본 건 아니지만 부족한 내가 느끼기에는 그랬다. 어려운 자료구조를 쓰지 않아도 (기본적인 재료로도)  충분히 난이도를 높여 갈 수 있는 (까다로우며 맛있는 요리?) 그런 문제들의 초입에 해당하지 않나 싶다. 아래는 풀이를 생각한 순서이다. 1. 출력은 맞지만 시간초과 풀이 2. 정답 풀이 먼저, 제한도 까다롭지 않고 시간도 2초나 주어졌기 때문에 풀어보는 것이 중요하다고 생각했다. N이 2,000일 때, 2차원 배열의 데이터 개수는 2,000 x 2,000 = 4,000,000 이다. O(n)에 해당하는 과정은 시간초과를 발생시키지 않으나, 폭탄을 찾기 위해서 자기 자신의 위치(arr[i][j])에서 가능한 모든 경우의 수를 찾으려고 하면 시간초과가 뜰 것이다. 여기까지 생각하고, 규칙을 생각해보았다. 예제 입력과 예제 출력들을 보면서, 가장 외곽에 위치한 배열의 원소들부터 채워가면 될 것이라고 생각했다. 먼저, (0, 0)부터 시작한다고 하면, 시계방향으로 테두리를 돌면서 1칸씩 안쪽으로 진행해볼 수 있다. 그러나 가장 첫 줄을 시물레이션 해보면,  우리가 이중 for문을 통해 배열을 탐색하는 일반적인 과정으로도 채워나갈 수 있다는 것을 알게 되었다. 왜냐하면, 폭탄이 있을 수 없는 구역이 존재하기 때문이다. (m = 1의 경우는 예외) m이 1인 경우에는 그대로 절댓값으로 바꿔서 출력하면 되고, m이 3이상의 홀수인 경우에 생각해보면, 외곽 테두리에 ...