알고리즘14 백준_7562_나이트의 이동 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제요약) -> 나이트가 한번에 이동할 수 있는 칸 나이트가 이동하려고 하는 칸이 주어졌을 때, 몇 번의 이동으로 목적지에 도달하는가? 입력) 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1.. 2023. 4. 20. 백준_1697_숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 요약) 수빈이의 현재 위치가 N, 동생의 현재 위치가 K라고 했을 때, N -> K 몇 초 걸리나? (0 nx - 4, 6, 10 if 0 dist[17] ~> 4출력 bfs() #def로 정의한 bfs함수 실행, 출력 2023. 4. 19. 구현(Implementation) 구현의 정의 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. (구현 관련 설명을 찾다보면 이그림은 무조건 있다) 구현 유형의 문제? 알고리즘은 간단하나 코드가 길어지는 문제 실수 연산을 다르고 특정 소수점 자리까지 출력해야 하는 문제 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 2차원 배열(행렬Matrix)에서의 이동, 회전 등 까다로운 문제 특정한 라이브러리를 찾아서 사용해야 하는 문제 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 완전 탐색 유형 모든 경우의 수를 주저없이 다 계산하는 해결 방법이다. 시뮬레이션 유형 문제에서 제시한 알고리즘들을 한 단계의 차례대로 직접 수행해야 하는 문제이다. 코딩테스트에서의 구현 문제를 풀 때 알아야 할 것 메모.. 2023. 4. 11. 그리디(Greedy) 알고리즘 그리디 알고리즘의 정의 단어 그대로 번역하면 탐욕법인데 말 그대로 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 현재 상황에서지금 당장 좋은 것만 고른다. 지금 당장 가장 좋은 것만 고르기 때문에 현재의 선택이 나중에 미칠 영향에 대해 고려하지 않은 풀이를 한다. 그리디 알고리즘 원리 여러 경우 중 하나 선택한다. 선택시 마다 최적이라고 생각되는것을 선택한다. 최종적인 해답에 도달한다. 그리디 알고리즘의 특징 한번 선택된 것은 번복하지 않는다. → 대부분의 탐욕 알고리즘들은 단순하며, 제한적인 문제들에 적용한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로 최적이다. → 하지만 선택들을 계속 수집해 최종적 해답을 만들었다고 해서, 최적이라는 보장은 없다. 따라서 사용 가능유무를 잘 알아야 한다.. 2023. 4. 11. 이전 1 2 3 4 다음
