알고리즘 문제 풀이/Softeer

조건을 만족하는 (i, j, k)를 찾기 위해 3중 loop를 돌린다면 O(n3)의 시간복잡도를 가지므로 시간 제한을 초과할 것이다. 따라서 DP를 이용해 (i < j, ai < aj)를 만족하는 i, j와 (i < k, ai < ak)를 만족하는 i, k를 따로 구하여 O(n2) 시간복잡도로 문제를 해결할 수 있다. [ 풀이 방법 ] 1. i를 선택하고, i < j와 ai < aj를 모두 만족하는 j의 개수를 구하는 기능 - loop를 돌며 dp[i][j]에 ai보다 큰 aj의 개수 저장 2. i를 선택하고 i < k와 ai < ak를 모두 만족하는 k를 구하여 결과를 구하는 기능 - loop를 돌며 ai와 ak를 비교하고 ak가 더 작다면 res에 dp[i][k-1](i와 k사이의 모든 조건을 만족..

성능이 가장 낮은 컴퓨터의 성능이 가질 수 있는 최대값 즉, 최적해를 구하는 문제이다. 따라서 decision problem의 형태를 가지며 이진 탐색을 사용해 풀 수 있다. [ 풀이 방법 ]  이진 탐색을 이용하여 성능이 가장 낮은 컴퓨터의 성능이 mid가 되도록 하는데 드는 비용의 합이 B보다 작은 경우 중 가장 큰 mid값을 찾는다. 이 때, B원의 값이 이미 매우 크므로 비용의 합을 구할 때, 비용의 합이 B보다 커지면 비용의 합을 구하는 프로세스가 바로 종료되도록 구현해야 한다.  [ 회고 ] 이진 탐색, 특히 decision problem에 대한 이해가 부족하여 풀이 방법과 구현 방법 생각이 어려웠다. 또한 B가 큰 값임을 알고 있었으나 자료형의 범위에 대한 생각없이, 아무리 큰 값이어도 lo..

[ 풀이 방법 ] 교차로의 각 위치에 들어온 차들을 저장할 queue와, 차가 들어온 교차로 위치를 저장하는 배열, 차가 들어온 시간을 저장하는 배열, 차가 교차로를 통과한 시간을 저장하는 배열을 차가 들어온 순서대로 생성하고 탐색하여 구현 1. 교차로가 모두 빈 경우 - 아직 탐색되지 않은 첫 번째 차의 도착 시간을 현재 시간으로 초기화한다. - 현재 시간에 도착한 차들을 모두 교차로의 올바른 위치에 삽입한다. - 오른쪽 교차로가 빈 교차로에 들어온 차들을 교차로 큐에서 빼준 뒤 교차로를 통과한 시간을 저장하는 배열에 현재 시간을 저장한다. 2. 교차로 중 일부가 빈 경우 - 현재 시간을 1초 늘린다. - 현재 시간에 도착한 차들을 모두 교차로의 올바른 위치에 삽입한다. - 오른쪽 교차로가 빈 교차로에..

[ 풀이 방법 ] 1. 5x5 크기의 표를 생성하는 기능 - 주어진 키의 알파벳을 순서대로 표에 넣는다. - 이 때, 이미 표에 들어간 알파벳은 다시 표에 넣지 않는다. - 키의 중복되지 않는 알파벳을 모두 표에 넣은 뒤, 표에 담기지 않은 알파벳을 순서대로 표에 넣는다. - 알파벳을 순서대로 저장하는 배열과, 표에 이미 넣은 알파벳을 체크할 map, 표에 저장된 알파벳의 좌표를 저장할 map을 이용해 구현 2. 메시지를 두 글자로 나누는 기능 - 메시지를 순서대로 두 글자씩 순회하며 vector에 저장 - 두 글자가 같지 않다면 pair를 이용해 두 글자를 저장 - 두 글자가 같다면 첫 번째 글자와 'X'를 pair를 이용해 저장하고, 두 번째 글자부터 남은 메시지를 순회 - 두 글자가 같고 'X'라면..

참가자 N명의 점수를 내림차순으로 정렬하고, 각 참가자의 등수를 가능한 작게 부여하여 출력해야 하고, N의 크기가 최대 100000이므로 최대 n log n의 시간복잡도를 갖는 알고리즘으로 구현해야 한다. [ 풀이 방법 ] 각 참가자의 등수를 가능한 작게 부여하는 기능은 점수를 내림차순으로 정렬한 배열에서 참가자의 점수보다 같거나 작은 점수가 처음으로 등장한 인덱스를 찾는 것과 같다. 처음엔 STL의 lower_bound()를 사용하여 구현하려 하였으나, 특정 원소보다 크거나 같은 원소의 첫 인덱스를 찾는 함수이기 때문에 오름차순으로 정렬된 컨테이너에서만 올바르게 작동하여 이 문제에서는 사용할 수 없었다. 따라서 이분탐색을 이용해 내림차순으로 정렬된 컨테이너에서 특정 원소보다 작거나 같은 원소의 첫 인..

시간 제한, 메모리 제한이 주어지는 H, K, R의 크기에 비해 널널해서 트리와 큐를 이용해 문제의 요구사항을 정확하게 구현하면 풀 수 있는 문제라고 생각했다. [ 풀이 방법 ] 1. 이진 트리 생성 기능 - 완전이진트리를 만들어야 하므로 크기가 2H+1, root의 index가 1인 배열을 생성해 트리를 생성한다. - leaf 노드는 큐 1개, 다른 노드는 큐 2개를 이용해 맡은 업무를 저장한다. - pair를 이용해 구현. - leaf 노드의 경우 first 큐만 사용하고 다른 노드의 경우 홀수 번째 날짜에는 first 큐, 짝수 번째 날짜인 경우 second 큐를 사용한다. vector tree; tree.resize(pow(2, H+1)); int leafIdx = pow(2, H); 2. 업무 ..

출근길에 들른 동네를 퇴근길에 다시 지날 수 있는 경우는, S에서 T로 가는 경로와 T에서 S로 가는 경로 모두에 포함되는 경우이다. 따라서 S에서 T로 가는 경로와, T에서 S로 가는 경로를 모두 탐색하여 두 경로에 모두 속한 정점의 개수를 찾으면 된다. [ 풀이 방법 ] 1. DFS를 이용해 S -> T, T -> S로의 경로를 탐색 - DFS의 반환값을 이용해 목적지에 도달 가능한지(경로에 포함되는지)를 체크 - 목적지에 도달하지 못하고 DFS가 종료된다면 false를 return - 목적지에 도달한다면 true를 반환하고 DFS를 종료 - true가 반환된 경로에 존재하는 정점들만 체크 2. S -> T, T -> S 경로 탐색에서 모두체크된 정점의 개수를 출력 그러나 이렇게 구현할 경우 각 정점..

3개의 수를 골라 중앙값이 m이 되도록 하는 경우는 m을 고르고 m보다 작은 수 하나, m보다 큰 수 하나를 고르는 경우와 같다. 따라서 m이 주어졌을 때, (m보다 작은 수 중 하나를 고르는 경우의 수) x (m보다 큰 수 중 하나를 고르는 경우의 수)를 출력하면 된다. 이 때, m보다 작은 수(or 큰 수) 중 하나를 고르는 경우의 수는 m보다 작은 수(or 큰 수)의 개수를 k라고 했을 때 kC1 = k와 같다. 따라서 (m보다 작은 수의 개수) x (m보다 큰 수의 개수)를 출력하여 문제를 해결할 수 있다. 최대 200000번 반복해야하기 때문에 m보다 작은 수와 큰 수의 개수를 구하는 알고리즘은 O(log n)의 시간복잡도를 가져야 한다. [ 풀이 방법 ] 1. 자동차의 연비 n개를 정렬한다. ..