viamemine

📍 삽입 정렬: 앞에서부터 순서대로 보면서, 앞에 있는 모든 원소가 정렬되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬시간복잡도: O(N^2)n 개의 원소에 대해 값 삽입을 수행하는데, 2번째 원소의 경우에는 최대 1개의 원소를 이동해야 하고, 3번째 원소의 경우에는 최대 2개의 원소를 이동해야 하며, n번째 원소까지 삽입하는 경우에는 최대 n-1개의 원소가 이동해야 함  💬 python 코드n 개의 원소가 주어졌을 때, 삽입 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().split()))for i in range(1, n): key = arr[i] j = i-1 while j >..

📍 선택 정렬: 앞에서 부터 정렬하는, 일상적인 방법의 알고리즘전체 값 중 가장 작은 값을 찾고, 해당 값을 맨 첫 번째에 배치함첫 번째 값을 제외하고 가장 작은 값을 찾아 두 번째에 배치함 두 번째, 세 번째, ... , n-1 번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함시간 복잡도: O(N^2)n-1, n-2, ..., 2, 1번의 비교 연산을 수행해야 하기 때문에, n(n-1)/2번의 연산 필요함 💬 python 코드n 개의 원소가 주어졌을 때, 선택 정렬을 이용해 n 개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().split()))for i in range(n-1): min_idx = i for j in r..

📍 버블 정렬: 가장 단순한 정렬 알고리즘 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ..., n-1번째와 n번째 값을 비교한다. 순서가 맞지 않은 값을 서로 교환하고, 정렬이 될 때까지 반복한다.비효율적인 알고리즘시간복잡도: O(N^2)ex) 5, 4, 3, 2, 1이라는 데이터가 존재한다고 가정할 때 한 바퀴 돌면 4, 3, 2, 1, 5로 정렬됨두 바퀴 돌면 3, 2, 1, 4, 5로 정렬됨N개의 숫자가 N-1 바퀴 돌아야 함 ( 나머지 한 개는 자연스럽게 정렬되기 때문에 고려하지 않아도 됨) 💬 python 코드 n 개의 원소가 주어졌을 때, 버블 정렬을 이용해 n개의 숫자를 오름차순으로 정렬n = int(input())arr = list(map(int, input().s..

문제 잘못된 풀이 n = int(input()) dp = [0] * n dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[i] = dp[i-1] + dp[i-2] print(dp[n-1] % 10007) 해당 문제는 다이나믹 프로그래밍으로 해결할 수 있다. 2*1일 때, 1 / 2*2일 때, 2 / 2*3일 때, 3 / 2*4일 때, 5 / 2*5일 때, 8 으로, dp[i] = dp[i-1] + dp[i-2]를 만족한다. 하지만 해당 풀이는 dp의 사이즈를 n으로 지정하면서 런타임 오류(IndexError)가 발생하였다. 올바른 풀이 n = int(input()) dp = [0] * 1000 dp[0] = 1 dp[1] = 2 for i in range(2, n): dp[..

문제 잘못된 풀이 T = int(input()) for i in range(0, T): n = int(input()) dp = [0] * n dp[0] = 1 dp[1] = 2 dp[2] = 4 for j in range(3, n): dp[j] = dp[j-1] + dp[j-2] + dp[j-3] print(dp[n-1]) 해당 문제는 n=1일 때, 1 / n=2일 때, 2 / n=3일 때, 4 / n=4일 때, 7 / n=5일 때, 13 / n=6일 때, 24이다. dp를 n만큼 초기화하여 문제 풀이를 시도했다. 런타임 에러(IndexError)로 문제풀이에 실패했다. 올바른 풀이 T = int(input()) def dfs(n): if n == 1: return 1 elif n == 2: return..

문제 올바른 풀이 n = int(input()) # 1 ~ 90 dp = [0] * (n+1) dp[0] = 0 dp[1] = 1 for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] print(dp[n]) 해당 문제는 다이나익 프로그래밍에 대한 매우 간단한 문제라, 쉽게 풀 수 있다.

문제 올바른 풀이 N = int(input()) def check_hansu(num, check): if num > 99: # 1000보다 작은 자연수 num_str = [int(i) for i in str(num)] if num_str[1]-num_str[0] == num_str[2]-num_str[1]: check = 1 else: check = 1 return check check = 0 cnt = 0 for i in range(1, N+1): cnt += check_hansu(i, check) print(cnt) 해당 문제는 각 자리수의 차가 동일한지를 확인하는 문제이다. 완전 탐색으로 문제를 해결하면 되는데, 1000보다 작거나 같은 자연수만큼 for문을 돌려서 각 자리수의 차를 확인해보면 된다..

문제 나의 풀이 not_self_number = list() for i in range(1, 10001): number = [int(num) for num in str(i)] not_self_number.append(sum(number) + i) if i not in not_self_number: print(i) 나는 각 자릿수를 더하는 과정을 string으로 변환하여 for문으로 처리하였다. 그리고 self_number가 아닌 숫자들을 담을 list를 만들어서 생성자를 담아준다. 최종적으로 생성자가 없는 셀프 넘버를 출력한다. 남의 풀이 def self_number(num): self_num = num while num != 0: self_num += num%10 # 오른쪽 끝 숫자를 더함 num //..

문제 잘못된 풀이 N = int(input()) num_list = list() num_list.append(666) for i in range(1, 10001): num = str(i) + str(666) num_list.append(int(num)) num = str(666) + str(i) num_list.append(int(num)) num_list.sort() print(num_list[N-1]) 666을 기준으로 앞 뒤에 숫자를 붙여서 .sort()한다면 문제를 해결할 수 있을 것이라고 생각했다. 올바른 풀이 N = int(input()) cnt = 0 num = 1 while True: if '666' in str(num): cnt+=1 if cnt==N: print(num) break nu..

문제 올바른 풀이 a, b, c, d, e, f = map(int,input().split()) for x in range(-999, 1000): for y in range(-999, 1000): if a*x + b*y == c and d*x + e*y == f: print(x, y) break 해당 문제는 쉬운 문제로, 완전 탐색으로 빠르게 해결할 수 있었다. (처음에 범위 설정을 999로 했다가 1000으로 재설정하여 풀이하였다.)