케이스윔의 개발 블로그

문제로봇이 동서남북 4개의 방향 중에 하나를 선택해서 이동하는데 N번의 행동을 취한다. 같은 곳을 한 번보다 많이 이동하지 않을 때, 로봇의 이동 경로가 단순하다고 한다. 각 방향으로 이동할 확률이 주어질 때 로봇의 이동 경로가 단순할 확률을 구하는 프로그램을 작성하시오.문제 출처: 백준 온라인저지(https://www.acmicpc.net/problem/1405) 풀이같은 곳을 한 번보다 많이 이동하지 않는 이동경로 = visited 배열이 0인 곳만 방문하는 경우를 의미합니다. N은 14보다 작거나 같으므로 visited 배열을 만들기 위한 값을 생각해보면 동, 서, 남, 북쪽으로만 N번 이동할 수 있으므로 (2*N)*(2*N)의 크기가 필요합니다. 출발점은 N, N이라고 생각할 수 있습니다. 그 다..

문제개수 N이 주어지고 가능한 모든 N*(N+1)/2개의 구간의 합에 대한 부호가 주어질 때, 수열 N을 구하시오.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1248) 풀이처음에 어렵다고 느껴서 헤맸던 문제입니다! N이라는 숫자가 주어지고 구간의 합의 모든 조합에 대한 +, -, 0가 주어질 때 이 모든 조건을 만족하는 수열을 구해야합니다. 처음에는 입력을 1차원 배열로 받다보니 i번째 자신에 대한 부호를 찾는 것도 몇번째에 위치하고 있는지 계산을 해야해서 복잡해졌습니다. 그래서 이 방법을 처음에 시도했다가 배열을 N*N으로 만들어서 첫째 줄에서는 N개를 사용, 두번째 줄에는 N-1개를 사용하도록 했습니다. 그렇게 하니 i번째 자리의 부호를 알기 위해서는 nu..

앞으로는 알고리즘문제들을 풀기 전에 이론에 대해서 좀 더 공부하고, 글로도 남겨서 차근차근 정리하려고 한다. 작년에 수강했던 알고리즘수업 때 필기와 인터넷 자료, 알고리즘 문제해결전략 책을 종합해서 공책에 필기로도 남기고 블로그에 글도 남길 것이다. 앞서서 공부했던 다이나믹프로그래밍, DFS, BFS에 대해서도 다시 정리를 하고 글로 남길 예정이다. 어제부터 다시 공부하기 시작한 알고리즘 분류는 Backtracking(백트래킹)이다. '백트래킹이란 무엇이다'라고 확실히 정의를 내리기는 어렵지만, 백트래킹은 가능한 모든 조합에 대해 전부 시도를 하는 것이다. 이 말을 자세히 다시 살펴보면 '가능한 모든 조합'이기 때문에 조건에 맞을 경우에 전부 시도를 한다. 알고리즘 교수님께서 해주신 필기에는 "DFS w..

문제 정의알파벳으로 이루어진 N개의 단어가 수학문제가 들어오면, 각 알파벳을 숫자에 대응시켜 합을 구했을 때 가장 큰 합이 나오도록 만들어야 한다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1339) 문제 풀이숫자는 0~9 까지 각 알파벳에 대응시킬 수 있으므로, 최대 대응을 시켜야하는 수는 10개의 알파벳이다.(입력자체도 모든 단어에 포함되어 있는 알파벳이 최대 10개이다.) 두줄에 걸쳐 입력되는 알파벳숫자들의 합이 최대가 되려면 일단 제일 앞자리에 있는 알파벳에 9,8,7... 순으로 큰 수를 대응시켜주면 된다. 문제는 하나의 알파벳이 두번 입력되어도 그 알파벳은 하나의 수로 대응되어야하니까 적절하게 대응시킬 수 있는 방법이 필요하다. 해결해야되는 부분들을..

문제숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.다음은 나쁜 수열의 예이다.3332121323123123213다음은 좋은 수열의 예이다.232321231232123길이가 N인 좋은 수열들을 N자리의 정수로 보아 그중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라. 예를 들면, 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다. 입력과 출력 입력은 숫자 N하나로 이루어진다. (1

문제세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다.말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다.좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다.문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/1987) 입력과 출력첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다. (1= C) continue; ..

문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 및 출력첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력은 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 문제 출처 : 백준 온라인 저지 https://www.acmicpc.net/problem/9663 풀이퀸을 놓을 때 규칙은 같은 가로줄, 세로줄에 놓을 수 없고 대각선으로 같은 줄이어도 놓을 수 없다. 퀸을 하나씩 놓아보며 모든 경우를 찾아보고 만약 놓을 수 없을 경우는 바로 다른 곳에 놓도록 한다. 제일 윗줄부터 차례대로 놓고, 놓은 퀸들은 배열에 저장해두고, 놓을 수 없는 경우 돌아가며 새로 퀸을..