Algorithm
DP JS로 구현하기
DP JS로 구현하기 1. DP의 뜻 이미 계산된 결과는 별도의 메모리 영역에 저장해서 다시 계산하지 않도록 함 메모리 적절히 사용하여 수행시간 효율성 비약적 향상 자료구조에서 동적 할당을 의미함 → 메모리 할당하는 기법, 그러나 알고리즘에선 이런 의미 뜻하진 않음 2. 풀이 흐름 일단 재귀 함수, 그리디, 구현, 완전 탐색 등 아이디어로 풀 수 있는지 생각해보고 일단 그 방식대로 작성 그 이후로 코드 개선 or 어떻게 해도 안되면 Dp를 고려 (시간 초과 등..) 대표적으로 사용하는 경우 최적 부분 구조 : 큰 문제를 작은 문제로 나눌 수 있을 때 → 작은 문제의 답을 모아서 큰 문제 해결 중복되는 부분 문제 : 동일한 작은 문제 반복적 해결 3. 종류 공통적인 전제 : 메모이제이션 ) 한 번 계산한 ..
BFS&DFS 알고리즘 JS로 구현하기
BFS&DFS JS로 구현하기 1. BFS : 너비 우선 탐색 1-1.필요한 자료구조 큐 (선입선출) 일반 배열을 큐처럼 이용 삽입 연산 : push 삭제 연산 : shift 1-2. 풀이 흐름 전제 ) 깊이 찾기보다 넓게 찾음 -> 최단 경로 찾기와 비슷 시작 노드를 큐에 넣고 방문 처리 큐에서 노드 꺼내고, 꺼낸 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 2의 과정 수행할 수 없을 때까지(큐가 빌 때까지 반복) 1-3. 구현 방식 // 각 노드 연결 정보, 첫번째 노드부터 보고자 배열 첫째항은 비워둔다. const graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7], ]; /..
편집거리 알고리즘
1. 문제 문자열 A, B가 주어졌을 때, 문자열 A를 편집해서 문자열 B로 만들고자 한다. 문자열 A를 편집할 때는 삽입, 삭제, 교체 세 가지 연산 중 하나를 선택하여 이용할 수 있다. 이때 편집거리란 문자열 A를 편집하여 B로 만들기 위해 사용한 연산의 수를 의미한다. 문자열 A를 문자열 B로 만드는 최소 편집 거리를 계산하는 프로그램을 작성하라. 예를 들어 "sunday"와 "saturday"의 최소 편집거리는 3이다. 2. 풀이 이런 방식으로 dp 테이블을 만들면, dp[n][m]이 최소 편집거리가 된다. def edit_dist(str1, str2): answer=0 n = len(str1) m = len(str2) dp = [[0] * (m+1) for _ in range(n+1)] # 초반..
[백준 14502] 연구소 / 파이썬
문제 https://www.acmicpc.net/problem/14502 생각한 과정 1을 딱 세 개만 추가해서 2가 최대한 안 퍼지도록 해야한다 ! 0인 칸들의 좌표를 넣어 두고 그 안에서 조합을 이용해 세 개를 꺼내 벽을 세우고 벽을 세운 경우들마다 bfs를 통해 바이러스를 퍼뜨리고 안전영역의 크기를 최댓값으로 업데이트 코드 import sys from collections import deque from itertools import combinations input = sys.stdin.readline n, m = map(int, input().rstrip().split()) graph = [list(map(int, input().rstrip().split())) for _ in range(n)]..
Javascript 알고리즘 #2 소수 찾기
문제 설명 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한사항 n은 2이상 1000000이하의 자연수입니다. 입출력의 예 n result 10 4 5 3 첫번째 풀이 방법 2부터 n까지 하나하나 소수인지 점검 나머지가 0인 수가 나오는 순간 걔는 소수가 아니므로 다시 for문으로 가서 다음 수 점검 continue문 영향 받지 않고 내려가서 수행되면 소수이므로 answer++ function solution(n) { var answer = 0; next: for(let i=2;i 소수의 배수들을 제거하고 남은 애들이 소수 기본적으로 1 대입, 소수가 아닌 것들을 ..
Javascript 알고리즘 #1 두 개 뽑아서 더하기
문제 설명 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 입출력의 예 numbers result [2,1,3,4,1] [2,3,4,5,6,7] [5,0,2,7] [2,5,7,9,12] 풀이 방법 배열 첫번째 하나 가져다가 2,3,4,5,...n 번째 접근하면서 더하기 그 중 중복되지 않는 애들 answer배열에 넣기 answer 배열 버블 정렬 function solution(numbers) { var answer = []..