Young

https://www.acmicpc.net/problem/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4 www.acmicpc.net 그냥 구현 문제입니다. 주어지는 R 값이 매우 큰데 이대로 한 칸씩 돌리면서 돌면 당연히 시간초과가 나겠죠. 배열의 고리의 길..

종만북에서 나오지만요. '중복없이 몇 개 중에 몇 개를 선택하는 방법' 너무 중요하게 다루고 있죠.완전 탐색의 기본 중에 기본 어떤 상황에서 물어봐도 바로 나와야 할 대답입니다. 우선 간단한 for문으로 고르는 방법부터 알아보겠습니다. 123456for(int i = 0; i

오늘은 DP의 특별한 문제 형태라고 할 수 있는 LIS를 알아보겠습니다.보통의 DP로 풀게 되면 O(N^2)으로 풀게 됩니다. 하지만 N의 값이 커지면 O(NlogN)의 알고리즘이 필요합니다. 우선 LIS 문제 정의 부터 알아보겠습니다. The Longest Increasing Subsequence (LIS) problem is to find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order. For example, the length of LIS for {10, 22, 9, 33, 21, 50, 41, 60, 80} is..

컴퓨터로 문제를 풀 때, 보통 그 문제는 탐색을 기반으로 합니다.문제가 정의하고 있는 '공간'을 탐색합니다. 상태를 논리적으로 정의할 수 없다면, 모든 공간을 커버한다는 보장이 없기 때문에해가 맞는 것인지 판별할 수 없습니다.그 다음 공간은 이전의 상태를 통해 발생하기 때문에, 트리처럼 공간이 뻗어 나갑니다. 그 공간을 방문하는 방법 중에 'BFS'와 'DFS'가 있습니다. 지금은 BFS(Breadth First Search)를 설명하려고 합니다. 영어 뜻 그대로 넓이 우선 탐색이다. 트리의 가지를 따라서 무작정 들어가지 않고, depth를 하나씩 늘려갑니다. 아래는 BFS와 DFS를 비교하는 그림입니다. 문제에 따라 어떤 방문 방법을 선택해야 정답을 빠르게 찾을 수 있을 것인지판단하고 적용해야 합니다...