SY DevLog

난이도는 어렵지 않은 문제이다. 어떤 수 N으로 나눌 때 나머지는 항상 N보다 작다. "나머지 = 몫"인 경우를 구하면 되므로 N보다 작은 수 i에 대하여 "i = 나머지 = 몫"이라고 할 때, "몫*N + 나머지"가 문제에서 구해야 하는 자연수이므로 i*N + i (단, i

백준 전깃줄 문제와 유사하다. 이진탐색을 사용한 증가하는최장부분수열(LIS)을 구하는 문제이다. 다만, 수열의 길이만 구하는 것이 아니라 수열 자체도 구해야 하므로 역추적하는 배열이 별도로 필요하다. 역추적을 통한 증가하는최장부분수열의 수열 구하는 방법은 아래 포스팅에 나와있다. LIS(Lowest Increasing Subsequence) - 수열 구하기 저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그.. lotuslee.tistory.com 이 문제는 전선이 만나지 않도록 하면서 전구가 ..

5670번: 휴대폰 자판 휴대폰에서 길이가 P인 영단어를 입력하려면 버튼을 P번 눌러야 한다. 그러나 시스템프로그래밍 연구실에 근무하는 승혁연구원은 사전을 사용해 이 입력을 더 빨리 할 수 있는 자판 모듈을 개발 www.acmicpc.net 이번 문제를 트라이를 이용하여 풀 수 있는 문제이다. Trie 의 insert, contain, delete 함수외에 검색횟수를 반환하는 별도의 getCount() 함수를 만들어서 문제를 해결하였다. 트라이 알고리즘에 대해 잘 모른다면 아래 링크를 참조하길 바란다. lotuslee.tistory.com/53?category=965898 트라이(Trie) - 1. 트라이 개념 및 노드 특징 트라이(Trie) 문자열들의 집합을 N진 트리 형태로 표현한 자료구조로, 문자열..

13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 처음에 각각의 A[n]에 대하여 무조건 총감독 1명은 필요하므로 cnt를 하나 증가시키고, A[n]에서 총감독이 감독하는 B명을 빼었다. -> A[n] - B 그리고 난 후, A[n] - B를 부감독이 감독할 수 있는 응시자 수인 C로 나누어서 몫을 cnt에 더하고, 만약 나머지가 존재하면 그 나머지 응시자도 감독을 해야하므로 cnt를 하나 더 증가시켰다. 그런데 결과는 '틀렸습니다.' 가 떴다. 내가 놓친..

10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 한바퀴 돌때마다 재귀함수를 호출하여서 arr 2차원 배열에 앉게 될 대기자의 대기번호를 차례대로 넣어준다. solve(int sr, int sc, int r, int c) (sr, sc)는 한바퀴에서 첫번째 시작하는 좌표를 의미하고, r은 세로 길이, c는 가로 길이를 의미한다. 소스코드 :

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 인오더에서는 루트를 기준으로 왼쪽은 왼쪽 자식 트리, 오른쪽은 오른쪽 자..

8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 이 문제는 이분탐색을 이용하여 해결할 수 있다. 사대의 위치를 arr 배열에 오름차순으로 정렬한다. 정렬 전 : 6 1 4 9 정렬 후 : 1 4 6 9 특정 동물의 위치에서 가장 가까운 사대의 위치를 이분탐색으로 찾는다. 이분탐색을 진행하는 방법은 다음과 같다. arr[middle] == x 이분탐색 범위(left ~ right)에서 arr[middle]가 동물의 x좌표와 일치한다면, 즉 사대가 같은 세로 일직선 상에 존재한다면 이 때의 사대가 동물과의 거리가..

2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net R : 홀수 OR C : 홀수 R, C 둘 중에 하나라도 홀수이면 모든 칸에 있는 기쁨을 다 더할 수 있다. 모든 칸을 다 방문할 수 있다. R : 짝수 AND C : 짝수 문제는 R과 C 둘 다 짝수인 경우이다. R과 C 둘 다 짝수인 경우에는 모든 칸을 다 지날 수 없기 때문에 기쁨의 합이 최대가 되는 방법을 생각해야한다. 처음에는 dfs를 이용하여서 모든 가능한 경로를 다 탐색한 후에 기쁨의 합이 최대가 되는 경로를 출력하도록 했었다. 그러나 결과는 '..