Kyle's Life Labs Kyle's Life Labs

OverviewProblem: https://www.acmicpc.net/problem/3273TimeComplexity: O(N)Type: 배열문제 파악구해야하는 값쌍의 개수입력1 1 1 요구사항입력으로 받은 수열 중에 두수의 합이 x가 되는 쌍의 개수를 출력한다. ai + aj = x (1 i와 J는 같은 값이 될 수 없음을 유의해야한다.문제분석모든 쌍을 다 검사하려면 O(N^2) = 10,000,000,000이 되므로 이 방법으로는 불가능하다.대신 x - a = b를 활용해서 a값은 고정해두고, b값이 이 수열에 있는지 확인만 하면된다.b값이 수열에 있는지 바로 알수만 있다면 이중루프에서 루프 하나를 제외시킬 수 있기 때문에 빠르게 해결할 수 있다.배열의 장점중 하나인 랜덤 액세스를 이용한다.a,b..

OverviewProblem: https://www.acmicpc.net/problem/10989TimeComplexity:Type: 정렬문제 파악구해야하는 값: 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.입력: 수의 개수 N(1 요구사항입력으로 받은 수를 정렬하여 출력한다.SolutionSolution1N개의 수가 10000이하의 자연수이기 때문에 10001개의 배열을 만들어서 넣고, 해당 배열에 담긴 수만큼 출력한다.이 풀이가 가능한 이유는 10000이하기 때문에 가능하다.1,000,000,000개였다면 4,000MB가 필요하기때문에 이 풀이는 불가능하다.fun main() { val br = BufferedReader(InputStreamReader(System.`in`)) va..

OverviewProblem: https://www.acmicpc.net/problem/10431TimeComplexity: O(T*n^2)Type: 삽입정렬문제 파악입력20개의 양의 정수구해야하는 값학생들이 뒤로 물러난 걸음 수의 총합요구사항입력으로부터 한명씩 뽑아서 줄의 맨 앞에 세운다.1. 자기앞에 자기보다 큰 학생이 있다면 그 학생 앞에 세운다.1-1. 그 뒤의 모든 학생들은 한발씩 물러선다.2. 자기보다 키가 큰 학생이 없다면 맨 뒤에 세운다.SolutionSolution1요구사항대로 구현한다.주의할 점은 아래와 같다.한발씩 뒤로 물러날때 맨 뒤부터 뒤로 물러나야 겹치지 않는다. 이중 루프에서 빠져나올때 외부루프의 나머지 로직(자기보다 키가 큰 학생이 없다면 맨 뒤에 서기)이 수행되지 않도록 하..

OverviewProblem: https://www.acmicpc.net/problem/10158TimeComplexity: O(n) 혹은 O(1)Type: 시간복잡도Git: https://github.com/kylelab/algorithms/blob/main/src/boj/BOJ10158.ktSolutionSolution1 (시간 초과)x축과 y축을 나눠서 생각해봤을때, x축은 w까지 이동하면 그 뒤에는 -1씩 이동하고 그 외에는 +1씩 이동한다.동일하게 y축은 h까지 이동하면 그 다음부터는 -1씩 이동하고 그 외에는 +1씩 이동한다.이 풀이는 시간 초과로 실패한다.그 이유는 시간 복잡도가 for문이 하나이기때문에 O(t)이 되는데 이 시간t의 범위가 1 ≤ t ≤ 200,000,000 으로 2초가 넘..

OverviewProblem: https://www.acmicpc.net/problem/1236TimeComplexity: O(nm) / 행열 탐색을 위한 이중 포문이 최대 시간 / n,m이 최대값이 50이므로 충분히 시간내 풀 수 있다.Type: 행열Git: https://github.com/kylelab/algorithms/blob/main/src/boj/BOJ1036.ktSolution경비원이 없는 행과 열의 갯수를 구한 후 그 중 최대값을 출력한다.모든 행에 한개씩 채우고, 나머지 열에 한개씩 채우는 것이 경비원의 최소값이므로, 행과 열중 큰 값이 정답이 된다. Solution1 이중 포문으로 각 행에 경비원이 포함되었는지 확인하고 총 행 수에서 경비원수를 뺀다.fun main() { val..