알고리즘/백준

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

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