개발일지

이번 포스팅에서는 가장 많이 쓰이는 자료구조중 하나인 스택에 대해서 알아보고 구현해 보도록 하겠다. 우선 사전적인 정의를 한번 보고오도록 하겠다. https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D 스택 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 스택의 구조 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 끝먼저내기 목록(Pushdown list)이라고도 ko.wikipedia.org 사전적인 정의에 대해서는 굳이 다시 옮겨 적진 않겠다. 중점적으로 볼것은 FILO , LIFO 구조 라는것이다. fisrt in last out, last in first out 즉 선입후출(先入後..

https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 백트래킹 알고리즘을 공부하는 N과 M 시리즈의 문제중 하나이다. 오름차순으로 수열을 출력하는 점은 같지만 이문제의 특이한 점은 중복되는 수열을 출력하면 안된다는 점이다. 즉 수열이 중복되지 않게 백트래킹하는 과정에서 특수한 조건이 하나 필요하다. 이 문제를 풀기위한 아이디어는 우선 오름차순 정렬에 집중해보는것이다. 입력받는 숫자들을 오름차순으로 정렬한뒤 백트래킹을 시행한다. 이때 그전..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 연산할 숫자가 주어지고, 연산자 +,-,*,/에 대한 개수가 주어진뒤 해당 연산자와 숫자로 구할수 있는가장 큰수와 작은수를 구하는 문제이다. 이런 문제는 그냥 모든 경우의 수를 다 따져서 푸는 브루트포스 알고리즘을 사용하지만 중복되는 연산을 하지 않는 방법인 백트래킹 알고리즘을 사용해 간단히 풀수 있다. 즉 현재 연산자가 남은 개수에 따라..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net BFS 로 간단히 풀 수 있는 문제지만 탐색과정중 뱀이나 사다리를 만나면 아예 다른 칸을 점프를 해야하는 점이 특이해서 가져온 문제이다. 주사위를 구려 1~6까지 한번에 바로 진행이 가능하다 이때 진행한 칸이 뱀이나 사다리가 존재한다면 뱀이나 사다리를 통해 이동된 다른칸에서 탐색을 진행하면 된다. 우선 방문처리할 보드, 그리고 뱀,사다리에 대한 정보를..

이번에 풀어볼 문제는 BFS 문제중 기출 문제라고 볼 수 있는 토마토 문제를 풀어보겠다. https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 첫번째 토마토 문제이다. 기존의 탐색문제들과 조금 다른 점은 탐색을 시작해야 하는 정점이 여러곳이라는 부분이다. 그동안 BFS문제를 풀 때 접근 방식은 시작정점을 큐에 넣고 꺼내서 해당 정점에 대한 탐색을 이어나가는 식으로 탐색을 진행했었고 이 문제 역시 같은 방식을 따르면 된다. 다만 시작 ..