할껀하고놀자

# 6.4 소풍 문제를 해결하는 (잘못된) 재귀 호출 코드 from sys import stdin import sys sys.stdin = open('1.txt') # 3 # 2 1 # 0 1 # 4 6 # 0 1 1 2 2 3 3 0 0 2 1 3 # 6 10 # 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 def countPairings(taken, areFriend, n): finished = True for i in range(n): if not taken[i]: finished = False if finished: return 1 ret = 0 for i in range(n): for j in range(n): if not taken[i] and not taken[j]..

# 6.3 보글 게임판에서 단어를 찾는 재귀 호출 알고리즘 dx = [-1, -1, -1, 1, 1, 1, 0, 0] dy = [-1, 0, 1, -1, 0, 1, -1, 1] # 한글자만 검사하는 방식으로 기저사례를 찾아내었다. def hasWord(y, x, word, a): # 기저사례1 : 범위 넘어가지 않기 if (x = len(a) or y = len(a)):return False # 기저사례2 : 첫글자가 다를 경우 if (a[y][x] != word[0]): return False # 위 거름망 통과 후에 길이가 1이라면 첫글자도 같고, 범위도 넘어가지 않는 경우이므로 # 참 반환 if (len(word) == 1): return True for dir ..

# 6.2 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘 def pick(n, list, toPick): if toPick == 0: print(list) return smallest = 0 if len(list) == 0 else list[-1] + 1 for next in range(smallest, n): list.append(next) pick(n, list, toPick - 1) list.pop() # 7까지의 숫자에서 4개의 숫자를 뽑고싶다. pick(7, [], 4)

# 삽입 정렬 list = [20,12,10,15,2] for i in range(len(list)): j = i while(j>0 and list[j-1]>list[j]): list[j-1],list[j] = list[j],list[j-1] j-=1 print(list) 속도 ( N~N^2) 정렬되어있다면 while문을 탐색하지 않기 때문에 for문 한번만 돌게 된다. 역순 정렬되어있다면 n^2번 탐색한다.

list = [20,12,10,15,2] for i in range(len(list)): for j in range(len(list)-1-i): if list[j]>list[j+1]: list[j],list[j+1] = list[j+1],list[j] print(list) 정렬 방법론. 1. N번째 위치와 N+1번째 위치의 값을 비교해서, N+1번째 위치의 값이 더 클 경우 N번째와 N+1번째의 값을 교환함. 특징. 1. 계속 비교하므로 리스트 크기가 크면 불리하다. 2. 정렬이 거의 된 데이터일 경우 더 유리하다.(교환이 적게 일어나므로) 3. 데이터가 역순인경우, 즉 최악의경우에 시간이 엄청 느리다.

list = [20,12,10,15,2] for i in range(len(list)): for j in range(i+1,len(list)): if list[i]>list[j]: list[i],list[j] = list[j],list[i] print(list) 정렬 방법론. 1. 최솟값을 찾아서 0번째 위치와 바꿈. 2. 0번째 위치를 제외한 최솟값을 찾아서 1번째 위치와 바꿈. 3. N번째까지의 위치를 제외한 최솟값을 찾아서 N번째와 바꿈. 4. 끝까지 가면 성공. 특징. 1. 정렬되있는 순서로 들어오던 아니던 실행시간이 비슷하다. 항상 비교하는양이 동일하기 때문. 2. 추가적인 기억장소를 요구하지 않는다.

문자열 검색 알고리즘. for문 한번만 돌기 때문에 좋다. #include #include using namespace std; vector makeTable(string pattern) { int j = 0; int patternSize = pattern.size(); vector table(patternSize, 0); for (int i = 1; i 0 && pattern[i] != pattern[j]) { j = table[j - 1]; } if (pattern[i] == pattern[j]) { table[i] = ++j; } } return table; } void KMP(string parent, string pattern) { ve..

#include #include #include using namespace std; int main() { char str[] = "00:12:34"; int cnt = 0; char *context = NULL; char *token = strtok_s(str, ":", &context); while (token) { cout

#include using namespace std; int main() { int n, result = 0; cin >> n; result += n / 500; n %= 500; result += n / 100; n %= 100; result += n / 50; n %= 50; result += n / 10; n %= 10; cout

#include #include #include using namespace std; const int n = 7; const int m = 11; int getParent(int parent[], int x) { if (x == parent[x]) return x; return parent[x] = getParent(parent, parent[x]); } void unionParent(int parent[], int a, int b) { a = getParent(parent, a); b = getParent(parent, b); if (a < b)parent[b] = a; else parent[a] = b; } int find(int parent[], int a, int b) { a = getParen..