문제 링크 2252번: 줄 세우기 풀이 위상 정렬 알고리즘을 알아야 풀 수 있는 문제. 모르겠어서 찾아봄 .. 알고리즘 자체는 간단하다. 사이클이 없는 방향 그래프에서 순서를 찾을 때 사용하는 듯하다. 해당 노드로 들어가는 간선이 없어야(다 해치워야) 그 노드를 방문할 수 있는 형태이다. 입력을 받으며 인접 리스트를 만들고 진입 차수 벡터도 만들어준다. 노드 1부터 n까지 확인하는데, 맨 첫번째 순서인 노드를 찾기 위해 진입차수가 0이고, 방문하지 않은 노드라면 위상 정렬을 실행한다. queue에 첫 번째 노드를 넣고, 방문 처리 뒤 queue가 빌 때까지 반복한다. q에서 나온 노드를 출력하고, 해당 노드 cur과 연결된 노드들을 cur과의 간선을 끊었을 때(진입차수를 줄이고), 진입차수가 0이 된다면..
문제 링크 1946번: 신입 사원 풀이 그리디 문제. n이 10^5라서 완탐으로 풀기엔 시간 초과가 남 a와 b를 입력 받으면서 a의 등수 인덱스에 b의 등수를 넣는다. 1등은 무조건 합격이기에, minNum을 1등의 b 점수로 넣고 2등부터 확인한다. minNum보다 arr[i]가 크다는 것은, 나보다 a 점수가 좋은 사람들이 b 점수도 좋다는 뜻이므로 제외한다. minNum은 계속해서 최솟값으로 갱신한다. 예제를 통해 arr를 만들면 이런 식이 될 것이다. a 등수 인덱스 1 (등) 2 3 4 5 6 7 arr (b 등수) 4 (등) 5 6 2 7 1 3 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0..
문제 링크 16234번: 인구 이동 풀이 DFS로 풀긴 했는데, BFS가 편했을 것 같다.. 값을 입력 받으며 벡터를 만든다. 인구 이동이 있어 다시 확인해야 하는지 체크하기 위한 변수 flag가 true라면 계속 인구 이동 시킨다. 첫번째는 인구 이동을 해야하는지 체크해야 하므로 do-while문을 쓴다. 벡터를 돌며 visited[i][j]가 0이면 탐색되지 않았다는 것이므로 dfs 함수로 탐색을 시작한다. dfs 함수에서는 상하좌우를 확인하며 gap이 범위 안에 있다면 재귀 호출을 한다. 영역 내의 총 합을 구하기 위한 sum과 영역 칸의 개수를 구하기 위한 cnt를 갱신한다. 영역 구분이 끝나면 arr의 값을 바꿔줘야 하므로 해당 위치 값을 갖는 unionArr에 추가한다. dfs를 돌고 한 영역..
문제 링크 1744번: 수 묶기 풀이 그리디 문제 아이디어는 양수는 양수끼리 절댓값이 큰 것끼리 묶고, 음수는 음수끼리 절댓값이 큰 것끼리 묶는다. 값을 입력받으며 양수이면 plus 벡터에 넣고, 음수면 minus 벡터에 넣는다. plus는 내림차순 정렬, minus는 오름차순 정렬한다. greedy함수를 통해 각 벡터의 최댓값을 구해 더해준다. 2번 과정을 통해 각 벡터는 절댓값이 큰 순서대로 내림차순 정렬 되어 있을텐데, 처음부터 묶어주거나 묶지 않거나를 선택해준다. 선택은 현재 숫자와 다음 숫자의 곱이 합보다 클 경우에 묶어준다. 묶어줄 경우 인덱스는 +2를 해줘야 중복해서 묶지 않게 된다. 묶지 않을 경우 인덱스를 +1 해줘서 그 다음 숫자와 묶일 수 있는지 확인하도록 한다. 그렇게 구한 양수와 ..
문제 링크 5052번: 전화번호 목록 풀이 문자열 문제. 처음에는 완탐으로 했는데 시간초과가 나길래.. 찾아보았다. 정렬하는 것까진 맞았는데, 정렬을 하게 되면 바로 뒤에꺼만 확인하면 된다. 하하 문자열을 입력받고 정렬한다. 현재 문자열을 기준으로 다음 문자열을 substr로 잘라서 같은지 확인한다. 같으면 NO, 전체 확인이 끝나도 flag가 true라면 YES를 출력한다. 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int i = 0; i > n; vector ..
문제 링크 1339번: 단어 수학 풀이 그리디를 사용하는 문제 처음엔 그냥 순서대로 점수 넣으려다 ACA BBD 같은 반례가 생각나서 우선순위? 느낌으로 변경함 문제를 입력받으며 가장 긴 문자열의 길이를 구해준다. maxLen 각 단어마다 알파벳의 우선순위를 구해주는데, ABC라는 단어가 있음면 A=100, B=10, C=1이 되게 구해준다. 그러면 각 알파벳마다 우선순위가 구해지는데, map으로 되어있기 때문에 vector로 바꿔주어 value기준 내림차순 정렬을 해준다. 우선순위가 높은 알파벳부터 9를 배정해주고 값을 하나씩 줄이며 숫자를 대응해준다. 다시 단어를 돌면서 대응한 숫자를 넣고 answer에 더해준다. 코드 #include #include #include #include #include ..
문제 링크 11057번: 오르막 수 풀이 DP로 푸는 문제 1자리 수일 때는 0~9까지 10개 2자리 수일 때는 00~09, 11~19 ~ 99해서 55개이다. 규칙은 n길이의 맨 첫번째 숫자가 만약 5라고 한다면 n-1길이의 숫자에서 55~99까지의 개수가 5로 시작하는 오르막 수의 개수일 것이다. 3 길이의 5로 시작하는 오르막 수를 구한다면, 555~559, 566~569, ..., 588~589, 599가 될 것이다. 해당 범위로 자른 이유는 n-1길이에서 55~59의 개수, 66~69의 개수 .. 를 구했을 것이기 때문이다. 점화식은 arr[n][i] = arr[n-1][i] + arr[n][j+1] (누적합으로 구해줄 것임) 코드 #include #include #define mod 10007..
문제 링크 9465번: 스티커 풀이 DP를 이용하는 문제 예시가 문제와 같이 다음 표라고 생각해보면 50 10 100 20 40 30 50 70 10 60 다음과 같이 생각할 수 있다. 50 10 + 30 100 + max(100, 30) = 200 20 + max(120, 100) = 140 40 + max(210, 120) = 250 30 50 + 50 70 + max(40, 50) = 120 10 + max(200, 40) = 210 60 + max(140, 200) = 260 정리하면, 해당 칸을 뜯는다고 가정할 때, 바로 대각선을 뜯을 것이냐 아니면 그 전 대각선을 뜯을 것이냐만 생각하면 된다. 점화식은 dp[0][j] = dp[0][j] + max(dp[1][j-1], dp[1][j-2]) 코..
문제 링크 11052번: 카드 구매하기 풀이 DP를 이용하는 문제 점화식을 구한다. n이 4라고 하면 4개짜리 하나 사는 경우와 `,2,3개짜리를 섞어서 사는 여러 경우가 있을 것이다. dp의 i번째 인덱스는 i개를 살 때 최댓값을 지불하는 경우가 저장되어 있을 텐데, 이를 이용해 1개짜리 사는 최댓값과 3개짜리 사는 최댓값을 더한 경우, 2개짜리 살 때 최댓값을 두 번 지불하는 경우, 그냥 4개짜리 사는 경우들에서 최댓값을 구해준다. 정리하면 점화식은, dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], dp[n](입력하면서 그냥 여기에 넣어줄거임))이 될 것이다. 점화식을 이용해 코드를 짜는데, 같은 경우를 두 번 계산하지 않기 위해..
문제 링크 배달 풀이 다익스트라로 푸는 문제인데 최소신장트리로 헷갈려서 약간 돌아갔다. 입력받은 road를 이용해 인접리스트를 만들어준다. 거리가 갱신될 dist는 최댓값으로 초기화해준다. 우선순위 큐로 최단 거리를 갱신해준다. 거리 순으로 정렬 되도록 pair를 {cost, end} 형태로 만들어준다. 그리고 오름차순 정렬한다. dist[next]>dist[cur]+nextCost라면 거리가 갱신된다는 것이므로 갱신해준 뒤 pq에 push한다. 그렇게 만들어진 dist를 돌면서 k보다 작거나 같다면 1 더해준다. 코드 #include #include #include #define INF 20000001 using namespace std; int solution(int N, vector road, in..
