분류 전체보기

16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 의식의 흐름 돌려야하는 줄이 몇 개인지 구하고 하나씩 반시계로 돌려보자 풀이 과정 1. 배열의 크기(N, M), 회전의 수(rotCnt)를 입력받는다. 2. 배열(nums)의 원소를 입력받는다. 3. 각각의 줄을 반시계방향으로 돌린다. 3-1) 돌려야하는 줄의 개수 = Math.min(N,M)/2 문제 조건 => min(N, M) mod 2 = 0 N=4, M=4인 경우..

22945번: 팀 빌딩 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다. (개 www.acmicpc.net 의식의 흐름 양 끝 개발자를 투 포인터가 가리키게 하면 될 것 같은데... 포인터 이동하는 조건을 어떻게 둬야하지..? (결국 풀이 참고함) start와 end를 양 끝에서 시작해서 점차 가까워지도록 하면 되는거였는데 두 포인터를 앞에 두고 시작하는 방법만 생각했댱,,, 풀이 과정 1. 개발자 수(N)를 입력받는다. 2. N개의 개발자 능력치를 배열(ability)에 담아둔다. 3. 포인터를 이동하면서 최대 능력치(maxAbility)를 갱신한다. 3-1..

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를 감소시키..

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