본문 바로가기

알고리즘

 (54)
[코드업] 4684 - 자물쇠 띠 모양의 자물쇠가 있다. 이 자물쇠는 한 줄로 늘어선 N개의 칸으로 이루어져 있고, 각 칸에는 1부터 N까지의 숫자가 하나씩 들어 있다. 맨 처음에는 1번째 칸부터 N번째 칸까지 1부터 N까지 숫자가 순서대로 하나씩 들어 있다. 아래 그림 1은 10개의 칸으로 이루어진 자물쇠의 맨 처음 모양을 보여주고 있다. 이 자물쇠를 잠그기 위해서는 다음과 같은 3회의 동작을 연속적으로 수행해야 한다. ➀ 왼쪽으로 밀기 ➁ 구간 뒤집기 ➂ 왼쪽으로 밀기 첫 번째 동작은 왼쪽으로 밀기이다. 칸 밖으로 밀려나간 번호는 다시 오른쪽으로 돌아온다. 그림 1의 자물쇠를 왼쪽으로 3칸 밀고 나면 그림 2와 같게 된다. 이렇게 왼쪽으로 K칸 밀기 동작을 K-왼쪽밀기라고 부른다. 이때 이다. 그 다음 동작은 정해진 구간의 숫자를..
[코드업] 2699 - 사투리 GSHS의 K모씨는 서울에서 태어났음에도 불구하고 대구에서 자라났기 때문에 사투리를 사용한다. 이 때문에 학교친구들은 K모씨에게 장난을 칠 때 사투리로 장난을 치는데 K모씨는 사투리와 서울말이 그렇게 다르지 않다는 것을 친구들에게 알리고 싶다. 그래서 K모씨는 주어진 사투리와 서울말의 subsequence(연속되는 부분 순서)의 최대 값을 구하려 한다. 이를 구하는 프로그램을 작성하시오. * 참고 : subsequence란 원래 순서에서 일부 몇 개를 지운 순서를 의미한다. 예를 들어 abcdefg 라는 순서가 있다면 이 순서의 부분순서는 abcdefg, adeg, efg, ag 등이 있다. 하지만 ba와 같이 순서가 바뀐 것은 부분순서가 아니다. 그리고, abcde, bace 의 최대 공통 부분순서는 ..
[코드업] 4039 - 놀이공원 문제 설명 어린이 놀이동산에 돌-블록이 타일처럼 배치되어 있는 마당이 있다. 이 마당은 아래 그림처럼 n×m 크기의 격자로 표시된다. 격자의 칸에 있는 값은 돌-블록의 높이이다. 이 마당의 입구는 (1,1) 위치이고, 출구는 (n,m) 위치이다. 이 마당에서 즐길 수 있는 놀이 중에는 입구에서 출구까지 길을 찾는 게임이 있다. 게임 참가자는 각 블록에서 동서남북으로 인접한 블록으로 점프하여 건너갈 수 있는데, 높이 차이가 1보다 큰 경우에는 건너갈 수 없다. 또한 출구를 제외하고는 마당 밖으로 나갈 수 없다. 위 예에서 출구인 (4,4) 블록까지 이동하기 위해서는 (1,1), (2,1), (3,1), (3,2), (2,2), (2,3), (3,3), (4,3), (4,4) 블록을 순서대로 지나가면 된다...
[코드업] 2652 - 극장 좌석 배치 2 문제 설명극장에 'n'개의 빈 좌석이 있다. 'k'명의 관객들이 영화를 보기 위해서 왔다. 이 관객들이 'n'개의 좌석에 앉을 수 있는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. (단, 'k'명의 사람을 서로 구분되지 않으며, 한 명이 좌석에 앉으면 그 양 옆자리는 비어 있도록 배치해야 한다.)입력첫 번재 줄에 n과 k가 공백으로 구분되어 입력된다. [입력값의 정의역] 1≤k≤n≤30출력구한 답을 첫 번째 줄에 출력한다.더보기입력 예시4 2출력 예시3#include #include #include using namespace std; long long factorial(int n){ if(n > n >> k; int blank = n - k; // 빈자리수 cout
[백준] 1865 - 웜홀 문제 때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을 하게 되면 시작을 하였을 때보다 시간이 뒤로 가게 된다. 웜홀 내에서는 시계가 거꾸로 간다고 생각하여도 좋다. 시간 여행을 매우 좋아하는 백준이는 한 가지 궁금증에 빠졌다. 한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우가 있는지 없는지 궁금해졌다. 여러분은 백준이를 도와 이런 일이 가능한지 불가능한지 구하는 프로그램을 작성하여라. 입력 첫 번째..
[백준] 12851 - 숨바꼭질 2 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 그리고, 가장 빠른 시간으로 찾는 방법이 몇 가지 인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 둘..
[코드업] 3210 - 기억력 테스트 5 주현이의 실력이 늘자 주현이 엄마는 더욱 사악해져 갔다. 이번에도 n개의 숫자를 불러주고, m개의 질문을 한다. 이번에 질문은 두 수 a, b를 이야기하는데, a번째에서 b번째 불렀던 수들 중 가장 큰 수를 묻는다. 예를 들어 2 100 24 99 25 24을 불러주고 3 6이라고 질문하면 3번째와 6번째 사이의 수 중 가장 큰 수인 99를 말해야 한다. 이번에는 없어서 못 파는 "파워레인저 다이노포스 티라노킹"이 걸려있다. 입력 첫 줄에 불러줄 숫자의 개수 n이 입력된다. ( 1 > a >> b; for(int j = 0; j = a && query[j].second
[코드업] 3736 - LIS (Large) LIS(Longest Increasing subsequence)란 최장 증가 부분수열을 말한다. 프로그래밍 문제를 풀 다 보면 이것을 응용하는 문제가 많이 출제되고 있고, 동적계획법의 대표적인 사용 예 중 하나이다. 다음과 같은 원소의 개수가 8개(N)인 수열이 있을 때, 1 3 2 9 7 8 5 10 LIS = 1 2 7 8 10 으로 그 길이는 5이다. 이번에는 데이터의 크기가 크므로 O(n^2)알고리즘으로는 해결할 수 없을 것이다. 입력 첫째줄에 수열의 원소개수 N이 입력된다.( 1 N; vec.push_back(-987654321); int ret = 0; int num; for(int i = 0; i > num; if(vec.back() < num){ vec.push..

티스토리툴바