1. 문제 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 2. 풀이 단순 구현 문제이지만 문제에서 유의해야 할 점은 바로 톱니바퀴가 연쇄적으로 상태가 바뀌는 것이 아니라는 점이다. 이게 무슨 말이냐면 아래 이미지에서 1번 톱니바퀴를 회전시킨 결과에 따라서 2, 3, 4번 톱니바퀴의 회전이 결정되는 것이 아니라는 말이다. 즉, 아래 이미지와 같이 정적인 상태에서 회전 여부가 결정이 되고 최종적으로 한 번에 회전하게 된다는 것이다. 회전에 대한 결과가 다음 회전에 대해 영향을 미치지 않게 구현하기 위해서는 ..

1. 문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 2. 풀이 구현/시뮬레이션 유형의 문제로, 우선 문제를 꼼꼼하게 이해하는 것이 무엇보다 중요한 문제다. 뱀의 움직임은 크게 아래와 같이 세 가지 유형으로 분리해서 생각할 수 있다. 1) 더 움직일 수 없는 경우 지도에서 벗어나려 하거나 움직이고자 하는 칸에 뱀의 몸뚱이가 있는 경우 게임은 종료된다. 2) 사과를 먹는 경우 사과를 먹는 경우 몸 길이가 1 늘어나게 된다. 문제에서는 복잡하게 설명하였으나, 다음칸으로 전진한 머리를 유지하고 꼬리는 삭제되지 않는다..

1. 문제 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 2. 풀이 뭔가 주어진 수열의 연속된 부분합의 최대를 구하는 것이 수학적인 공식으로 해결할 수 있을 것 같기도 한데... 귀찮아서 백트래킹으로 풀었읍니다... 백트래킹을 시도할 수 있는 근거는, 문제에서 주어진 정수 배열의 범위가 최대 8로 8!의 경우의 수만 해결해주면 되기 때문이다. 따라서 배열에서 중복되지 않는 순열을 만드는 기법을 이용해 합을 산정해주었다. 이 때 매개변수로 이전 idx를 넘겨줌으로써 연속된 idx들의 합을 계속해서 더해나갈 수 있도록 처리하였..

1. 문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 2. 풀이 구현 문제이지만 주사위를 굴리는 방법을 구현하는 과정에서 실수를 범하기 좋은 유형의 문제다. 하지만 문제는 꽤나 단순하게 접근할 수 있는데, 그 이유는 주사위 6면에 대해서는 1차원 배열로 선언이 가능하며 네 방위(동, 서, 남, 북)로 움직이는 행위만 잘 정의해주면 되기 때문이다. 따라서, 각 배열의 index에 대해 위치를 사전에 정의해두고, 이를 네 방면으로 굴렸을 때 인..

1. 문제 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 2. 풀이 해당 문제를 요약하자면 주어진 수열에서 연속된 부분수열의 합이 C를 만족하는 경우의 수를 찾으라는 내용이다. 가장 단편적인 방법으로는 brute-force로 해당 문제를 해결해도 될 것으로 보인다. 하지만 연속된 부분수열의 합을 매번 구해야 한다면 O(N²)의 시간복잡도가 발생할 것이다. 그렇다면 부분 수열의 합을 어떻게 하면 효율적으로 계산할 수 있을까를 먼저 해결해보자. 1.1 누적합 연속된 부분..

1. 문제 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 2. 풀이 단순한 구현 문제이지만, 로봇의 동작이 다소 복잡하게 정의되어 있어 난이도가 올라간 것으로 보인다. 하지만 문제에서 정의한 청소기의 동작 방식을 순차적으로 잘 구현만 한다면, 큰 어려움은 없다. 현재 칸이 아직 청소되지 않은 경우, 현재 칸을 청소한다. 현재 칸의 주변 4칸 중 청소되지 않은 빈 칸이 없는 경우, 바라보는 방향을 유지한 채로 한 칸 후진할 수 있다면 한 칸 후진하고 1번으로 돌..

1. 문제 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 2. 풀이 전형적인 백트래킹 유형의 문제로, 백트래킹(backtracking)을 이용한 순열만들기 유형의 문제라고 보면 된다. 그렇다면 중요한 것은 어떠한 조건을 만족시켜야 하는가를 잘 정의해야 하며, 해당 조건들은 아래와 같다. 모음 1개 이상 자음 2개 이상 사전 순으로 출력 길이 C의 문자열 생성 사전 순으로 출력해야 하는 조건이 있기 때문에 입력 받은 문자 배열을 오름차순 정렬을 먼저 해주고, 모음 및 자음의 개수는 backtracking 메서드의 ..

00. 들어가며 테스트 주도 개발(TDD, Test-Driven Development), 말 그대로 테스트가 메인이 되는 소프트웨어 개발 방법론으로 선 개발 후 테스트가 아닌, 선 테스트 후 개발 방식을 의미한다. TDD가 반드시 필요한가 혹은 유리한 것인가에 대한 다양한 포스트들이 존재하지만, 현재 필자는 TDD가 필요하다는 입장이다. 현재 서비스 운영회사를 다니고 있고, Legacy와의 전쟁이 이어지고 있는 가운데 리팩토링 과정에서 수정으로 인한 사이드이펙트를 발생시키지 않기 위해서는 TDD를 도입하는 것이 바람직할 것이라고 생각하기 때문이다. 또한 동료들이 TDD에 대한 관심도가 상당히 높은 편인데, 스스로 많이 부족하다고 생각하여 본격적으로 TDD에 대한 공부도 함께 하고자 한다. 다른 카테고리의..

보다 유연하고 확장성 있는 설계를 하기 위해 나는 과연 객체에 대해서 온전히 이해하고 있을까? 사내스터디로 조영호님의 오브젝트라는 책을 공부하게 된 배경이다. Chapter 3를 통해 언급될 역할, 책임, 협력은 실생활에서도 적용된다고 보는데, 내가 회사에서 맡고 있는 역할과 책임을 다하기 위해 그리고 보다 나은 협력을 구축하기 위해 공부하고 있는 내용을 블로그에도 추가적으로 정리하고자 한다. 앞으로 해당 카테고리에 기재할 내용들은 모두 앞서 말한대로 조영호님의 오브젝트 책을 보고 공부한 내용을 정리한 게시글들입니다. 반드시 기억해야 할 내용들을 요약함과 동시에, 공부하며 든 생각을 함께 정리합니다. Chapter 01. 객체, 설계 여느 공학보다 상대적으로 짧은 역사를 가지고 있는 소프트웨어 분야는 이..

1. 문제 2642번: 전개도 입력은 여섯 줄로 되어 있으며 각 줄에는 0에서 6까지의 정수들이 여섯 개 있고, 숫자 사이에는 빈칸이 하나씩 있다. 1에서 6까지의 숫자는 전개도의 면을 나타내고, 0은 전개도의 바깥 부분을 나 www.acmicpc.net 2. 풀이 문제에서 요구하는 것은 간단하다. 전개도가 주어졌을 때, 정육면체를 만들 수 있는 전개도인지 판단하고 가능하다면 숫자 1이 써져 있는 면의 반대 면에 위치한 숫자를 출력하는 것이다. 그렇다면 당연하게도 우리는 주어진 전개도가 정육면체를 만들 수 있는지 여부를 어떻게 판단할 것인가를 고민해야 한다. 2.1 정육면체 전개도의 종류 먼저 정육면체를 만들 수 있는 전개도의 종류는 아래 이미지와 같이 총 11가지가 있다. 그럼 첫 번째로, 11가지 유..