반응형 분류 전체보기108 2022-07-29 TIL ☝ 리스트에서 특정 인덱스보다 크거나 작은 수 찾기 이중 for문을 사용하여 해당 인덱스부터 마지막 인덱스까지 순차적으로 크거나 작은 수가 있는지 찾기 ☝ 백준 1912번 import sys n = int(sys.stdin.readline()) array = list(map(int, sys.stdin.readline().split())) d = [-1000] * ((10**5)+1) d[1] = array[0] for i in range(1, n) : if array[i] + d[i] > array[i] : d[i+1] = array[i] + d[i] else : d[i+1] = array[i] print(max(d)) 2022. 7. 30. 2022-07-27 TIL ☝ 다이나믹 프로그래밍 동적 계획법이라고 표현하기도 함 다이나믹 프로그래밍으로 해결할 수 있는 대표적 예시 👉 피보나치 수열 ☝ 피보나치 수열 피보나치 수열 👉 이전 두 항의 합을 현재의 항으로 설정하는 수열 피보나치 수열 구현 예시 def fibo(x) : if x == 1 or x == 2 : return 1 return fibo(x-1) + fibo(x-2) print(fibo(10)) 해당 방식은 n이 커질수록 시간이 기하급수적으로 증가 👉 O(2*n) ☝ 다이나믹 프로그래밍 사용 조건 큰 문제를 작은 문제로 나눌 수 있을 때 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일할 때 ☝ 메모이제이션 기법 다이나믹 프로그래밍을 구현하는 방법 중 한 종류 한 번 구한 결과를 메모리 공간에 .. 2022. 7. 27. 2022-07-26 TIL ☝ 리스트에서 set을 이용해서 중복 제거하기 array = list(set(array)) set을 이용해 중복을 제거한 후 다시 list로 변환 ☝ 리스트를 길이로 정렬하고 길이가 같은 경우 문자로 정렬하기 이 경우 배열에 문자열의 길이와 문자를 같이 저장해준다. sort 함수와 lambda를 이용해 문자열 길이로 한 번 문자로 한 번 정렬해준다. for _ in range(n) : word = sys.stdin.readline().strip() array.append((len(word), word)) array.sort(key = lambda array: (array[0], array[1])) ☝ Collections 함수 어떤 리스트에서 각 리스트 요소 별 개수를 세는 함수 from sys impo.. 2022. 7. 27. 2022-07-22 TIL ☝ 알고리즘 반복문을 돌려서 반복문의 결과로 나오는 값 중 최댓값이나 최솟값을 구해야 하는 경우, 반복문 내에서 반복문의 결과를 받을 변수를 선언하고, 반복문 밖에서는 반복문의 결과를 받아온 변수와 비교하여 최종 값을 저장할 변수를 설정한다. 예시 # 1부터 10까지 반복문을 돌려 최댓값을 찾는 경우 #최종값을 받을 변수 선언 result = 0 for i in range(1, 11) : #반복문의 리턴값을 받을 변수 선언 count = 0 for x in range(n) : for y in range(m) : #로직 실행 생략 count += 1 #반복문 실행 결과값과 외부의 result(처음은 0)과 max 비교 result = max(count, result) #실행 결과 외부의 result 값 변.. 2022. 7. 22. 2022-07-21 TIL 오늘 증명사진 찍으러 갔다 오느라고 개인 공부를 많이 못했다 .. 또르르.. ☝ 좌표가 주어졌을 때 그래프 그리기 - for문의 범위를 좌표로 제한 x1, y1, x2, y2 = map(int, input().split() for i in range(y1, y2) : for j in range(x1, x2) : graph[i][j] = 1 - x 좌표 시 y값의 range로 체크한다는 것에 주의 ☝ bfs 방문처리 - 방문처리할 때 초기 방문처리를 해야 하는지 안 해야 하는지 주의해서 사용하기 - queue에 append 하기 직전 방문처리 하는 것이 좋다. 2022. 7. 21. 2022-07-20 TIL ☝ 스택 - 선입 후출 - append(), pop() 메서드 사용 가능 - 스택 최상단 원소부터 출력하는 방법 print(stack[::-1]) ☝ 큐 - 선입선출 - from collections import deque - 큐 규현을 위해 deque 라이브러리 사용 - queue = deque() - append(), popleft() 메서드 사용 가능 - queue.reverse()로 역순 정렬 가능 ☝ 재귀 함수 - 자기 자신을 다시 호출하는 함수 - 재귀 함수는 스택 자료 구조를 이용하기 좋다. - 마지막에 호출된 함수가 수행을 끝내야 그전에 호출된 함수가 실행될 수 있기 때문 - 스택 자료구조로 재귀 함수를 이용하는 대표적 알고리즘은 DFS ☝ DFS - 깊이 우선 탐색(Depth First .. 2022. 7. 21. 이전 1 2 3 4 5 ··· 18 다음 반응형
