이론

[python 알고리즘 팁] 소수판별, 진수 변환

소수 판별 64까지의 약수를 판별하자면 1 x 64, 2 x 32x 4 x 16, 8 x 8로 1, 2, 4, 8, 16, 32, 64의 약수를 갖는걸 알 수 있다 자기 자식의 제곱근까지의 수를 살펴보면 전체 약수를 구할 수 있다. 이렇게 소수를 찾는 방법을 에스테라토스 체라 한다. num(num > 0)이 주어졌을 때 소수인지 아닌지 판별하려면 1이면 소수가 될 수 없다 2이면 소수다 짝수면 2로 나눠지므로 소수가 아니다 그 외 수는 홀수만 살펴보면서 num과 나누었을 때 나머지가 0인 수가 있다면 num은 소수가 아니다 위와 같은 조건들로 코드를 짜면 아래와 같다 import math # 소수 판별 함수 def check(num): # 2이면 소수 if num == 2: return True # 1이..

파이썬 문법 정리 (1)

1. ord 함수, chr 함수 1-1) ord(문자) 하나의 문자를 인자로 받고 해당 문자에 해당하는 유니코드 정수 반환 result1 = ord('a') # 97 result2 = ord('ㄱ') # 12593 1-2) chr(숫자) 하나의 정수를 인자로 받고 해당 정수에 해당하는 유니코드 문자 반환 result3 = chr(97) # a result4 = chr(12593) # ㄱ 2. 정렬 sort, sorted [공통점] sort와 sorted는 둘다 내림차순으로 정렬해준다 정렬 후 a[::-1]을 사용하면 오름차순 정렬이 가능하다 [차이점] sort는 따로 변수에 할당해주지 않아도 되지만, sorted는 정렬된 리스트를 반환 해주는 함수기 때문에 변수에 할당 해줘야 한다 2-1) a.sort(..

Github 여러 계정 한 기기에서 사용하기

회사 컴퓨터를 사용하면서 개인 Github도 같이 관리하고 싶은데 어려움이 있었습니다 이처럼 저와 같이 계정분리를 원하는 분들을 위해 해결방법을 알려드리고 싶어 글을 적었습니다 1. 원하는 계정의 SSH key-gen만들기 일단 아무폴더에 가서 무지성으로 코드를 쳐줍니다 > ssh-keygen -t rsa -b 4096 -C "your@email.com" 그럼 아래처럼 저장할 폴더를 물어보는데 Generating public/private rsa key pair. Enter file in which to save the key (/${userPath}/id_rsa): 저는 id_rsa가 아닌 personal로 key를 저장하였습니다 Enter file in which to save the key (/${..

[최단경로] 다익스트라 - Python

최단경로 알고리즘 그래프 상에서 가장 짧은 경로를 찾는 알고리즘 최단경로를 찾는 알고리즘으로는 다익스트라 알고리즘과 플로이드 워셜 알고리즘, 벨만포드 알고리즘이 있다 종류 한 지점에서 다른 특정 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 모두 구하기 등이있음 표현 방법 그래프로 표현하며 각 지점은 그래프에서 노드로 표현되고, 지점간 연결된 도로는 그래프에서 간선으로 표현됨 다익스트라 알고리즘 '단계마다 방문하지 않은 노드 중에서 가장 최단 거리가 짧은 노드'를 선택한 뒤에 그 노드를 거쳐가는 경우를 확인해 최단 거리를 갱신하는 방법 우선순위 큐를 이용해 소스코드를 작성해야 효율적이다 역할 : 한 지점에서 다른 모든 지점까지의 최단 경로를 계산합니다 음의간선(0보다 작은 값을 가지..

우선순위 큐와 heap - python

참고 | 이코테2021 | 우선순위 큐 우선순위 큐 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용 ex) 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터꺼내서 확인해야 하는 경우 구현 방법 단순히 리스트 이용해 구현 가능 힙(heap)을 이용해 구현 가능 데이터가 N개일 때 구현 방식에 따른 시간복잡도 우선순위 큐 구현 방식 삽입 시간 삭제시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일(힙 정렬) 이 경우 시간 복잡도는 O(NlogN) 힙의 특징 힙은 완전 이진 트리 자료구조의 일종 힙에서는 항상 루트 노드를 제거한다 최소 힙(m..

[그래프탐색] BFS - JS, Python

너비 우선 탐색 - Breath Frist Search 가까운 노드부터 탐색하는 알고리즘 DFS는 최대한 멀리있는 노드를 우선으로 탐색하는 방식으로 동작한다했는데, BFS는 가까이 있는 노드부터 우선탐색 큐를 이용한 선입선출방식 가중치 없는 그래프에서 최단 경로 문제에서 많이 쓰인다 ex) 서울에서 부산으로 가는데 거쳐야하는 최소 정거장의 수 ex) 임의의 4자리 숫자 x에서 한자리(0~9)로 변경하면 다른 숫자 y를 만들 수 있음 이떄 x에서 z를 만들기 위한 최소 변경횟수 ex) 친구관계에서의 단계 1. 탐색 시작 노드를 큐에 삽입하고 방문처리 2. 큐에서 노드를 꺼내 해당 노드의 인접노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문처리 3. 2번 과정을 더이상 수행할 수 없을 때까지 반복 ..