전체 글

✨백트래킹(backtracking) 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법 주요 개념은 해를 얻을 때까지 모든 가능성을 시도 트리를 검사하기 위해 깊이 우선 탐색을 사용 ✨ 예시문제) 백준 N과 M(1) https://www.acmicpc.net/problem/15649 끝나는 조건:리스트의 길이가 M이 되었을때 -> 정답목록에 해당 리스트를 추가, 종료 수열의 조건: 방문했던 숫자에 다시 방문하면안됨 ->방문 리스트 V를 만들어서 체크 전체 코드 import sys def back(n,li): if(n==M): answer.append(li) #종료조건 return for j in range(1,N+1,1): if(V[j]==0): V[j]=1 back(n+1,li+..

✨ 합병정렬(merge sort) 합병 정렬은 O(n log n) 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다. (분할정복:그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법) ✨ 과정(2-way 합병 정렬) 길이가 1이하임을 확인(1이하인경우 정렬완료상태) 분할: 리스트를 절반으로 나눈다. 정복:각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬 결합:두 부분 리스트를 다시 하나의 정렬된 리스트로 합병( 임시배열에 저장 ) 복사:임시 배열에 저장된 결과를 원래 배열에 복사 def merge_sort(arr): #길이 1이하확인 if(arr

✨팩토리얼(factorial) 그 수보다 작거나 같은 모든 양의 정수의 곱 python 코드 import sys n=int(sys.stdin.readline().rstrip()) su=1 for i in range(1,n+1,1): su*=i sys.stdout.write(str(su)) ✨순열(permutation) 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산 n개의 요소에서 k개를 뽑는다. itertools의 permutations코드 from itertools import permutations n=[1,2,3,4] k=2 print("개수:"+str(len(list(permutations(n,k))))) for i in permutations(n,k):print(i, end="") #결과..

✨ 유클리드 호제법(Euclidean algorithm) 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. ✨과정 a,b 두개의 자연수가 있다 (a>b) a/b -> 나머지 r1 a/r1 -> 나머지 r2 3번을 반복 a/r -> 나머지 0 일때 r은 a,b의 최대공약수다. A,B=list(map(int,sys.stdin.readline().rstrip().split(" "))) if (B>A):A,B=B,A num=A r=B while True: r1=num%r if(r1==0): break num=r r=r1 print(r) 🎈참고자료 https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%9..

✨Set(집합) 1.순서가 없다.(비순차적) 2.중복이 허용되지않는다.(중복 들어갈경우 하나의 값만 저장) ✨python 집합 set A= set(list) A= {1,2,3,4} A.add(5) A.update(6,7,8) A.remove(8) A.discard(9) #KeyError 발생 안함 print(1 in A) #True print(A.pop()) #임의의 요소 하나 제거 ✨교집합(and) A & B A.intersection(B) ✨합집합(or) A | B A.union(B) ✨차집합(-) A - B A.difference(B) ✨대칭 차집합(XOR) A^B A.symmetric_difference(B) 🎈참고자료 https://data-marketing-bk.tistory.com/entry..

✨계수 정렬(Counting Sort) 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나 키의 다양성이 항목의 수보다 상당히 크지 않은 상황에서 사용한다. ✨과정 배열 생성 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가 인덱스를 인덱스 값만큼 출력 ex) 백준 수 정렬하기 3 https://www.acmicpc.net/problem/10989 import sys n=int(sys.stdin.readline().rstrip()) li=[0]*10001 for i in range(n): a=int(sys.stdin.readline().rstrip()) li[a]+=1 for i in range(1,len(li)): for j in..

✨deque(덱) 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태 ✨python deque ✨ deque import from collections import deque ✨ deque 생성 dq = deque() ✨deque 뒤,앞 값 추가 dq.append() dq.appendleft() ✨deque iterable 객체 값추가 dq.extend([7, 8, 9]) dq.extendleft([2, 1, 0])#마지막 값부터 추가됨 ✨deque 뒤,앞 값 pop dq.pop() dq.popleft() ✨deque 값 number만큼 회전(number 양수 1->2->3->4->5->1..., number 음수 5->4->3-..

✨Stack(스택) 스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다. 구조가 단순해서 구현이 쉽다. 데이터 저장/읽기 속도가 빠르다. class stack: def __init__(self): self.items = [] def push(self, item): self.items.append(item) def peek(self): return self.items[-1] def pop(self): if len(self.stack) < 1: return None return self.stack.pop() ✨Queues(큐) 먼저 들어간 자료가 먼저 나오는 자료구조. 자료를 넣는 Enqueue 함수와 자료를 빼내는 Dequeue 함수를 가진다. 선..