본문 바로가기

junior developer :)/알고리즘 & 코딩테스트20

[알고리즘]동적 계획법(Dynamic Programming/DP) 동적 계획법(Dynamic Programming) 동적계획법이란 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법을 말한다. 연산이 진행될 때 처음 진행되는 연산은 기억해두고, 이미 진행해서 저장이 되어있는 연산이라면 저장되어 있는 값을 가지고 오는 원리이다. 이렇게 미리 계산해서 저장해둔 결과를 활용해서 중복 연산을 줄이는 방식을 메모이제이션이라고 한다. 메모이제이션을 이용하면 중복되는 하위문제를 조금 더 효율적으로 해결할 수 있다. 모든 방법을 일일이 계산해서 최적의 해를 찾아내는 방식의 알고리즘이다. 그래서 시간이 오래걸린다는 단점이 있지만 최적의 해를 찾는데에 오류가 발생할 수 없다는 장점이 있다. 동적 계획법은 큰 문제를 작은 문제로 쪼개어 해결할 수 있어야 하고, 동일한 부분 문제가 여러.. 2023. 7. 27.
[프로그래머스]타겟 넘버(깊이/너비 우선탐색/JS) 예전에 깊이/너비 우선탐색을 공부했던 적이 있는데 어느정도 시간이 지난 후에 다시 하려니 머리가 새하얗다. 다시 감을 잡아봐야겠다 싶어서 문제 풀이를 해봤다. DFS/BFS DFS(Depth first search)는 깊이 우선 탐색으로 세로방향으로 자식노드를 먼저 탐색 후 다시 상위노드로 올라가서 BFS(Breadth first search)는 너비 우선 탐색으로 가로방향으로 형제 노드 먼저 탐색 후 자식노드로 내려간다. 전에 BFS/DFS를 정리했던 글을 참고했다. 알고리즘_깊이우선탐색(DFS),너비우선탐색(BFS) / JS 타겟 넘버 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, .. 2023. 7. 14.
[프로그래머스]완전탐색_모의고사(Level 1/JS) 오늘은 완전탐색 방법으로 풀이한 문제를 적어보려고 한다. 완전탐색은 말 그대로 모든 경우의 수를 완전하게 탐색해서 정답을 찾아내는 알고리즘 방법이다. 모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까.. 2023. 7. 13.
[프로그래머스]그리디(탐욕법)_조이스틱(Level 2/JS) 오늘은 그리디 알고리즘에 대해 적어보려고 한다. 그리디 알고리즘은 탐욕법이라고도 하며 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않고 현재 상황에서 지금 당장 좋은 것을 고르는 방법을 의미한다. 프로그래머스에서 해당하는 문제로는 Level 2 조이스틱 문제를 풀이해봤다. 조이스틱 문제 설명 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로.. 2023. 7. 11.
728x90
반응형

티스토리툴바