알고리즘

20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 의식의 흐름 투 포인터로 앞뒤 이동하면서 최대 길이 구하면 되겠징,, > 투 포인터의 시간 복잡도 = O(N) 풀이 과정 1. 수열의 길이(N), 같은 숫자의 최대 개수(K)를 입력받는다. 2. N개의 숫자를 배열(nums)에 담아둔다. 3. 만약 `N != 1`인 경우, 최장 연속 부분 수열의 길이(maxLength)를 구한다. -> `findMaxLength()` 3-1) start, end 포인터를 둔다. 3-2) 포인터 사이 숫자들에 대해 K개를 넘는..

14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 의식의 흐름 선수 과목에 대한 Arraylist 배열(subjects)을 만들고 개수를 세면 되지 않나,, 이후에 'A < B인 입력만 주어진다'는 조건을 제대로 안보고 시작 과목을 어떻게 정하지?하고 엄청 헤맸다👻 풀이 과정 1. 과목의 수(N), 선수 조건의 수(M)를 입력 받는다. 2. 어떤 과목의 선수 과목인지 담을 배열(subjects)과 선수과목 수를 담을 배열(dp)를 생성한다. - subjects : ArrayList[] - dp : int[] 3. subjects를 채우고 ..

2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 의식의 흐름 이전에 풀었던 가장 긴 증가하는 수열(https://monicajo074.tistory.com/44)을 사용하면 될 것 같은뎅..? 일단 가장 긴 증가하는 수열을 구한 다음에 해당 수열 안에 들어가지 못한 아이들만 옮기면 그게 최소인 경우일 것 같다. 풀이 과정 1. 아이들의 수(N)을 입력 받는다. 2. 현재 서있는 순서를 배열(nums)에 담고 증가하는 수열의 길이를 담을 배열(dp)를 1로 초기화한다. for(int i=0;i 자세한 풀이는 2023...

9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 의식의 흐름 dfs로 풀면 되지않나..? > 시간 초과 0~M까지 만들 수 있는 경우의 수를 담아놓자 > 성공 풀이 과정 1. 테스트케이스의 수(T)를 입력 받는다. 2. 동전의 가지 수(N)를 입력 받는다. 3. N가지 동전의 금액을 배열(coins)에 담는다. 4. 만들어야 할 금액(M)을 입력 받는다. 5. 각 합을 만들 수 있는 경우의 수를 담을 배열(dp)을 생성한다. - dp[j] = 동전의 합이 j인 경우의 수 - dp[0] = 1로..

9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 의식의 흐름 이차원 배열 만들어서 하나씩 비교하면서 가능한 수를 저장하면 될 것 같은데...? (글자 수 = 최대 1000개 => 1000*1000 => 시간 가능) 풀이 과정 1. 첫째불과 둘째줄에 입력 받은 문자열을 각각 배열(input1, input2)에 저장한다. -> 지금 생각해보니 문자열을 굳이 배열에 저장안하고 나중에 .charAt() 써도 됐을듯하다. 2. input1[j]와 input2[i]를 비교하여..

15724번: 주지수 네모 왕국의 왕인 진경대왕은 왕국의 영토를 편하게 통치하기 위해서 1X1의 단위 구역을 여러 개 묶어서 하나의 거대 행정구역인 주지수(州地數, 마을의 땅을 셈)를 만들 예정이다. 진경대왕은 www.acmicpc.net > 의식의 흐름 예전에 풀어봤던 사각형 내 합 구하는 문제랑 비슷하다. (1 1 i j) 구역 내 사람 수를 dp에 담아두고 그때그때 원하는 구간의 사람 수 합을 다시 구하면 될 것 같다. > 풀이 과정 1. 영토의 세로(N), 가로(M)의 크기를 입력 받는다. 2. 단위 구역 내 살고 있는 사람의 수를 배열(population)에 담는다. 3. (1 1 i j) 구역 내 살고 있는 사람의 수를 배열(dp)에 담는다. dp = new int[N+1][M+1]; // d..

1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net > 의식의 흐름 bfs로 풀면 될 것 같은데..? => 계속 틀렸습니다 뜸 => 알고 보니 다음 위치를 어디로 할 것인지 순서에 따라 정답/오답이 나왔다,, (자세한 건 풀이에) > 풀이 과정 1. 수빈이의 위치(N), 동생의 위치(K)를 입력 받는다. 2. 만약 수빈이와 동생이 같은 위치라면 0초만에 동생을 찾을 수 있기 때문에 두 명의 위치가 다른 경우에만 bfs를 수행한다. 3. 수빈이의 처음 위치를 덱에 넣기 4. while문 ..

15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net > 의식의 흐름 dfs로 풀면되려나..? > 실패 반복문 사용해서 i번째 날까지의 최대 수익을 구하자 > 성공 > 풀이 과정 1. 퇴사까지 남은 일수(N)를 입력 받는다. 2. Consulting 클래스에 상담에 대한 정보를 담아 배열(consultings)에 담는다. - Consulting 클래스에 date(필요한 일수), cost(받을 수 있는 돈)을 담는다. 3. i일까지의 최대 수익을 이용하여 i일의 상담을 끝내고 얼마 받을 ..

11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net > 의식의 흐름 이전에 풀었던 가장 긴 증가하는 부분 수열(https://monicajo074.tistory.com/44)이랑 완전 같은 문제네 > 풀이 과정 1. 수열의 크기(N)을 입력 받는다. 2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(sum)을 nums[i]로 초기화한다. 3. nums[i]와 뒤쪽 수(nums[j])를 비교한다 - 만약 nums[i] < nums[j]인 ..