SY DevLog

https://algospot.com/judge/problem/read/BOARDCOVER algospot.com :: BOARDCOVER 게임판 덮기 문제 정보 문제 H*W 크기의 게임판이 있습니다. 게임판은 검은 칸과 흰 칸으로 구성된 격자 모양을 하고 있는데 이 중 모든 흰 칸을 3칸짜리 L자 모양의 블록으로 덮고 싶습니다. 이 algospot.com 재귀함수를 이용하여 문제를 풀었다. 게임판을 (0,0)부터 시작하는 좌표상에 위치시킨다고 할 때, L자 블록이 특정 위치 (tx,ty)를 포함하는 경우는 다음과 같이 총 12가지이다. (tx,ty)를 기준으로 했을 때 (tx,ty)를 포함시키는 L블럭이 감싸는 3개의 좌표 모두 흰 칸이어야만 L블럭을 사용할 수 있다. 즉, (tx,ty) (x1,y1)..

https://www.acmicpc.net/problem/25501 25501번: 재귀의 귀재 각 테스트케이스마다, isPalindrome 함수의 반환값과 recursion 함수의 호출 횟수를 한 줄에 공백으로 구분하여 출력한다. www.acmicpc.net 문제 자체는 정말 쉬운 편에 속한다. 어떤 문자열이 주어졌을 때, 팰린드롬인지 아닌지 판별하는 문제인데 게다가 심지어 문제에서 재귀 함수까지 직접 짜서 준다. 재귀함수 호출 횟수도 출력해야 하기 때문에, 주어진 재귀함수에다가 카운트 변수 하나 추가하여서 호출 될 때마다 +1 해주면 끝이다. ...라고 생각했으나, 계속 5% 대에서 실패 다음 코드는 실패가 떴을 때의 제출한 코드이다. #include #include int T; int cnt; int..

https://algospot.com/judge/problem/read/PICNIC algospot.com :: PICNIC 소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 algospot.com 알고리즘 학생들을 짝지어 주되, 짝이 된 학생끼리는 서로 친구이도록 짝을 지어줘야하는 문제이다. 친구인지 아닌지 여부는 미리 주어진다. 학생의 수가 총 4명이고 n = 4, 친구쌍이 총 6쌍이고 다음과 같을 때 m = 6 (0,1) (1,2) (2,3) (3,0) (0,2) (1,3)가 서로 친구인 쌍이다. 4 6 0 1 1 2 2 3 3 0 0 2 1 3 0번 학생부터 4번..

2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 비트마스크를 이용한 동적 프로그래밍 + dfs 방법으로 풀 수 있는 문제이다. 아래는 문제 예제의 도시와 경로를 나타낸 것이다. dp 2차원 배열을 생성한다. 첫번째 인덱스는 현재 위치한 도시, 두번째 인덱스는 여태까지 방문한 도시정보를 비트마스크로 표현한다. dp[1][0001(2)] : 현재 위치한 곳은 1번 도시이고, 여태까지 방문한 도시는 1번 도시일 때, 전체 도시를 순회하기 위해 남아있는 최소비용 dp[2][001..

1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 분할하여 같은 동작을 반복하기 때문에 재귀를 이용하여 풀 수 있다. 처음에는 1, 2, 3, 4 분면의 모든 경우의 수를 다 재귀함수 호출을 했더니 시간 초과가 나왔다. 그래서 조건문을 이용하여 (r, c)이 포함된 사각형만 선별적으로 재귀를 실행하도록 변경하였다. 2차원 배열의 정보를 가장 왼쪽 위 좌표(i, j) 와 한 변의 길이 size로 나타낼 때, 이 2차원 배열을 4등분한 각각의 사각형은 다음과 같이 표현이 가능하다. - 2사분면 : (i, j..

2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 색종이를 계속 4등분으로 분할하여 모두 같은 색으로 이루어졌는지 아닌지를 확인하는 문제. 분할을 하면서 동일한 로직을 반복하기 때문에 재귀를 이용하여 해결할 수 있다. 재귀 문제는 항상 base case 즉, 탈출 조건이 무엇인지를 확인해야 한다. 이 문제의 base case은 다음과 같다. 1. 색종이의 크기가 1인 경우 색종이의 크기가 1이면 더 이상 분할이 불가능하므로 재귀를 종료한다. 2. 색종이의 크기가 1보다 크지만, 모두 ..

2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 다음과 같은 트리가 있을 때, 인오더와 포스트오더로 나타내면 아래와 같다. InOrder : 4 - 2 - 5 - 1 - 6 - 3 - 7 PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1 포스트오더로 나열하면 가장 오른쪽에 있는 값은 트리의 루트가 된다. 포스트오더는 왼쪽 노드 - 오른쪽 노드 - 가운데 노드 순서대로 순회하기 때문이다. PostOrder : 4 - 5 - 2 - 6 - 7 - 3 - 1 인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자..