알고리즘5 [BOJ 7562 파이썬] 나이트의 이동 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1.. 2022. 7. 3. [Programmers 파이썬] 메뉴 리뉴얼 DFS 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성.. 2022. 7. 2. [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 의 개념과 차이 알고리즘을 풀다보면 그래프를 탐색해야하는 상황이 많이 발생한다. 그래프를 탐색하는 방법에는 크게 깊이 우선 탐색 (DFS)과 너비 우선 탐색 (BFS)가 있다. 두개의 알고리즘을 그림으로 보면 다음과 같다. 1. 깊이 우선 탐색 (DFS) ✅ 깊이 우선 탐색의 개념 한 노드로 부터 시작해서 다음 분기(다른 경로)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 예를 들어서, 미로찾기를 한다고 가정해보자. 최대한 한 방향으로 가다가 해당 방향의 막다른 길에 다다랐을때, 다시 갈림길로 돌아와서 다른 경로를 똑같이 탐색하고, 이를 탈출구를 찾을 때까지 반복하는 것이 바로 DFS 깊이 우선 탐색이다. 그런데, 만약 잘못 선택한 경로가 올바른 경로에 비해 매우 깊은 (시간이 많이 걸리는) 경로라면?.. 2022. 6. 27. [알고리즘] 브루트포스(brute force) 기법 정리 Goal 1. 브루트포스 알고리즘이 무엇인지에 대하여 정확히 이해한다. 2. 브루트포스 알고리즘이 쓰이는 문제의 종류에 대하여 정리한다. 브루트포스(brute force) 알고리즘이란? 브루트포스 알고리즘이란, 완전 탐색 알고리즘을 말한다. 즉, 가능한 모든 경우의 수를 탐색하면서 조건문을 통해서 요구조건이 충족되는 결과를 도출해 낸다. 모든 경우의 수를 탐색한다 -> 예외 없이 100%확률로 답을 가져올 수 있다. - 알고리즘 설계의 가장 근본적인 방법은 해가 있을 곳을 예상해서 탐색하는 것이다. - 브루트포스 알고리즘은 전체 구역을 탐색한다. - 전체 구역을 탐색하는 방법은 선형구조를 전체 탐색하는 순차 탐색 (반복문을 통한 전체 순차 탐색), 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), .. 2022. 2. 23. 이전 1 2 다음
