알고리즘/백준

6137번: 문자열 생성 첫 번째 줄에 문자열 S의 길이 N이 주어진다. (N 실패 : 한 번만 옆을 비교하는 경우 양 끝이 여러번 같은 경우 이상하게 나옴 (ex. CCACFBCC) => 그럼 다른 글자가 나올 때까지 양 끝을 비교하면 되겠네? => 실패 실패 실패 실패 ... => ?????????? (결국 포기) => 하루 지나서 문득 생각난 오류 = 전체 문자열에 대해서 돌리고 80번째에서 새 줄로 변경한 것이 아니라 80개씩 잘라서 양끝 비교하고 출력함... => 수정 => 통과 아,, 즐겁당^^ 풀이 과정 1. 문자열 S의 길이(N)을 입력 받는다. 2. 입력받은 문자를 char[] S에 저장한다. 3. 투 포인터를 이용하여 배열 S의 양 끝 문자를 비교한다. 만약 S[start] < S[en..

15787번: 기차가 어둠을 헤치고 은하수를 입력의 첫째 줄에 기차의 수 N(1 ≤ N ≤ 100000)과 명령의 수 M(1 ≤ M ≤ 100000)가 주어진다. 이후 두 번째 줄부터 M+1번째 줄까지 각 줄에 명령이 주어진다. www.acmicpc.net 의식의 흐름 일단 2차원 배열에 넣고 1,2,3,4에 따라서 나눠주고 중복되는지 확인하고..? 근데 중복을 하나하나 다 확인해야하나..? (헤매다가) HashSet 쓰면 되겠댱 풀이 과정 1. 기차의 수(N), 명령의 수(M)을 입력받는다. 2. 명령의 종류에 따라 배열(seats)에 사람 유무를 나타낸다. 타있는 경우 => seats[i][x] = true, 타고있지 않은 경우 => seats[i][x] = false; 1 i x : seat[i][..

17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 의식의 흐름 dp로 1~n까지 만드는데 필요한 최소 개수 구해보자. + 종이에 1~12까지 구할 수 있는 최소 경우의 수를 써보는데 12 = 3^2+1^2+1^2+1^2(4개) / 2^2+2^2+2^2(3개)로 나뉘는 것을 확인하고 무조건 최대 제곱수를 쓰면 틀리겠구나 생각함 풀이 과정 1. 자연수(n)을 입력받는다. 2. 1~n까지 만드는데 필요한 제곱수의 최소 개수를 구하여 배열(dp)에 저장한다. dp[i] = i를 만드는..

21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 의식의 흐름 빡구현,... 풀이 과정 1. 교실 크기(N)를 입력받는다. 2. 각 학생의 자리를 찾는다. 2-1) 학생 번호(studentNum), 좋아하는 학생들의 번호(favorites[studentNum])을 입력받는다. 2-2) 학생들의 자리를 지정한 배열(seat)을 이용하여 각 자리 정보(Seat)를 ArrayList(possibleSeats)에 저장한다. 자리 정보(Seat)는 'x좌표, y좌표, 근처 빈자리 개수, 근처 좋아하는 학생 수'..

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를 채우고 ..