algorithm10 [JS] 프로그래머스 점찍기 https://school.programmers.co.kr/learn/courses/30/lessons/140107?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 풀이 문제를 조금 풀어서 설명 하자만 x,y 축에 k의 배수 씩 점을 찍을 건데 원점과 거리가 d를 넘으면 점을 찍지 않는 것! 문제 풀이의 핵심은 원점과의 거리를 구하는 것입니다. d^2 = x^2 + y^2 위 공식을 기반으로 점을 찍을 좌표가 원점과의 거리가 d 보다 크지 않으면 answer를 올려주면 됩니다. 주의 해야할 점은 d,k의 인풋이 최대.. 2023. 7. 30. JS로 BFS, DFS 구현 위 와 같은 그래프를 탐색하는 알고리즘은 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)으로 나뉩 니다. 위 그림과 같은 그래프를 탐색하는 알고리즘을 js로 구현해 보려 합니다. BFS 위 그림과 같이 너비를 우선으로 탐색 => 현재 정점에가 같은 deps에 있는 노드들은 먼저 방문한다는 뜻 탐색 중인 현재 노드에서 인접한 노드를 먼저 방문 최단 거리를 찾을 때 주로 사용 자료구조 queue를 사용하여 구현 DFS 방문할 수 있는 최대 deps를 우선적으로 방문 루트 노드에서 시작해서 해당 그래프의 최대 deps 까지 탐색, 더이상 탐색할 수 없다면 되돌아가 다시 최대 deps로 방문 stack 혹은 재귀 함수로 구현 가능 code const graph = { A: ["B", "D"], B: [.. 2023. 7. 19. 최장 공통 부분 수열(LCS) 최장 공통 부분 수열은 Longest Common Subsequence의 약자로 줄여서 LCS라고 한다. 우선 Subsequence와 Substring의 차이에 대해 알아야 한다. Substring이랑 부분 문자열로 공통 Substring을 구해야 한다면 공통된 연속하는 문자열을 구할 수 있어야한다. Subsequence는 부분 수열로 공통 Subsequence는 문자를 건너 뛰더라도 공통뒤는 문자 수열을 말한다. 최장 공통 부분 수열(Longest Common Subsequence) LCS를 구하는 방법은 다이나믹 프로그래밍 방식을 사용한다. 두 문자열이 있을 때 각 문자열의 인덱스를 하나 씩 방문하여 같은지 비교하여 값을 저장한다. 그림으로 이해하면 이해하기 쉬움 위 그림을 예시로 "ABCAB"라는 .. 2022. 2. 15. 퀵 소트(Quick Sort) 이름이 퀵소트지만 가장 빠른 정렬 방법은 아니다. 평균 시간복잡도는 O(N*logN) 이고 최악의 경우 시간복잡도는 O(N^2) 동작 원리: 특정 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한뒤에 배열을 나누는(분할)방법을 사용 여기서 특정 값을 pivot 값이라고 하는데 보통 첫 번째 원소를 pivot으로 설정하고 초기 시작을 한다. 동작을 풀어서 설명하면 피벗값을 설정한다 -> 왼쪽에서 부터 피벗값 보다 큰 숫자를 찾고 오른쪽에서 부터 피봇값 보다 작은 수를 찾는다. -> low 그러면 피봇값을 기준으로 2분할 되는데 각각 똑같이 quick sort를 수행해 주면 된다. 코드 : #include #include #include using namespace std; int arr[20]; void .. 2021. 10. 6. 병합정렬 (Merge Sort) 알고리즘 처음 배울 때 Merge Sort, Quick Sort에서 본격적으로 어려워 했던 기억이 난다. 재귀함수에 익숙하지 않으면 이해하기 어려운데 그림으로 천천히 따라가면 이해하기가 쉽다 분할 정복기법이라고 해서 - 분할 : 해결하기 쉽도록 문제를 여러개의 작은 부분으로 나눈다 - 정복 : 나눈 작은 문제를 각가 해결한다 - 통합 : 해결된 해답을 모은다 과정을 거치는 알고리즘이다 그림만 보면 어렵지 않은데 재귀적으로 호출 되고 정렬되고 합쳐진다는 개념이 생소했던 기억이 난다. divide(분할) 와 merge(합병) 두가지 함수로 구성되었는데 각각 살펴보면 void divide(int left, int right) { int mid; if (left < right) { mid = (left + ri.. 2021. 9. 24. 기수정렬 (Radix sort) 숫자의 각 자리 수는 0~9로 이루어져있기 때문에 자리 수 별로 정리한다고 생각하면 쉽다 1. 우선 일의 자리를 기준으로 해당하는 위치에 배열 후 정렬 2. 그다음 10의 자리 수를 기준으로 정렬 3. 위 과정을 반복하며 최고 자리수까지 정렬하면 된다. 위 그림을 보면 알수 있듯이 먼저들어온 수가 먼저 나가기 때문 queue자료구조를 사용하여 구현해 볼 것이다. 주의 해야할 점은 최대 자리수 보다 작은 자릿수 즉 최대자릿수가 1000일때 1~999 같은 세자리 수는 앞에 자리수를 0으로 계산해 줘야한다. #include #include #include #include #include using namespace std; int arr[20]; queue que[10]; void radixSort(int*.. 2021. 9. 15. 이전 1 2 다음
