01. 영화 예매 시스템 영화 예매 시스템을 구현하면서 객체지향 프로그래밍에 대한 개념을 잡아본다. 1) 요구사항 정의 영화: 영화에 관련된 기본 정보(제목, 상영시간, 가격정보, ...) 상영: 실제로 관객들이 영화를 관람하는 사건 할인조건: 가격의 할인 여부(순서조건, 기간조건), 할인 정책에는 다수의 할인 조건을 설정할 수 있음 순서조건: 상영 순번을 이용해 할인 여부를 결정 기간조건: 영화 상영 시작 시간을 이용해 할인 여부를 결정 할인정책: 할인 요금을 결정, 영화당 하나의 할인 정책만 할당할 수 있음 금액 할인 정책: 예매 요금에서 일정 금액을 할인해주는 방식 비율 할인 정책: 정가에서 일정 비율의 요금을 할인해주는 방식 02. 객체지향 프로그래밍을 향해 진정한 객체지향 프로그래밍으로의 전환은..

1. 문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 2차원 DP형태의 문제라 직관적으로 해답을 떠올리기 다소 어려운 유형의 문제라고 할 수 있다. 따라서 점화식을 먼저 한 번 도출해보도록 하자. 숫자 N을 정수 K개의 조합으로 만들 수 있는 문제를 다시 재조합하면 아래와 같이 생각할 수도 있다. dp[N][K]는 N을 K개 조합으로 만드는 경우의 수를 의미하고, 예시로 N = 6이고 K = 4라고 가정해보자. (_ , _ , _ , L) 네 개의 숫자 조합에서 마지막 자리를 L(0 ≤ L ≤ 6) 로 결정한다면, L 값에 따라서 아래 표의 경우의 수가 만들어짐을 알 수 있다. L case 0 dp[6][3] 1 dp[..

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번으로 돌..