https://www.acmicpc.net/problem/1334 문자열 구현 문제다. 펠린드롬 수라고 해서 1씩 키워서 펠린드롬인지 확인해봐야지 라고 생각했으나 자릿수가 최대 50인 걸 보고 바로 문자열로 틀었다.이전에는 문자열에서 1씩 키워서 확인하는 방법을 사용했던 것 같다. (당연히 시간초과겠지^^) 3년 만에 문제를 다시 보고 바로 든 생각은 중점을 기준으로 비교해나가는 것이었다.해당 수 보다 크면서 가장 작은 펠린드롬 수를 구하기 위해서는 최대한 뒤쪽 수를 높여야 한다. 중점 기준으로 중앙에서부터 왼쪽과 오른쪽 문자를 비교해나간다.왼쪽 문자가 큰 경우 오른쪽 문자만 값을 키우면 되고, 오른쪽 문자가 큰 경우 중점 값을 키우면 된다. 처음에는 문자열 길이가 짝수인 경우와 홀수인 경우를 나눠서 생..
Algorithm/Implementation
https://www.acmicpc.net/problem/1022 백준 문제 중 '시도했지만 맞지 못한 문제' 도장 깨기를 해보려고 한다.구현 문제다.중앙부터 시작해 돌아 나오는 소용돌이 중 (r1, c1) 부터 (r2, c2)를 출력하면 되는 문제다. 소용돌이 최대 크기가 10001 x 10001 이라서 그냥 만들어 놓고 범위만 출력하면 안되나? 했는데 어림도 없다.열심히 규칙을 찾기 위해 이리 저리 숫자 놀이를 해본 결과 8이라는 숫자를 이용할 수 있었다.1을 중심으로 8방향으로 점점 커지는 숫자들의 규칙이 (공차가) 8씩 증가했다.위로 가는 걸 기준으로 1 4 15 34 --- 이 숫자들이 간격은 3 11 13 --- 간격의 간격이 모두 8이었다.8방향 모두 같은 규칙이고, 간격의 시작점만 달랐다...
https://www.acmicpc.net/problem/2818 수학, 도형 감각이 약간 필요한 구현 문제다.n X m 배열을 1, 1부터 n, m까지 주사위가 ㄹ자로 모든 면을 굴러간다.이 때 모든 칸에서의 윗 면의 합을 구하는 문제다.시작은 윗 면 1, 앞 면 2, 오른쪽 면 3이다. 일반 주사위와 마찬가지로 마주보는 면의 합은 7이다. 굴러가는 걸 하나하나 구현하는 방법이 가장 먼저 떠올랐으나입력 범위가 n ,m 노가다 구현 방법도 떠오르지 않았다... 경우의 수가 너무 많아보였다. 그래서 생각한 건 가로의 길이가 4n + 0, 4n + 1, 4n + 2, 4n + 3인 경우로 나누어 생각했다.사실 1, 2, 3, 4만 생각해보고 그 후로는 계속 반복될 것이라고 생각했다.몇 줄을 내려가야 처음 상..
https://www.acmicpc.net/problem/17822 난이도를 확 높인 골2 구현 문제다. 나름 유명한 문제고, 이전에도 문제 찾다가 종종 본 적이 있었는데 딱 봐도 귀찮아서 안했었다.근데 오랜만에 잡으니까 근자감으로 이 정도는 껌일 것 같아서 시도 했더니 껌이었다ㅋ 우선 원판 회전을 위해 배열 대신 벡터를 사용했다.방향을 주의하여 한쪽 끝의 값을 저장하고 삭제한 뒤 반대쪽 끝에 값을 삽입했다. 이후 이웃한 값이 같은 값인지를 판단해야 한다.간단하게 머리로 시뮬레이션을 돌려봤더니 밖에서부터 하든 안에서부터 하든 문제가 발생했다.예를 들면 원판의 값이 1 1 1인 경우 처음 두 개의 1 1 이 같아 0 0 1로 바꿔버리면 마지막 1은 같은데도 불구하고 무시된다. 그래서 찾은 방법은 원 배열은..
https://www.acmicpc.net/problem/1283 몸풀기로 실버 문제를 한 문제 더 풀었다. 문자열, 구현 문제다.분명 어려워 보이지는 않는데 C++ 문자열은 split도 안되고 문자열 전체의 대소 변경도 안되는 관계로 조금 까다로웠다. 우선 입력 받는 문자열에 공백이 포함되므로 getline을 이용해서 입력을 받는다.(getline은 쓸 때마다 헷갈려서 찾아봤는데 이번 학기에 타 과 C++ 수업 또 들으면서 확실히 익숙해졌다.)다른 언어들이면 split을 이용해서 공백으로 구분을 했을텐데 C++은 그런게 존재하지 않기에 반복문을 돌렸다.1. 첫 글자가 단축키로 지정되었는지 확인2. 이전 글자가 공백인 글자가 단축키로 지정되었는지 순차적으로 확인 3. 별다른 조건 없이 옵션에 포함된 글자..
https://www.acmicpc.net/problem/1138 사실 이렇게 빨리 다시 코테 블로그를 작성하게 될 줄은 몰랐다.오랜만에 하니 역시나 재밌고, 코드를 더더더더더 간결하게 작성하고 싶어진다. 구현 문제다.나를 기준으로 왼쪽에 자신보다 큰 사람이 몇 명인지 순차적으로 입력이 들어온다.이와 비슷한 고난도 문제들에서는 자신보다 큰 거나 작은 것이 아닌 그들끼리도 관계를 가진다.그러나 이 문제는 나와의 관계만 파악하므로 쉽게 해결할 수 있었다. 입력의 크기가 굉장히 작기 때문에 효율적인 방법을 생각하지 않아도 해결할 수 있다. 작은 사람부터 배치할 것이기에 이후에 위치하는 사람들은 나보다 큰 사람이다.따라서 1번부터 n-2번 까지는 왼쪽에서 부터 i+1번째 빈 칸에 위치하면 된다.n-2번 까지 위..