백준

22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 의식의 흐름 투 포인터를 사용해서 가장 긴 길이를 저장해두자 풀이 과정 1. 수열의 길이(N), 삭제할 수 있는 최대 횟수(K)를 입력받는다. 2. N개의 숫자를 배열(nums)에 담아둔다. 3. 삭제한 횟수(removedCnt)가 K 이하인 경우 최대 길이(maxLength)를 갱신한다. 3-1) start, end 포인터를 둔다. 3-2) removedCnt에 따라 start, end를 이동한다. removedCnt K인 경우, nums[start]의 값에 따라 removedCnt를 감소시키..

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]인 ..

11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net > 의식의 흐름 수열의 크기가 최대 1,000이니까 O(N^2) 가능하겠넹..? 그럼 전체 다 훑어봐야지~ > 풀이 과정 1. 수열의 크기(N)을 입력 받는다. 2. 수열을 배열(nums)에 입력받고 수열의 길이를 저장하는 배열(arrCnt)를 1로 초기화한다. 3. nums[i]와 뒤쪽 수(nums[j])를 비교한다 - 만약 nums[i] arrCnt[i]+1인 경우, 가장 긴 수열을..

2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net > 의식의 흐름 이전에 풀었던 행복 유치원이랑 비슷한 문제 같은데,, 센서 위치 정렬만 중간에 추가하면 될 것 같다. > 풀이 과정 1. 센서의 개수(N), 집중국의 개수(K)를 입력 받는다. 2. 센서의 위치를 배열(sensors)에 저장한다. 3. 센서의 위치를 오름차순으로 정렬한다. 행복 유치원에서는 학생의 키가 정렬된 순서로 주어졌기 때문에 따로 오름차순 정렬을 하지 않았다. 4. 옆 센서와의 거리를 배열(gap)에 저장한다. 5..

13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net > 의식의 흐름 dfs를 써서 모든 경우에 대해 비용을 구하고 그 중 최소를 뽑으면 되지 않을까? => 시간초과 옆 사람과의 키 차이가 얼마인지 구한 뒤에 차이가 큰 부분을 잘라서 조로 나눠버리면 될 것 같은데..? => 성공 > 풀이 과정 1. 원생의 수(N), 조의 개수(K)를 입력 받는다. 2. 모든 원생의 키를 배열(heights)에 저장한다. 3. 옆 원생과의 키 차이를 배열(gap)에 저장한다. 4. 배열 gap을 오름차순으로 정렬한 후 `N-K`..