B_log

👨‍💻 특징 - 최적해를 찾는데 사용되는 근시안적 방법 - 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 - 각 시점에서 지역적으로는 최적의 선택이지만 전체적으로 보면 그 해답이 최적이라는 보장이 없음 - 일반적으로 머리에 떠오르는 생각을 바로 구현하면 그게 탐욕 알고리즘이 된다. 🚦 필요한 경우 - 💾 예시 - 거스름돈 줄이기(500원, 100원 등 최소 개수로 거스름돈 주기) - 출처 : https://swexpertacademy.com/

👨‍💻 특징 - 모든 경우의 수를 나열해 보고 확인하는 기법 - Brute-Force 또는 Generate and Test 라고도 불린다. - 속도는 느리지만 높은 확률로 해답을 찾을 수 있다. - permutations(순열), combinations(조합)과 함께 사용하기 좋다. 🚦 필요한 경우 - 경우의 수가 작을 때 💾 예시 - - 출처 : https://swexpertacademy.com/

List의 종류 및 특징 - Tuple이 List보다 처리속도가 빠르므로 내용물을 변경하는게 아니라면 튜플을 사용하는 것이 더 좋다. - dictionary는 내용물의 순서가 없어 key의 중복을 허용하지 않는다. - set 역시 내용물의 순서가 없다. - list는 크기를 변경하는 작업은 내부적으로 큰 overhead 발생작업으로 많은 시간을 소요한다. ==> 미리 배열의 크기를 설정한 후 내용물을 변경하는 것이 더 빠르다. - set은 중복을 제거하기위해 내부적으로 Hashing 기법을 사용하는데 이 때문에 불변 객체만 저장이 가능하다. ex) 리스트를 요소로 가지고있는 리스트를 set으로 변경할 경우 에러 발생 - 배열(Array)은 같은 타입의 변수들을 하나의 이름으로 묶어 사용하는 자료구조이지만..

😅 문제 https://swexpertacademy.com/main/ 🤔 문제 상황 - 회문이 가로, 세로 두가지 경우가 발생할 수 있다. 🧐 해결 전략 - 회문을 탐색하는 함수를 만들어 판별한다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 def palin(s): rev = s[::-1] # s를 거꾸로 출력 if s[:len(s)//2] == rev[:len(s)//2]: return True return False t = int(input()) # testcase 개수 result = [] # 결과 리스트 fo..

😅 문제 https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do 🤔 문제 상황 - 하나씩 꺼내와 계산한다. 딕셔너리까지 사용할 이유가 없다. 🧐 해결 전략 - set를 통해 반복을 줄이고 개수를 세 최대값을 갱신한다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 t = int(input()) # testcase result = [] for _ in range(t): m = 0 # 최대값 a , b = list(set(input())), input() for i in range(len(a)): temp = b.count(a[i]) if temp > m : m = temp result.append(m) for i in r..

😅 문제 🤔 문제 상황 - 주어진 리스트를 보면 리스트 내부의 순서가 뒤죽박죽이고 순서가 중요하므로 단순히 정렬해서는 의미가 없다. - 주어진 리스트가 하나의 긴 string이고 부호가 {} 로 되어있으므로 리스트화 하기가 까다롭다. - split의 조건으로 '},{'를 사용하였다. 🧐 해결 전략 - 리스트를 정수화해서 담아준 뒤, 2차원으로 탐색하며 결과 요소에 없다면 새로 담는 식으로 풀이하였다. 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 def solution(s): a = s[2:-2].split('},{') for i in range(len(a)): a[i] = list(map(int, a[i].split(','))) a.sort(key = len) result = [] for i in..

문제 문제 상황 - 증가하는 부분수열 중 합이 가장 큰 것을 찾아야한다. 증가하는 수열 중 어떤 선택을 할 때 다음에 올 수 있는 요소들에 영향을 미치므로 DP를 활용한다. 해결 전략 - i 와 j로 n^2의 순회를 해주며 a[i] > a[j]일 때에만 비교를 하도록 한다. 코드 1 2 3 4 5 6 7 n, a = int(input()), list(map(int, input().split())) dp = a[:] for i in range(1, n): for j in range(i): if a[i] > a[j]: dp[i] = max(dp[j]+a[i], dp[i]) print(max(dp)) Colored by Color Scripter cs 해설 새로 학습한 것 & 실수 - dp를 초기화 할 때, ..

문제 문제 상황 - 선택을 하나 했을 때, 다음 선택을 할 수 있는 경우는 2가지 뿐이고 한 선택이 다른 선택에 영향을 주며 그 상황에서 최대 값 찾는 문제이므로 DP를 사용한다. 해결 전략 - 최대값을 담는 dp 리스트를 따로 만들어 문제의 dp를 담는다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 # dp[i][j] = i행 j열 까지의 합 중 최대가 되는 경우의 합 # a[i][j] = 주어진 삼각형을 담는 리스트 n = int(input()) a = [[0] for _ in range(n)] for i in range(n): a[i] = list(map(int, input().split())) dp = [[0]*n for _ in range(n)] dp[0][..