투투

문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) 출력 예제와 같이 요세푸스 순열을 출력한다. 접근 1번부터 N번까지 큐에 넣고 큐가 빌 때까지 다음을 반복한..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 출력 첫째 줄에 입력으로 주어진 M..

www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 접근 처음에는 단순하게 리스트에 N개의 수를 넣고 또 다른 리스트에 M개의 수를 넣어 for문으로 탐색하면서 in연산을 사용하였다. 하지만 리스트를 탐색하는 것은 O(N)의 시간복잡도가 발생하여 시간초과가 발생하였다. 이를 set이나 dict 자료형을 사용하면 O(1)의 시간복잡도를 갖기 때문에 효율적이라는 것을 알게되었다. 구현 N개의 수를 set 자료형으로 입..

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 접근 다른 사람들의 풀이를 참고하였다. 현재까지 이해한 것은 각각의 money로 만들 수 있는 1부터 n까지의 수를 누적해서 계산해나간다. 1은 1부터 n까지의 돈을 만드는 경우의 수가 1개이다. 2는 1을 만들 수없기 때문에 이전의 1에서 1을 만드는 경우의 수에서 가져온다. 그리고 2로 2를 만들 수 있는 경우의 수는 1+1과 2이다. 즉 1로 만든 수와 자기..

programmers.co.kr/learn/courses/30/lessons/42860 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 접근 최소한의 조작으로 입력된 문자열로 변경해야한다. 조작은 문자열 변경을 위해 위, 아래로의 조작과 바꿀 문자열의 위치로 이동하는 왼쪽, 오른쪽의 조작이 있다. 이를 최소로 하기위해서는 바꿔야하는 문자에서 A와 Z까지의 거리 중 최소를 구하고 현재 위치에서 왼쪽과 오른쪽으로 갈 때의 최소를 구하도록 한다. 구현 - 먼저 changed_name에 위, 아래..

문제 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고, 활성 상태인 바이러스는 상하좌우로 인접한 모든 빈 칸으로 동시에 복제된다. 연구소의 바이러스 M개를 활성 상태로 변경하려고 한다. 연구소의 크기는 NxN이며 빈 칸, 벽, 바이러스로 이루어져 있다. 활성 바이러스가 비활성 바이러스가 있는 칸으로 가면 활성화된다. (0은 빈 칸, 1은 벽, 2는 바이러스) M개의 바이러스를 선택하여 모든 빈 칸에 바이러스를 퍼뜨리는 최소 시간을 구한다. 입력 첫째 줄에 N(4이상 50이하)과 바이러스 개수 M(1이상 10이하)를 입력한다. 이어서 NxN의 연구소 맵을 입력한다. 출력 모든 빈 칸이 바이러스가 되는 최소시간을 구하고 바이러스를 퍼뜨릴 수 없다면 -1을 출력한다. ..

문제 NxM의 맵에서 1은 벽이기 때문에 이동할 수 없고 0은 이동할 수 있다. (1, 1)에서 출발하여 (N, M)까지 이동을 할 때 최소로 이동하는 거리를 구한다. 이때 벽으로인해 이동할 수 없다면 최대 한 번은 벽을 부수고 이동할 수 없다. 벽을 부수고 이동했을 때도 도착지에 가지 못한다면 -1을 출력한다. 입력 첫째 줄에 1이상 1000이하의 N과 M을 입력한다. 출력 첫째 줄에 최소거리를 출력한다. 접근 처음에는 맵을 탐색하다가 벽이 보였을 때 벽을 제거하고 BFS를 하도록 했지만 시간초과가 났다. 그래서 여러번 시도를 해보고 다른 사람들의 풀이를 참고하였다. BFS를 할 때 3차원 배열로 방문표시와 이동거리를 표시를 한다. 마지막 축은 크기가 2인데 0은 벽을 부수고 이동한거리, 1은 벽을 부..

문제 스타트링크에 다니는 사람들이 모여서 축구를 한다. 모인 사람은 항상 짝수인 N명이 모였으며 스타트팀과 링크팀으로 나누려고 한다. 이때 i와 j가 팀이 되었을 때 능력치가 있는데 N명이 두 팀으로 나눴을 때 각각 팀의 능력치를 구하여 두 팀의 능력치 차이가 최소가 되도록 구하라. 입력 첫째 줄에 N이 주어진다. 둘째 줄부터 N개의 줄에 N개의 능력치가 주어진다. i번째 줄의 j번째 수는 i와 j가 팀이 되었을 때 능력치이다. 출력 스타트팀과 링크 팀의 능력치의 차이가 최소가 되는 값을 출력한다. 접근 먼저 두 개의 팀으로 나눴다. 스타트팀은 1, 링크팀은 0으로 표시를 한다. 이후 능력치를 조사하는데 2차원 배열을 탐색할 때 행과 열의 인덱스가 모두 1일 때는 스타트 능력치에 더하고 모두 0일 때는 ..

문제 N개의 수로 이루어진 수열이 있다. 수와 수 사이에 N-1개의 연산자를 끼워넣어 최댓값과 최솟값을 구하라 사용할 수 있는 연산자의 수는 주어진다. 입력 첫째 줄에 수의 개수 N(2이상 11이하)이 주어진다. 둘째 줄에 N개의 수가 주어지며 셋째 줄에 + - x / 순으로 개수가 주어진다. 출력 첫째 줄에 최댓값 둘째 줄에 최솟값 접근 수열에서 앞의 숫자를 시작으로 그 다음 수와 연산을 진행한다. 연산자는 사용할 수 있는 개수가 정해져있기 때문에 연산자의 수가 담긴 리스트를 탐색하여 연산자가 남아있다면 그에 해당하는 연산을하도록 한다. 구현 필요한 정보를 입력받으며 최댓값과 최솟값 비교를 위한 수를 설정한다. 중간 결과를 포함한 모든 결과가 -10억 이상 10억 이하이기 때문에 아래와 같이 설정해주었..

www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 접근 뒤에서부터 접근하고자 했다. 아직까지 DP의 개념을 완벽하게 이해하고있지 않아 뒤에서부터 어떻게 메모이제이션을 진행할지 감이 잡히지 않았다. 그래서 다음과 같이 생각하기로 했다. 뒤에서부터 경우의 수에 따라 최댓값을 구하자. 즉 뒤에서부터 진행하면서 해당 날짜에 상담을 했을 때와 안했을 때의 수익 중 최댓값을 채워나간다. 이러한 개념으로 현재 날짜에 상담을 한다면 T일 후에있는 상담을 할 수 있기 때문에 두 개의 수익을 더하고 현재 날짜에 상담을 안한다면 다음 날 상담을 하게되므로 이 두 개의 경우의 수 중 최댓값을 채워나가도록 한다. 구현 ..