![]()
문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다. x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다. 다음은 6 x 6 크기 행렬의 예시입니다. 이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은..
![]()
문제 설명 개발자를 희망하는 조르디가 카카오에 면접을 보러 왔습니다. 코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야 하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다. 대기실은 5개이며, 각 대기실은 5x5 크기입니다. 거리두기를 위하여 응시자들 끼리는 맨해튼 거리 1가 2 이하로 앉지 말아 주세요. 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다. 예를 들어, 5개의 대기실을 본 조르디는 각 대기실에서 응시자들이 거리두기를 잘 지키고 있는지 알고 싶어 졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실 별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실 별로 거리두..
![]()
문제 교재와 강의자료를 참고하여 0-1 배낭 문제를 해결하는 Algorithm 5.7을 완성하시오. 단, 문제의 입력은 단위무게당 이익순으로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘의 출력은 알고리즘의 실행 단계별로 상태 공간 트리의 각 노드에서의 상태를 출력해야 함에 주의하시오. 입력 첫번째 줄에 아이템의 개수 n과 배낭의 무게 W가 주어진다. 두 번째 줄에 n개의 아이템 무게 w [i]가 주어진다. 세 번째 줄에 n개의 아이템 이익 p [i]가 주어진다. 출력 첫 번째 줄부터 한 줄에 하나씩 상태공간트리를 방문하는 노드의 상태를 출력하시오. 노드 상태는 다음과 같은 순서로 출력한다. i weight profit bound maxprofit 상태를 출력하는 순서는 Algorithm 5.7의 노..
![]()
문제 교재의 내용과 강의자료를 참고하여 0-1 배낭 문제를 해결하는 알고리즘의 구현을 완성하시오. 강의자료에서 knapsack2() 또는 knapsack3()를 참조할 것. 단, 입력값은 단위 무게당 이익의 순서로 정렬되어 있지 않음에 유의하시오. 또한, 알고리즘 실행 결과의 출력은 알고리즘의 실행 과정에서 결과 테이블 P에 저장한 무게(i) 또는 이익(j)이 0이 아닌 모든 항목 P[i][j]를 (i, j)의 오름차순으로 모두 출력한다는 것에 주의하시오. 입력 첫 번째 줄에 아이템의 개수 n이 주어진다. 두 번째 줄에 n개의 무게 w[i]가 주어진다. 세 번째 줄에 n개의 이익 p[i]가 주어진다. 네 번째 줄에 배낭 무게의 개수 T가 주어진다. 이후로 T개의 줄에 한 줄에 하나씩 배낭 무게 W가 주어..
![]()
문제 설명 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다. 124 나라에는 자연수만 존재합니다. 124 나라에는 모든 수를 표현할 때 1, 2, 4만 사용합니다. 예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다. 자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution함수를 완성해주세요. 제한사항 n은 500,000,000이하의 자연수입니다. 1 1 11 42 2 2 12 44 3 4 13 111 4 11 14 112 5 12 15 114 6 14 16 121 7 21 17 122 8 22 18 124 9 24 19 141 10 41 20 142 1~20까지 입출..
![]()
문제 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다. "[닉네임]님이 들어왔습니다." 채팅방에서 누군가 나가면 다음 메시지가 출력된다. "[닉네임]님이 나갔습니다." 채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다. 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다. 채팅방에서 닉네임을 변경한다. 닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다. 예를 들어, 채팅방에 "..
![]()
문제 주어진 무방향 무가 중치 그래프 G = (V, E)에서 해밀턴 회로의 개수를 출력하시오. Algorithm 5.6을 구현할 때, 출발 정점은 1로 간주한다는 것을 주의하시오. 입력 첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어진다. 둘째 줄부터 m개의 간선이 주어진다. 출력 첫째 줄에 해밀턴 회로의 개수를 출력한다. 문제 해석 이 문제를 풀기 위해서는 해밀턴 회로와 해밀턴 경로의 차이를 알아야 한다. 해밀턴 회로 VS 해밀턴 경로 해밀턴 회로 한 정점에서 출발을 해 모든 정점을 딱 한 번씩 방문하고 다시 출발 정점으로 돌아와야 한다. 출발 정점과 해밀턴 회로는 무관하다. 해밀턴 경로 해밀턴 경로는 해밀턴 회로와 다르게 출발 정점에 따라 값이 다르다. 한 정점에서 출발해서 모든 정점을 한 번씩 ..
![]()
문제 주어진 평면 그래프 G = (V, E)에 대해서 인접한 지역을 서로 다른 색으로 색칠하기 위해 필요한 최소 색의 수 m의 값과 해당하는 m의 값으로 색칠할 수 있는 경우의 수를 출력하시오. 단, 그래프의 입력은 간선의 집합으로 주어지고, 주어진 그래프는 평면 그래프라고 가정해도 된다. 입력 첫 줄에 정점의 수 n과 간선의 수 k가 주어진다. 둘째 줄부터 k개의 간선이 주어진다. 출력 첫째 줄에 색칠 가능한 최소의 m값을 출력한다. 둘째 줄에 해당 m값으로 색칠할 수 있는 경우의 수를 출력한다. 문제 해석 그림과 같이 인접해 있는 영역끼리는 서로 다른 색을 칠해야 한다. 여기서 인접한다의 의미는 영역들끼리 가로 세로중 하나라도 맞닿아있어야 한다. v1과 v3, v2는 가로 세로 중 한 영역이 맞닿아있..
![]()
문제 n개의 원소를 가진 정수의 집합 S가 주어지고, 임의의 정수 W가 주어졌을 때, 합이 W가 되는 부분집합의 개수와 각 부분집합을 출력하도록 하시오. 입력 첫 줄에 원소의 개수 n과 임의의 정수 W가 주어진다. 둘째 줄에 n개의 정수가 주어진다. 출력 첫 줄에 원소의 합이 W가 되는 부분집합의 개수를 출력한다. 둘째 줄부터 원소의 합이 W가 되는 모든 부분집합을 한 줄에 하나씩 출력한다. 단, 부분집합에서의 원소 출력 순서는 주어진 S의 원소 순서와 동일해야 한다. (백트래킹 순서대로) ※처음 문제를 보고 떠오른 생각 주어진 집합 S의 원소들을 더해서 W를 만들어야 한다. Backtracking을 이용해서 모든 경우의 수를 구한다. 유망성검사를 통해서 가지치기를 함. 만약 뽑은 원소들의 합이 W면 종..
