Ikjo's Technology blog

문제 설명 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 접근 방법 해당 문제는 이름에 맞게 스택 자료구조를 이용하여 해결할 수 있었습니다. 문제에서 주어진 예시로 스택 자료구조를 직접 그려보면서 접근해보니 수월하게 해결할 수 있었습니다. 우선 최초 스택 자료구조가 비어있다고 가정했을 때, 최초 4라는 숫자를 만난다면 1 ~ 4의 숫자를 스택에 push 하고 마지막 숫자 4를 pop 시켜야 합니다. 이때 스택 자료구조는 다음과..

문제 설명 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 접근 방법 해당 문제는 그리디 알고리즘 기법을 이용하여 해결할 수 있었습니다. 사실 이 문제를 처음 봤을 때 시간 제한이 2초이길래 A에 있는 N개의 수를 재배열할 수 있는 모든 경우의 수에 대해 완전 탐색하여 구해도 되겠다는 생각을 했었습니다. 그리하여 백트래킹을 통해 각각의 경우에 수에 대해 최솟값을 구하도록 했으나, 결과는 시간 초과였습니다. 😅 N은 50보다 작거나 같은 자연수이긴 하지만 이들을 순열로 재배열한다는 것은 50!라는 엄청난..

문제 설명 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 접근 방법 해당 문제는 백트래킹을 이용하여 해결할 수 있었습니다. 우선 주어진 스도쿠 데이터에서 빈 칸(0)의 개수를 카운팅해서 백트래킹 시 최대 depth(깊이)로 설정했습니다. 이후 9 * 9 스도쿠 판 좌표 (1, 1) 지점부터 마지막 (9, 9) 지점까지 순차적으로 백트래킹하면서 빈 칸을 채워나갔습니다. 해당 빈 칸을 채울 때는 우선 해당 빈칸에 나올 수 있는 숫자 목록을 구해내도록 했습니다. 이때 해당 빈 칸에 나올 수 있는 숫자들은 해당 빈..

문제 설명 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 접근 방법 다이나믹 프로그래밍(메모이제이션 기법)을 통해 문제를 해결할 수 있었습니다. 어떻게 값을 메모이제이션 할 수 있을까 고민하던 중 그림으로 그려보다가 아이디어를 떠올릴 수 있었습니다. 위 그림을 통해 다음과 같은 사실을 알 수 있습니다. 세 개의 칸 중 왼쪽 칸의 값은 바로 위 칸의 값과 그 오른쪽 칸의 값에만 의존적입니다. 세 개의 칸 중 가운데 칸의 값은 위에 있는 세 개의 칸 값에 의존적입니다. 마지막으로, 세 개의 칸 중 오른쪽 칸의 값은 바로 위 ..

문제 설명 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 접근 방법 해당 문제는 DFS를 통한 백트래킹을 이용하여 해결할 수 있었습니다. 우선 로봇이 이동하는 평면을 나타내야 하는데, 로봇은 이 평면의 중심상에서 출발하여 동, 서, 남, 북 각각의 방향으로 이동할 수 있어야 합니다. 이때 이러한 평면의 전체 크기는 주어지는 정수 n의 크기와 규칙이 있었습니다. if n = 1, then 3 x 3 board if n = 2, then 5 x 5 board if n = 3, then 7 x 7 board...