Algorithm
-
[알고리즘] 기본 정렬 알고리즘[버블 정렬, 삽입 정렬, 선택 정렬] - ItisFutureAlgorithm 2022. 9. 14. 22:13
버블 정렬 ---- for문을 한 번 돌면 마지막에는 무조건 큰 숫자가 담긴다 ---- 매번 처음 인덱스 부터 시작 ---- 기준 인덱스와 바로 뒤 인덱스를 비교하여 앞이 크면 자리를 바꾼다. def bubblesort(ary): for idx1 in range(len(ary) - 1): # 길이보다 하나 작게 반복할거야 for idx2 in range(len(ary) - idx1 - 1): # 매번 처음부터 시작, 끝은 길이에 반복 횟수와 1을 빼줌 -> 왜 1을 빼줘? if ary[idx2] > ary[idx2+1]: # 기준보다 하나 큰 인덱스를 사용하기 때문에 ary[idx2], ary[idx2+1] = ary[idx2+1], ary[idx2] return ary 삽입 정렬 - 기준과 기준 다음의..
-
[백준 1158 Python] 요세푸스 문제 파이썬 - ItisFutureAlgorithm/Baekjoon 2022. 9. 13. 20:13
m,n=map(int,input().split()) li = list(range(1,m+1)) step = n - 1 del_idx = step res = [] while len(li)>0: length = len(li) if del_idx > length - 1: del_idx %= length res.append(li.pop(del_idx)) del_idx += step print('') 문제 아이디어 1. 제거할 인덱스는 리스트의 길이 값으로 나눈 나머지 값 2. 다음의 빼야할 인덱스(del_idx)는 하나가 제거 된 리스트가 기준이기 때문에 step은 하나 작은 값이 된다.
-
[알고리즘] 더하거나 빼거나 - ItisFutureAlgorithm 2022. 9. 13. 20:06
Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 , 타겟 넘버 target_number이 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오. - 리스트의 순서를 바꾸는 것이 아닌 순차적으로 더하거나 빼거나 cnt = 0 def plus_or_minus(num_list, target_num, start_idx, now_total): global cnt ..
-
[자료구조/알고리즘] 링크드 리스트 자료구조 - ItisFutureAlgorithm/theory 2022. 9. 13. 19:38
링크드 리스트는 노드와 노드를 이어 제한 없이 생성 가능하다는 장점이 있다. 단점은? 즉각적인 인덱싱의 어려움, 메모리를 많이 먹는다. 링크드 리스트의 시작 마지막 노드에 다음 노드를 추가해주는 것을 기억하면 쉽다. ( 기차 놀이 ) class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, data): self.head = Node(data) def add(self, data): if self.head == '': self.head = Node(data) else: node = self.head while node.next: node = node.next node.ne..
-
[백준 18870 Python] 좌표 압축 - ItisFutureAlgorithm/Baekjoon 2022. 9. 11. 22:29
내가 쓴 정답 코드 n = int(input()) n_list = list(map(int,input().split())) n_dic = {i:0 for i in n_list} n_sorted_list = sorted(n_list) cnt = 0 prev = n_sorted_list[0] for i in n_sorted_list: if i == prev: n_dic[i] = cnt else: cnt+=1 n_dic[i] = cnt prev = i for idx,i in enumerate(n_list): n_list[idx] = n_dic[i] print(*n_list) 풀이 아이디어 1. 제일 작은 숫자가 0 임을 파악 2. 오름차순으로 +1씩 2-1. 주어진 값에 대하는 순서를 딕셔너리에 업데이트 3. ..
-
[백준 9020번 python] 골드 바흐의 추측Algorithm/Baekjoon 2022. 9. 5. 19:59
정답 코드 li=[0]*10001 for num in range(2,10001): for i in range(2,int(num**0.5)+1): if num % i == 0: li[num] = 0 break else: li[num]=num for _ in range(int(input())): n = int(input()) st = 0 for i in range(n//2,0,-1): if li[i] != 0: st = i break sosu_list = sorted(set(li[:n+1])) st_idx=sosu_list.index(st) brk=False for idx,i in enumerate(sosu_list[st_idx::-1]): for j in sosu_list[idx:]: if i+j == n..
-
백준 1920번 수 찾기 파이썬 pythonAlgorithm/Baekjoon 2022. 4. 29. 16:04
선행 지식 1. List 와 Set에서의 in 연사자 성능 차이 더보기 list 자료형에서는 in 연산자의 시간 복잡도는 O(n)이다. ==> 앞에서 부터 차례로 하나하나 비교해 나간다. set 자료형에서는 in 연산자의 시간 복잡도는 O(1)이다. ==> 어떤 숫자를 찾던 같은 시간이 걸린다. ex) list(range(1,1000000))와 set(range(1,1000000)) (1번 상황) 숫자 1을 찾아라 1 in 리스트 >>> 0초에 가까운 시간 1 in set >>> 0.5초 (예시) (2번 상황) 100000 in 리스트 >>> 100초 100000 in set >>>0.5초 정리 List 자료형은 선형적으로 시간이 늘어나고, Set 자료형은 일정하다. 결론 많은 양의 데이터에서의 in을 ..