프로그래머스 - Level2 멀리 뛰기 문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달...

프로그래머스 - Level2 N-Queen 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 문제 해석 4 * 4 체스판에서 퀸을 (0, 0) 지점부터 놓고, 그 다음에 놓을 수 있는 자리를 계속 찾아나간다. 그림으로 표현하면 다음과 같다. 현재 행에 퀸을 놓으면 현재 행에는 더 이상 퀸을 놓을 수 없으므로 다음 행에 ...

프로그래머스 - Level2 2 x n 타일링 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 처음에는 DFS 로 접근해서 모든 경우의 수를 탐색해서 풀었다. 모든 경우의 수를 구하기 위해서 1차원 배열을 사용하는 방법을 먼저 떠올렸다. 가로가 1 인 직사각형은 1 , 가로가 2 인 직사각형은 2 로 저장한다. n...

📌 동적 계획법 (Dynamic Programming) 이란? 동적 계획법은 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 작은 문제를 해결한 결과를 저장하여 큰 문제를 해결할 때 사용하는 문제 해결 패러다임이다. 🤷 동적 계획법이 필요한 이유? 일반적으로 재귀 함수의 불필요한 연산을 줄이기 위해서 동적 계획법을 사용한다. 재귀 함수도 ...

프로그래머스 - Level2 수식 최대화 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 다른 분들의 코드를 참고해서 작성했다. 연산자의 모든 조합을 생성한다. 연산자는 +, -, * 뿐이고, 생성 가능한 모든 경우의 수는 6가지다. 정규 표현식으로 연산자와 피연산자를 분리한다. ...

프로그래머스 - Level2 교점에 별 만들기 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 직선을 2개씩 조합하는 모든 경우의 수를 구한다. 각 조합마다 교점을 구한다. 교점을 구하는 공식에 따라 계산 계산 결과가 정수인 경우만 배열에 추가 2차원 배열에 교점의 위치...

프로그래머스 - Level2 삼각 달팽이 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 n = 5 일때, 다음과 같은 규칙을 발견할 수 있다. 아래 방향으로 끝까지 도달할 때까지 n 개의 수를 채운다. 오른쪽 방향으로 끝까지 도달할 때까지 n - 1 개의 수를 채운다. 위 방향으로 끝까지 도달할 때 까지 n...

다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘이다. 인공위성 GPS 소프트웨어 등에서 가장 많이 사용되는 알고리즘이다. 다익스트라 알고리즘은 특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 계산한다. 이때, 거리가 음수인 간선은 포함할 수 없다. 하지만, 현실 ...

프로그래머스 - Level2 배달 문제 설명 문제 설명 생략 🙋‍♂️나의 풀이 🤔문제 접근 다익스트라 알고리즘을 적용해서 풀었다. 그래프 문제는 처음이라 자료를 찾아가며 풀었다. 1번 마을에서 K 시간 안에 배달이 가능한 마을이 몇 개 있는지 구해야 한다. 주어진 시간 안에 이동하기 위해서는 최단 시간으로 이동하는 것이 좋기 때문에...

TL; DR DFS 는 스택과 재귀를 이용한다. BFS 는 큐와 반복문을 이용한다. 문제에서 요구하는 조건에 따라 DFS 나 BFS 둘 중 하나를 선택한다. 미로찾기 알고리즘이란? 미로찾기 알고리즘은 코딩 테스트에서 자주 등장하는 알고리즘이다. 시작 지점과 도착 지점이 주어지며, 탈출할 수 있는 경로를 출력하거나 탈출까지 걸리...