문제 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접근이 가능하다..

클린 코드를 읽게 된 계기 알고리즘 문제 풀이를 공부하면서 느끼게 된 점이 있다. 혼자 코드를 짜고 문제를 맞히게 되면 자신의 코드를 다시 되새기며 개선점을 찾으려는 노력을 기울이기 힘들다는 것이다. 어려운 문제를 풀어보아도 결국 다시 자신이 푼 방법을 복습하지 않으면 얼마 지나지 않아 까먹게 되는 것 같다. 알고리즘 문제 풀이에서 실력 향상에 가장 중요한 것은 스스로 문제를 끝까지 잡고 늘어지는 것이 아니라, 다른 사람의 코드를 참고하더라도 자신의 것으로 흡수하는 것이라고 많이 들었다. 즉, 문제를 맞혔든 틀렸든 간에 자신의 코드를 리뷰하는 습관을 들여야 하는 것이다. 이러한 습관을 들이는 데에는 자신의 블로그에 꾸준히 문제 풀이를 올리는 것만큼 좋은 것은 없다고 생각해 블로그를 시작하게 되었다. 블로..

문제 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 풀이 실제로 스도쿠 문제를 풀때, 가능한 수 중에 한개씩 넣어보면서 진행하다 불가능할 경우 뒤로 돌아가서 수를 바꾸는데 말그대로 백트래킹이 적용 가능한 문제이다. 입력 받은 스도쿠 배열에서 다음 0을 찾아 nr,nc에 저장한 후, pos_num에 행,열과 해당 3x3 범위의 수들을 확인하여 간능한 수를 찾아준다. 그 다음은 가능한 수를 for문으로 넣어보면서 재귀호출을 하면, 마지막 0에서 ..

문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 bool board[14][14] : 퀸을 놓기가 가능하면 true로 저장해 둠. void BanBoard(int r,int c) : r과 c 위치에 퀸을 둘 경우 양대각과 가로 세로의 board를 false로 변경 voidDfs(int column): column이 N이상일 경우만 cnt를 +1하고 나머지에서는 퀸을 하나씩 두며 Dfs 재귀 호출 board_copy를 선언해 이전의 board의 값을 ..