문제 이해 단계 https://www.acmicpc.net/problem/1022 더보기 반시계 방향으로 돌아가는 소용돌이를 구현해야 한다. 특이한 점은 음수 좌표까지 존재하고 이미 그림 상의 좌표는 지정해 놨고 위치도 이미 정해져 있다는 것이다. 우리가 해야 할 것은 가장 왼쪽 위 칸(r1, c1)과 가장 오른쪽 아래 칸(r2, c2) 사이에 있는 사각형 영역을 출력하는 것이다. 출력을 할 때는 왼쪽에 공백을 넣어 오른쪽에 공백을 넣어 출력해야 한다 문제 접근 단계 해당 문제에서 고려해야 할 점이 많다. 반시계로 도는 소용돌이 구현 이러나저러나 결국에는 반시계로 도는 소용돌이를 구현해야 해당 문제를 풀 수 있다. 위에서 정해준 (0,0) 좌표에서 시작하여 반시계방향으로 도는 소용돌이를 만드는 방법을 생..

문제 이해 단계 배열 돌리기 시리즈 문제. NxM 크기인 배열에 K개의 회전 연산 (r, c, s)이 들어오는데, 이건 NxM안에 포함된 정사각형을 의미한다. 이 정사각형의 크기는 왼쪽 위 대각선은 (r-s, c-s)을 오른쪽 아래 대각선은 (r+s, c+s)를 가진다. 이 정사각형은 위에 그림처럼 회전하게 된다. K개의 회전이 끝난 후 각 행의 합 중 가장 작은 값을 답으로 출력한다. K개의 회전연산의 순서는 임의로 섞을 수 있으며, 최소 값이 나오도록 해야 한다. 문제 접근 단계 배열 돌리기 시리즈 문제인데, 돌아가는 패턴 자체는 익히 봐왔던 패턴이다. 이 패턴을 시계방향을 돌린다. 다른 점은 총 2가지인데 회전하는 정사각형이 따로 있다는 점과, 회전 순서를 섞을 수 있다는 것이다. NxM 배열에서 ..

문제 이해 단계 짧고 간결해서 아주 좋은 문제 4와 7로 구성된 숫자 중에서 입력된 K번째로 작은 수를 구하는 문제 문제 접근 단계 문제에서 건질만한 것은 K의 범위가 10^9라서 int 범위를 넘어가지 않는다는 것 정도? 그다음부터는 찾아내야 할 것 같다. 이렇게 수를 다루는 문제 같은 경우, 1번째부터 K번째 작은 수까지 한번 적어서 생각해 보는 게 낫다. 대충 어느 정도 열거해 보면 이런 식인데.. 정말 4와 7을 열거하는 것이다 보니 얼마씩 더해지고 그런 건 없는 것 같다. 그렇다면 브루트포스처럼 첫 번째부터 구해야 하는 K번째까지 일일이 세야하나? 그것도 불가능하다. K가 10^9까지이기 때문에 10^9 번 계산한다면 분명 시간초과가 날 것이다. 그렇다면 하다못해 해당 K가 몇 자릿수 인지는 알..

문제 이해 단계 우리가 익히 아는 사다리 타기인데, 입력으로 인원수 K와 가로줄의 개수 N이 들어온다. 그다음에는 사다리 타기의 결과가 문자열로 주어진 후, 사다리 타기의 모양이 주어진다. 사다리 타기의 시작은 무조건 알파벳순대로 들어온다. (ABCDE..) 사다리 타기가 종료되면 입력됐던 결과가 출력되도록 "???"를 구성하는 것이 해당 문제. 만약 구성하지 못할 경우 인원수만큼 x를 출력한다. 문제 접근 단계 사다리 타기에서 처음 상태에서 마지막 상태까지 가능한가를 따져보려면, 일단 최대한 두 상태가 근접해야 한다. 다행히도 "?????"로 들어오는 가로는 무조건 한 줄이기 때문에 직선은 하나 차이로 들어온다. 아래 그림과 같이 "???"에 최대한 가까이 붙여주면 이를 판단하기 훨씬 더 쉬워진다. 그..

문제 이해 단계 https://www.acmicpc.net/problem/14888 N개의 수와 N-1개의 연산자가 주어진다. 연산자가 주어지는 방법은 공백을 구분으로 개수로 들어온다. 처음부터 덧셈, 뺄셈, 곱셈, 나눗셈이다. 나눗셈은 몫만 남고 나머지는 버린다. N개의 수 사이에 입력받은 연산자들을 마음대로 배열할 수 있을 때, 나올 수 있는 최댓값과 최솟값을 구하는 문제 문제 접근 단계 해당 문제에서 봐야 할 점은 수의 개수인 N이 최대 11개라는 것이다. 이에 따라 연산자도 최대 10개밖에 되지 않는다. 모든 연산을 하나하나 확인하면 O(n)이 n! 가 될 것인데, 11! 이기 때문에 충분히 가능하다. 하지만 사이사이에 연산자들을 차례차례 나열해 보고 계산 값의 최댓값의 최솟값을 구하는 백트래킹 ..

문제 이해 단계 문제 자체는 굉장히 심플하다. 0 ~ 9까지 숫자를 딱 한 번씩만 사용해서 K자릿수를 만드는데 아래의 두 조건을 동시에 만족하는 수가 몇 개인지 구하는 문제 1. 서로 다른 소수의 합으로 나타낼 수 있어야 함 2. M으로 나누어 떨어지지 않을 때까지 나눈다. (계속 나눈다.) 더 이상 나눌 수 없을 때의 수는 소수의 곱이다. ( 이때의 두 소수는 같아도 됨) 문제 접근 단계 일단 문제 조건에서 공통적으로 소수라는 키워드가 계속 나온다. 소수의 합이던 소수의 곱이던 알기 위해선 일단 소수를 알아야 한다. 이럴 때 쓰이는 대표적인 수학적 알고리즘은 에라토스테네스의 체이다. 이를 이용하여 K = 5 일 때 즉 5자리일 때 (99999)까지 일 때의 소수를 모두 구할 수 있다. 소수의 리스트들을..

문제 이해 단계 https://www.acmicpc.net/problem/16927 배열 돌리기 시리즈 문제 NxM 직사각형을 R번 회전시킨다. 회전시킬 때 한 칸씩 반시계 방향으로 돌아가는데, 직사각형 안에 직사각형이 있는 구조다. 그림을 보면 이해가 빠를 것이다. 이런 상황일 때 R번 회전시켰을 때의 결과를 구하는 것 문제 접근 단계 이전에 풀었던 배열 돌리기와 방향만 다르지 완전히 똑같은 문제 아닌가? 라고 생각했는데 제한 조건을 보니 아니었다. R이 최대 10^9이라는 점.. 이전 문제는 한 칸씩 이동시키는 것으로 구현했었다. 이 문제는 그렇게 하면 최악의 경우 10^9 번 이동시켜야 한다. 그럼 당연히 시간초과가 뜨겠지.. 해당 문제에서 구현해야 할 것은 어떻게든 R을 줄여서 이동하는 로직을 구..

문제 이해 단계 문제 이해하는데 좀 오래 걸렸다. 입력으로 테스트케이스 T와 알파벳(문자열)이 주어지면, 그 알파벳들을 사전순으로 배열한다고 가정한다. 사전순으로 쭉 나열했을 때, 입력으로 들어온 문자열 다음으로, 나올 문자열을 출력하는 것이 해당 문제 문제 접근 단계 해당 문제에서는 동일한 문자열에 있는 알파벳들 간의 사전순, 즉 아스키코드의 크기가 중요하다.예제 입력으로 나와있는 것으로 한번 보자. 알기 쉽게 문자 말고 사전순서의 순위로 표시해 보자. HELLO → HELOL == 21334 → 21343 DRINK → DRKIN == 15243 → 15324 SHUTTLE → SLEHTTU == 5264431 →5312446 ZOO → ZOO == 211 → 211 노란색 바탕인 숫자들은 변화가 일..