문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 쉬운 듯 하지만 정답률이 낮은 이유는 감소하는 수의 최댓값은 9,876,543,210로 int형의 최댓값인 2,147,483,647보다 크기 때문에 int 형이 아닌 long형을 써주지 않아 그런것 같다. 본인의 경우에는 감소하는 수가 0~9까지만 이용가능 하므로, 11자리 이상 갈 일이 없다고 생각하질 않고 문제를 풀어 메모리 초과가 발생했다... 두 점만 명심하고 풀면 어렵진 않다...

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 풀이 테트로미노는 문제에서 나오는 5가지의 모형을 대칭, 회전시키면 총 19개의 고정 형태의 테트로미노가 나온다. 종이의 크기는 500이하로, 19가지의 모형을 모두 대입해서 모든 경우의 수를 구하는 게 충분히 가능하다. 이를 구현하기 위해서 (0,0)인 현재 위치로 부터 상대적인 위치를 저장한 int tetrominoModel[19][3][2] 가 필요한다. 1 2 3 4 5 6 7 8 ..

문제 www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 풀이 모바일 게임으로 많이 해봤을 법한 2048게임을 구현하는 문제이다. 블록들은 네가지 방향중 한 방향으로 모두 이동 시키는데, 이때 같은 크기의 블록이 있다면 합쳐지면서 두배의 수가 된다. 또한 구현에서 중요한 것이 현재의 이동을 통해 이미 한번 합쳐진 블록은 또 다시 합칠 수가 없다. 이 점을 유의하며 구현해보자. 일단은 네가지 방향중 왼쪽으로 이동시키는 경우를 구현한 M..

문제 algospot.com/judge/problem/read/CLOCKSYNC algospot.com :: CLOCKSYNC Synchronizing Clocks 문제 정보 문제 그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 �� algospot.com 풀이 이번 문제의 핵심은 두 가지이다. 시계는 4번 돌리면 결국 원상태로 돌아온다. 즉, 4번 이상 시계를 돌릴 필요는 없다. 스위치를 누르는 순서는 중요하지 않다. 예를 들어, 0번과 1번 스위치를 누른다고 할 때 무엇을 먼저 누르든 결과는 같다. int pushedNum[10]; //스위치를 누른 횟수를 저장 int c..

문제 algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 �� algospot.com 풀이 흰 칸들을 4가지 모양(회전하면 네 가지 모양이 나옴)으로 덮을 경우 가능한 경우 수를 구하는 문제. 해당 문제는 다음과 같이, 한 빈칸을 네 가지 경우로 채우는 재귀 함수를 구현한다. 빨간 부분이 호출된 칸이고, 그 칸과 인접한 1,2번 블록을 채우는 네 가지 블록 모델이다. 이렇게 네가지 경우 이외는 생각해 주지 않아도 되는 이유는 흰 칸의 위치..

문제 https://www.algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 www.algospot.com 풀이 고등학교 확률과 통계 시간에 뭔가 많이 볼 듯한 문제였다. 모든 경우의 수를 확인하는 Burute Force방법으로 해결하면 된다. 이차원 배열인 bool partnerBoard[45][45] //45인 이유는 최대의 짝의 경우 수가 (10*9)/2이기 때문 에 서로의 친구 여부를 담아둔다. 그 후에는 기저 사례로 짝지어진 수가 전체 학생 수의 반인 ..

문제 www.algospot.com/judge/problem/read/BOGGLE algospot.com :: BOGGLE 보글 게임 문제 정보 문제 보글(Boggle) 게임은 그림 (a)와 같은 5x5 크기의 알파벳 격자인 게임판의 한 글자에서 시작해서 펜을 움직이면서 만나는 글자를 그 순서대로 나열하여 만들어지는 영어 �� www.algospot.com 풀이 알고리즘 문제 해결 전략 서적에서 무식하게 풀기(Burute Force) 장에서 가장 처음 나오는 문제이다. 이 문제의 정답 비율이 극악인 이유는 단순히 모든 경우의 수를 확인하는 방법으로는 시간제한을 초과하기 때문이다. 따라서 BF장에서 나오는 문제이지만 동적 계획법(Dynamic programming)을 사용해야 시간 안에 통과할 수 있다. ..

문제 https://www.algospot.com/judge/problem/read/FESTIVAL algospot.com :: FESTIVAL 록 페스티벌 문제 정보 문제 커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 � www.algospot.com 풀이 흔히 종만북이라는 알고리즘 문제 해결 전략 책에서 가장 먼저 나오는 문제. 그 만큼 제출 횟수는 많지만 소수점 출력이 8자리 이상은 되어야해서 틀리는 경우가 많은 듯하다. 첫 문제다 보니 틀리면 상당히 의지가 꺽인다.. ㅠㅠ 가장 먼저 생각난 방법은 역시 모든 경우의 수를 모두 구해보는 부르트 포스 전략이다. 공연장을 대여할 수 있는 날의..

백준 문제를 풀던 중 분명히 예제 입력에서는 제대로 된 출력이 나오는데도 정답 소스코드를 제출하는 경우 시간 초과가 발생하는 경우가 있었다. 아무리 코드를 뜯어보아도 최적화에는 문제가 없다고 생각했는데 cout에서 주로 개행을 위해 사용되는 endl을 '\n'으로 바꿔주자 정답을 맞힐 수 있었다. 그러한 이유는 다음과 같다. endl의 경우 스트림 버퍼의 끝에 \n을 삽입해주고 flush까지 수행하여 버퍼를 비워준다. std::cin과 같이 입력을 받을 경우, 이전의 데이터가 버퍼에 남아있으면 사용자의 값입력을 받지 않고 그대로 버퍼의 값을 사용한다. 즉 버퍼를 깨끗하게 지워주어야 다음 값을 입력받을 수 있다. 이때 flush를 통해 버퍼를 비워줄 수 있다. C에서는 fflush(stdin); 와 같이 ..

지금까지 배운 객체지향 언어는 Java와 C++ 이였는데, 필자는 C++를 먼저 접하고 Java를 공부했었다. 두 언어는 지향점이 다르더라도 둘 다 C언어 기반의 객체지향 언어라 비슷한 구조가 많다. 그런데 웬걸? 두 언어를 왔다 갔다 공부하다 보니 c++에서 계속 이해가 되지 않는 코드가 있었다. 아래의 예제 코드를 보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include using namespace std; class Test{ public: Test(int n): data(n){} Test(const Test& rhs){ //복사 생성자 data = rhs.data; //rhs의 private멤버인 data접근이 가능하다..