목록자료구조 & 알고리즘 (39)

FE PARADISE

프로그래머스 땅따먹기 - 자바스크립트 풀이(Bottom-up DP사용)

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.예를 들면,| 1 | 2 | 3 | 5 || 5 | 6 | 7 | 8 || 4 | 3 | 2 | 1 |로 땅이 주어졌다면,1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.마지막 행까지 모두..
자료구조 & 알고리즘 2025. 4. 21. 22:25
분할정복 알고리즘 - 큰수 곱셈

두 수를 곱할 경우 우리는 그 두 수의 각자리수를 곱하고 덧셈한다.만약 두 수 가 큰 수라면 연산 횟수가 많아져 O(n^2)의 시간이 걸린다.이 문제를 해결하는 것이 바로 카라바츠 알고리즘 이다.카라바츠 알고리즘분할정복으로 큰 두수의 곱셈을 처리한다. 일반적인 두 수 A와 B의 곱셈을 나타내어보자. 두 수의 자릿수가 n인 경우,m = n / 2 ( 자릿수의 반)A = a1 * 10 ^ m + a0B = b1 * 10 ^ m + b0A * B = (a1 * 10 ^ m + a0) * (b1 * 10 ^ m + b0) = a1*b1*(10 ^ 2m) + a1 * (10 ^ m) * b0 + a0*b1*(10^m) + a0*b0= a1*b1*(10^2m) + (a1*b0 + a0*b1) * (10^m) + a..
자료구조 & 알고리즘 2025. 4. 19. 22:08
[자료구조] 힙 Heap - 자바스크립트로 구현하기

힙 Heap이진 트리(binary tree)의 일종으로 항상 완전 이진 트리 형식을 유지한다. 완전 이진 트리란 왼쪽 노드부터 차례대로 값이 채워지는 형식이다. 부모와 자식 노드의 값 크기에 따라 최대 힙과 최소 힙으로 나눠진다.최대 힙 (Max Heap)부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우. 상위 노드(root)가 제일 큰 값을 가짐.최소 힙 (Min Heap)부모 노드의 값이 자식 노드의 값보다 작거나 같은 경우. 상위 노드(root)가 제일 작은 값을 가짐.사용 예제 우선순위 큐 (ex: 처리 순서가 정해진 작업)다익스트라(Dijkstra) 알고리즘 (최단 경로 구하기)힙 정렬 (Heap Sort) 예시[9, 7, 6, 5, 4, 3, 2, 1] 배열을 heap으로 나타내 보자.해..
자료구조 & 알고리즘 2025. 4. 13. 21:58
프로그래머스 뒷 큰수 스택 풀이 - 자바스크립트 풀이

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr레벨2 도장깨기 중에 만난 문제인데 여태 풀었던 레벨2 중에 제일 풀기 힘들었던 문제였다. 이게 레벨2 맞나...?안 어렵다고? ㅇㅇ 축하한다.사실 이번 문제는 내 힘으로 못 풀었다. 질문하기 힌트보고 겨우 풀었다. 자수한다. 이제 풀이 들어간다.stack을 사용하여 문제를 풀라는 힌트에 한 10분 동안 뇌가 정지되었다. 스택을 어디에 어떻게 사용하란건지처음에 for문과 while문으로 막힘없이 슉슉 작성하고 O(n*n)의 시간복잡도와 함께 시간 초과를 맛보고 온 후 머리가 더 굴러가지 않았다. 휴 😮‍💨 stack을 이용하여 문제를 풀어보자.let st..
자료구조 & 알고리즘 2025. 3. 8. 16:53
이전 Prev 1 2 3 4 ··· 10 Next 다음