목록전체 글 (139)

jae_coding

(백준 알고리즘 문제풀이) 12015번 가장 긴 증가하는 부분 수열 2

문제 문제 링크 문제 접근 백준 11055번 과 다른 점은 N의 range이다. 이점을 잘 생각해야 한다. 1,000 -> 1,000,000 시간복잡도 O(N logN)인 binary search를 사용해야 한다. 코드 시간 초과 코드 (시간 복잡도: O(N^2)) import sys N = int(sys.stdin.readline()) seq = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if seq[i] > seq[j]: dp[i] = max(dp[i], dp[j] + 1) print(dp) 통과 코드 ( 시간복잡도: O(NlogN) import sys N = int(sys..
알고리즘 문제/백준 2022. 7. 7. 16:00
(백준 알고리즘 문제풀이) 1676번 팩토리얼 0의 개수

문제 문제 링크 문제 접근 case1: N이 0 또는 1인경우는 0! 또는 1!이므로 1을 출력한다. case2: N 팩토리얼의 수를 구한 후 string타입으로 변경 후 마지막 문자부터 첫번째 문자 순서대로 "0" 인경우 count를 올려준다. 만약 "0"이 아니라면 for문을 빠져나온다. 출력은 count를 하면된다. 코드 import sys N = int(sys.stdin.readline()) num = 1 if N == 0 or N == 1: print(0) else: for i in range(1, N+1): num *= i st = str(num) count = 0 for i in range(len(st)): if st[len(st)-i-1] == "0": count += 1 else: bre..
알고리즘 문제/백준 2022. 7. 7. 02:10
(백준 알고리즘 문제풀이) 1904번 가장 긴 감소하는 수열

문제 문제 링크 문제 접근 이 문제는 dp에 대한 개념을 정리하기에 좋은 문제인 듯하다. step1: N과 수열 받아온다. step2: dp의 list를 모두 1로 초기화한다. step3: i번째 수열의 이전 값이 i번째 수열 값보다 크면 dp의 i번째를 dp의 i번째와 이전의 dp보다 큰 값이 있다면 그 값에 +1한 것과 비교하여 높은 것을 dp의 i번째에 넣는다. step4: dp리스트에서 가장 높은 값을 출력한다. 코드 import sys N = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) dp = [1] * N for i in range(N): for j in range(i): if array[i] <..
알고리즘 문제/백준 2022. 7. 7. 01:28
Prev 1 ··· 39 40 41 42 43 44 45 ··· 47 Next