알고리즘

# 위상 정렬이란? 순서가 정해져 있는 작업들을 차례대로 수행해야 할 때, 그 순서를 결정해주는 알고리즘 선후 관계가 정의된 그래프 위상 정렬이 성립하기 위해서는 방향 비순환 그래프이어야 한다. # 흐름 0. 모든 정점의 진입 차수를 계산한다. 진입 차수(in-degree) : 자신으로 들어오는 간선의 수 1. 진입 차수가 0인 정점을 모두 큐에 넣는다. 진입 차수가 0인 정점 = 시작점 위 경우에서는 A, E가 큐에 들어가게 된다. 2. 큐에서 정점을 꺼내어 해당 정점과 인접한 정점의 간선을 제거하고 인접한 정점의 진입 차수를 1 감소시킨다. 인접한 정점의 진입 차수가 1 감소 이후 0이 된다면 인접한 정점을 큐에 넣어준다. 큐가 빈 상태가 될 때까지 반복한다. # 관련 문제 (2252 - 줄 세우기 ..

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를 만드는..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 의식의 흐름 dp 문제네 -> 0원~n원까지 가능한 경우의 수를 다 저장하면 되겠다. -> 풀고 나니 1,000,000,007로 나눈 나머지라는 조건을 까먹고 그냥 원래 값을 return했는데 통과네..? -> 1,000,000,0007로 나누는 코드 추가해서 제출했는데 시간 초과 🙄 -> 코드 살짝 수정하고 통과 문제 자체는 어렵지 않았는데 이 문제 덕분에 내가 쓰던 로직을 살짝 수정해서 좀 더 빠른 로직으로 수정할 수 있었다 풀이 과정 1. i번째 동전까지 사용해서 j원 만들 수 있는 경우의 수를 담을 배..

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