MingyuPark

문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 아이디어 사람을 제거하는 문제이기 때문에 deque를 이용하면 쉽게 풀 수 있다. 사람을 제거하는 과정은 popleft()를 이용한다. 여기서 핵심은 원을 따라 이다. 이것을 구현하기 위해서는 deque의 rotate()를 이용한다. 1, 2, 3, ..., n 의 사람이 앉아있다고 하자. 1번으로부터 시작한다. 이 때 k번째 사람을 제거되는 것은 지금 위치 기준 (k-1)만큼 시계방향에 있는 사람이 제거된다는 의미와 같다. 즉 deque를 (k - 1)번 반시계 방향으로 돌..

LIS 알고리즘이란? Longest Increasing Subsequence의 줄임말로, 주어진 수열에서 오름차순으로 정렬할 수 있는 가장 긴 부분 수열을 찾는 문제이다. 수열의 길이가 n일 때 O(n logn)의 시간복잡도로 해결이 가능하다. 예를 들어보자. 주어진 리스트가 [1, 4, 5, 2, 3, 6, 7, 8, 5] 라고 하면, LIS는 [1, 2, 3, 6, 7, 8]이 된다. LIS 알고리즘을 구현하는 방법은 완전탐색, Dynamic Programming, Binary Search가 있다. 우선 DP에 대해서 알아본다. 다이나믹 프로그래밍 - O(N^2) 0번 인덱스만으로 부분 수열을 구성하는 경우는 길이가 1이다. 즉 최소 길이는 1이다. 그 뒤로는 이전 인덱스의 모든 값과 비교한다. 각 ..

문제 https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 아이디어 각각의 함수를 정의해준다. 최빈값의 경우가 조금 까다로웠다. 각각의 수에 대해 나타난 횟수를 딕셔너리로 정의했다. 각 숫자를 key, 나타난 횟수를 value로 정의했다. 각각의 key, value 조합에 대해서 value가 이때가지 나타난 value의 최댓값보다 큰 경우 해당 숫자가 최빈값이라고 할 수 있기 때문에 max_ 변수를 최빈값의 빈도로 업데이트하고 리스트를 초기화한다. 이 때 빈도가 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 간단한 완전탐색 문제다. 첫 번째로 노란색 격자와 갈색 격자와 개수를 통해 전체 카펫의 격자의 개수를 계산할 수 있다. 카펫은 직사각형이기 때문에 격자의 개수를 구하면 가능한 (가로, 세로) 조합의 크기를 계산할 수 있다. 첫 번째로 전체 격자의 개수에 대해 가능한 (가로, 세로) 조합의 크기를 계산하는 func 함수를 정의했다. 가로의 길이는 세로의 길이보다 같거나 크기 때문에 가..

문제 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 아이디어 주어진 N개의 자연수의 S번째부터 E번째까지의 수가 팰린드롬을 이루는지의 여부를 나타내는 2차원 배열을 이용한다. 즉, N×N의 배열을 초기화한 후, S번째부터 E번째까지의 수가 팰린드롬을 이루는 경우는 배열의 (S, E)번째 성분을 1로, 팰린드롬을 이루지 않는 경우는 0으로 둔다. 이 문제는 크게 3가지로 나눌 수 있다. - 주어진 숫자열의 길이가 1인 경우(즉, S = E인 경우) - 주어진 숫자열의 길이가 2인 경..

문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 아이디어 N킬로그램에서 필요한 봉지의 수를 f(N)이라고 하자. 이 경우 봉지를 하나 추가하는 경우는 3kg 봉지를 하나 추가하는 경우와 5kg 봉지를 하나 추가하는 경우 둘 중 하나이다. 즉, f(N) = f(N-3) + 1이거나 f(N) = f(N-5) + 1이 될 수 있다. f(N-3)과 f(N-5)의 대소관계를 비교해야 한다. 봉지 수가 가장 적은 경우를 구해야 하기 때문에 f(N-3)과 f(N..