이론/알고리즘

[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이..

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

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

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

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

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

탐색이란? 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 그래프, 트리 등의 자료구조 안에서 탐색하는 문제 자주 물음 DFS와 BFS를 다루기 전에 스택, 큐, 재귀함수에 대한 개념을 알아야 하는데 전 포스팅에 정리한 내용을 확인해 주세요 2021.02.07 - [이론/자료구조] - 스택(Stack) - JS 2021.02.07 - [이론/자료구조] - 배열 - JS 2020.04.15 - [이론/알고리즘] - 재귀 함수 배열 - JS 배열이란? 가장 일반적인 구조 메모리 상에 같은 타입의 자료가 연속적으로 저장됨 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위 특징 같은 타입의 데이터를 나열한 선형 자료구조 ssafy-story.tistory.com 스택(Stack) - JS 참고사이트자바..

[소수 판별] 에라토스테네스의 체 - JS

에라토스테네스의 체 소수 판단 알고리즘 소수들을 대량으로 빠르고 정확하게 구하는 방법 단일 숫자 소수 여부 확인 어떤 수의 소수 여부 확인할 때는 특정한 숫자의 제곱근 까지만 약수의 여부를 검증하면 O(N*1/2)의 시간 복잡도로 빠르게 구할 수 있음 수가 수(N)를 나누면 몫이 생기는데, 몫과 나누는 수 둘 중 하나는 N의 제곱근 이하이기 때문 원리 가장 먼저 소수를 판별할 범위만큼 배열을 할당하여, 해당하는 값을 넣어주고, 이후에 하나씩 지워나감 배열을 생성하여 초기화 2부터 시작해서 특정 수의 배수에 해당하는 수를 모두 지운다. (지울 때 자기자신은 지우지 않고 이미 지워진 수는 건너뛴다) 2부터 시작하여 남아있는 수를 모두 출력한다 Array() : 배열 초기화 Array안에 수(n)를 넣으면 n..

[JavaScript] 알고리즘에 쓰이는 문법(형변환)

형변환 Number() string을 숫자로 바꿔줌 문자가 하나라도 포함되어 있을경우 NaN출력 Number('123') // 123 Number('12.3') // 12.3 Number('123e-1') // 12.3 Number('') // 0 Number(null) // 0 Number('0x11') // 17 Number('0b11') // 3 Number('0o11') // 9 Number('foo') // NaN //문자가 하나라도 있으면 Nan Number('100a') // NaN parseInt string을 진수별 10진수 정수로 바꿔줄 수 있음 숫자가 하나라도 있으면 숫자출력(Number와의 차이점) ECMAScript 5는 8진수 해석을 삭제했음 parseInt('12.68') //..