날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42842.py at main · Junroot/Algorithm 풀이 일단 내가 푼 방법은 문제에서 의도한 방법은 아닌 것으로 보인다. brown + yellow = (가로) * (세로) yellow = ((가로) - 2) * ((세로) - 2) 라는 식을 적어 놓은 뒤 이차방적식으로 문제를 풀면 O(1)으로 문제 풀이가 가능하다. 문제 의도인 완전 탐색으로 문제를 풀어도, 위 두 개의 식을 이용할 수 있을 것으로 보인다. def solution(brown, yellow): sum = brown + yellow for h in range(1, brown + yellow + 1): if sum % h == 0: w = sum // h if yellow == (w - 2) * (h - 2): return [w, h]
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42840.py at main · Junroot/Algorithm 풀이 각 수포자의 점수 구하기 1등 수포자들 구하기 이렇게 2개의 소문제로 나눌 수 있다. 1번 문제는 약수를 이용하면 쉽게 점수를 구할 수 있다. 각 수포자들은 일정한 주기의 찍기 패턴을 가지고 있다. 1번 수포자는 주기가 5, 2번 수포자는 8, 3번 수포자는 10이다. (문제 번호) % (수포자의 패턴 주기)를 하면 수포자가 패턴의 몇 번째를 사용했는지 파악할 수 있게된다. 2번 문제는 먼저 최대 점수를 구하고 최대 점수에 해당하는 사람들을 전부 찾는 방식으로 구현했다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42839.py at main · Junroot/Algorithm 풀이 종이 조각으로 만들 수 있는 모든 수 구하기 만들어진 수 중에 가장 큰 수 이하의 모든 소수 구하기 소수 리스트에 만들어진 수가 포함된 것의 개수 구하기 이렇게 3가지 소문제로 나눴다. 이렇게 접근한 이유는 숫자마다 소수인지 검증하는 과정을 매번 계산하는 것이 비효율적이라고 생각했기 때문이다. 1번 문제의 경우 파이썬의 itertools라는 모듈에 permutations 함수를 사용해도되지만 이번에는 모든 순열을 구하는 함수를 직접 구해봤다....
날짜: 2022년 1월 31일 오후 5:51 코드 https://www.notion.so 풀이 복잡한 로직이 없어서 쉽게 풀 수 있다. 인덱스 i-1부터 j-1까지 리스트를 자른 다음 정렬하고, k-1번째 인덱스의 값을 찾으면 된다. 문제에서 i, j, k를 1번부터 세는 것에 유의해야된다.
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42747.py at main · Junroot/Algorithm 풀이 발표한 논문의 수가 1000편이하기 때문에, h=1000부터 하나씩 내려오면서 가능한지 확인해도 처리속도가 빠를 것이라고 생각이 들었다. 이 때, h값을 하나씩 줄이면서 전 단계에서 세었던 논문의 개수를 다시 셀 필요가 없을 것으로 보였다. citations를 역순으로 정렬한 뒤, h를 1씩 줄이고 h값을 만족하는 논문의 수가 h값 이상 인 경우에 그 h를 반환하도록 구현했다. 다른 사람의 풀이를 봤는데 너무 충격적이여서 여기에도 남겨본다....
날짜: 2022년 1월 31일 오후 5:51 코드 Algorithm/42746.py at main · Junroot/Algorithm 풀이 두 수 a,b가 있을 때, a*(10^len(b)) + a > b*(10^len(a)) + a이면 최대값은 항상 a가 b보다 먼저 온다는 것을 증명할 필요가 있다. 따라서, a와 b를 이어붙이고 뒤집어본 다음 더 큰 경우의 순서대로 수가 나열되면 가장 큰 값이 나온다는 뜻이다.
날짜: 2022년 8월 23일 오전 11:21 코드 Algorithm/17685.py at main · Junroot/Algorithm 풀이 단순하게 단어하나씩 입력을 늘려가면서 구하게되면 O(N*L)로 타임아웃이 발생할 것이다. 트라이를 이용해 중복되는 계산 부분을 제거하면 시간복잡도를 O(L)로 줄일 수 있다. 위 사진은 ‘go, gone, guild’를 트라이로 만들었을 때의 그림이다. 오른쪽 상단은 존재할 수 있는 단어 개수, 오른쪽 하단은 해당 글자로 끝나는 단어가 있는지 여부를 나타내는 true, false를 나타낸다. 최종 답을 찾을 때는 오른쪽 상단이 1이거나, 현재 글자로 끝이나는 단어의 depth를 모두 더해주면된다....
날짜: 2022년 7월 12일 오후 7:08 코드 Algorithm/17682.py at main · Junroot/Algorithm 풀이 단순 구현문제다. 파싱을 한뒤 문제조건에 맞게 구현하면된다.
날짜: 2022년 7월 12일 오후 8:01 코드 Algorithm/17681.py at main · Junroot/Algorithm 풀이 간단한 구현문제다.
날짜: 2022년 7월 8일 오후 6:43 코드 Algorithm/17679.py at main · Junroot/Algorithm 풀이 단순 구현 문제다. 더 이상 제거되는 블록이 없을 때까지 반복하면 된다.
날짜: 2022년 7월 6일 오전 10:34 코드 Algorithm/17678.py at main · Junroot/Algorithm 풀이 크루들이 타게되는 버스를 모두 차례대로 계산한 뒤에, 콘이 마지막 버스를 타기위해 언제 나오면 되는지를 계산하면된다. 마지막 버스가 만원인 경우 마지막 버스에 마지막에 타는 크루보다 1분 빨리 도착하면 된다. 마지막 버스가 만원이 아닐 경우 마지막 버스의 도착시간에 맞춰서 도착하면 된다.
날짜: 2022년 3월 8일 오후 3:41 코드 Algorithm/17676.py at main · Junroot/Algorithm 풀이 2가지 문제를 해결해야 됐다. 로그를 기반으로 처리시각의 시작 시각과 끝 시각 구하기 초당 최대 처리량 구하기 처리시각 구하기 ms 단위로 처리해야되기 때문에 2016-09-15에서 몇 ms가 지났는지를 기준으로 처리하기로 했다. 로그의 마지막 부분인 처리시간 T를 ms단위로 변환하는 것에 어려움이 있었는데, 로그에 적혀있는 숫자 개수를 기반으로 처리했다. 숫자의 개수가 0이 될 때까지 뒤에 0을 더 붙이는 형식으로 구현했다. def second_to_ms(second): result = 0 digit_count = 0 for c in second: if "0" <= c <= "9": result = result * 10 + int(c) digit_count += 1 while digit_count < 4: result *= 10 digit_count += 1 return result 초당 최대 처리량 구하기 처음에는 0ms부터 24 * 60 * 60 * 1000ms 까지 모든 경우를 다 구하려고했는데 이 방법은 당연히 시간 초과가 발생했다....