Algorithm (21) 썸네일형 리스트형 [코드트리 조별과제] 동적계획법 동적계획법: 큰 문제에 대한 답을 얻기 위해 동일한 문제이지만 크기가 더 작은 문제들을 먼저 해결한 뒤, 그 결과들을 이용해 큰 문제를 비교적 간단하게 해결하는 기법for loop 이용재귀함수 이용메모이제이션: 값을 기록하고, 그 기록한 값을 참조하는 것memoization 이용시에는 함수 도입부에 -1이 아닌 경우 memo 값을 반환해주는 코드를 작성그렇지 않은 경우라면 반환해줘야 하는 값을 memo에 저장해준 뒤 해당 값을 반환해주면 됨탑다운 방식Tabulationfor문 이용하는 방법Tabulation이용 시 배열의 이름은 보통 dp라고 지음바텀업 방식💡 이론적인 시간복잡도는 두 방법이 동일하나, 탑다운 방식은 함수를 재귀적으로 여러번 실행해야 하므로 함수 처리에 추가적인 시간이 약간 더 붙어 실.. [코드트리 조별과제] 이진탐색 이진탐색시간복잡도O(logN)루프 한 번 돌 때마다 다루는 구간의 길이는 반으로 감소, 구간의 길이가 1이 될 때까지 계속 반복해서 탐색⇒ 루프 내부의 시간복잡도: O(N)⇒ 루프는 약 logN번 돌게 됨이진탐색의 단점반드시 정렬이 되어야 함배열이 정렬된 상태가 아니라면 정렬을 하기 위한 추가적인 연산을 필요로 함 정리탐색을 여러 번 진행해야 한다면 이진탐색을 사용하는게 좋음가장 큰 값이나 값을 딱 한개만 찾는다면 굳이 이진탐색을 사용할 이유가 없음이진탐색 시 이중연결리스트를 사용하게 되면 mid 위치를 찾는데 O(N)의 시간이 걸리므로 O(logN)보다 시간이 더 걸림Lower Bound: 원하는 값 target 이상이 처음으로 나오는 위치= target 보다 같거나 큰 원소의 위치들 중 가장 작은 값.. [SWEA / python] 1974. 스도쿠 검증 import sys sys.stdin = open("input.txt", "r") T = int(input()) for test_case in range(1, T + 1): num_list = [] result = 1 for i in range(9): tmp = list(map(int,input().split())) num_list.append(tmp) #1 가로, 세로로 겹치는 숫자 있나 확인 for i in range(9): check_r = [0 for i in range(10)] check_c = [0 for i in range(10)] check_r[0] = 1 check_c[0] = 1 for k in range(9): check_r[num_list[i][k]] += 1 check_c[num_.. [SWEA / python] 1961. 숫자 배열 회전 import sys sys.stdin = open("input.txt", "r") T = int(input()) for test_case in range(1, T + 1): n = int(input()) #행렬 크기 num_list = [] result= "" for i in range(n): tmp = list(map(int,input().split())) num_list.append(tmp) print("#"+str(test_case)) for i in range(n): # 90도 회전 for k in range(n - 1, -1, -1): result += str(num_list[k][i]) print(result, end=" ") result = "" # 180도 회전 for k in range(.. [SWEA / python] 1959. 두 개의 숫자열 import sys sys.stdin = open("input.txt", "r") T = int(input()) for test_case in range(1, T + 1): n , m = map(int,input().split()) #A, B배열 크기 a = list(map(int,input().split())) b = list(map(int, input().split())) result = 0 #최댓값 if(m>n): for i in range(m-n+1): sum = 0 for k in range(n): sum += a[k]*b[i+k] if (sum > result): result = sum else: for i in range(n-m+1): sum = 0 for k in range(m): sum .. [SWEA / python] 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV13zo1KAAACFAYh&categoryId=AV13zo1KAAACFAYh&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=2&pageSize=10&pageIndex=3 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com import sys sys.stdin = open("input.txt","r") T = int(input()) for.. [SWEA / python] 1984. 중간 평균값 구하기 https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5Pw_-KAdcDFAUq&categoryId=AV5Pw_-KAdcDFAUq&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=2&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 정렬을 굳이 하지 않아도 최대 최소값만 알면 중간값 평균은 구할 수 있기 때문에,, 하지만 정렬을 하면 if문을 쓰지.. [SWEA / python] 1859. 백만 장자 프로젝트 https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=2&contestProbId=AV5LrsUaDxcDFAXc&categoryId=AV5LrsUaDxcDFAXc&categoryType=CODE&problemTitle=&orderBy=FIRST_REG_DATETIME&selectCodeLang=PYTHON&select-1=2&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제를 푸는 핵심은 배열의 끝 요소부터 최대값으로 넣어 놓은 후 앞으로 가면서 비교하기 for 문 뒤부터 보기: fo.. 이전 1 2 3 다음
