코딩공부66 (python) 7562 나이트의 이동, 7569 토마토 7562 나이트의 이동 https://www.acmicpc.net/problem/7562 문제 체스판의 길이와 시작위치, 도착위치를 주고 체스에서의 나이트로 최소 몇 번만에 도착할 수 있을지 묻는 문제이다. 입력 테스트 케이스 개수를 주고 그다음 체스판의 한 변의 길이 (체스판은 주어진 변수 * 변수가 크기가 된다.) 시작위치 x, y 도착위치 x, y 기본적인 그래프에서의 BFS를 사용하고 이동 좌표만 나이트에 맞추어 설정해 주면 된다. from collections import deque def bfs(): while queue: x, y = queue.popleft() for i in range(8): nx = x + dx[i] ny = y + dy[i] if 0 2023. 1. 19. (Python) DFS (깊이 우선 탐색) 백준 2606번(재귀함수 제한 해제) DFS (깊이 우선 탐색)한 노드와 연결된 모든 부분 먼저 탐색하는 BFS와 달리 DFS는 먼저 한 부분을 최대한 깊숙이 확인하고 돌아와 다른 부분을 탐색하는 것이다. 재귀호출이나 스택 배열을 이용하여 구현한다.2606번 바이러스https://www.acmicpc.net/problem/2606트리 형태 문제이며 dfs 기본 문제라고 할 수 있다. 연결되어 있는 컴퓨터 종류 알려준다. 바이러스가 감염되면 연결되어 있는 컴퓨터도 감염된다. 1번 컴퓨터가 감염됐을 때 감염되는 컴퓨터의 수를 출력하는 문제이다. DFS로 생각하면 1의 경우가 되는 부분만 탐색하면 된다. 입력 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크.. 2023. 1. 16. (Python) bfs(너비 우선 탐색) 백준 2178, 7576, 14502 bfs(너비 우선 탐색) 트리 구조나 그래프 구조에서 방문 탐색법이다. 큐를 사용하여 1. 시작점을 큐에 저장함 2. 시작점에 연결되어 있는 모든 자식 노드를 저장하고 차례로 방문 후 방문 처리 3. 2번 방법을 반복 4. 방문 가능 노드를 모두 방문했다면 탐색 끝 2178번 미로탐색 https://www.acmicpc.net/problem/2178 그래프 구조 중 기초 문제 N X M 구조 그래프 갈 수 있는 칸을 1, 갈 수 없는 칸을 0으로 주어지고 상하좌우로 이동하여 최소칸을 거치는 경우의 수 찾기 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. 시작점 (1, 1)에서 도착점인 .. 2023. 1. 16. (python) 이진 탐색(이분 탐색) ex 2110번 이진 탐색(이분 탐색)이란 컴퓨터과학, 수학 등에서 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 대부분 정렬되어 있는 수들에 대해서 타깃을 찾을 때 중간 부분(mid)을 기준으로 1. start와 end를 설정함 중간(start + mid) // 2를 기준으로 탐색 mid 타깃일 때 end를 mid값으로 하여 다시 탐색 즉 탐색 범위를 절반씩 좁혀가며 값을 탐색하기에 시간복잡도는 O(logN) 파이썬으로는 재귀함수나 반복문을 사용할 수 있고, 이진 탐색 라이브러리를 사용할 수도 있다.재귀함수 (low = start, high = end) d.. 2023. 1. 2. 백준 10844번 동적계획법 -python 얕은 복사와 깊은 복사 개념으로 import copy를 이용하여 해결할 수 있는 문제가 있어 들고 왔다. 단계별 풀어보기 동적계획법1에서 가장 낮은 정답 비율을 기록하고 있는 문제이다. 문제 https://www.acmicpc.net/problem/10844 45656이란 수를 보자. 이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다. 입력 첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 출력 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. 문제가 정말 짧게 설명되어있는데 짧다고 쉬운 것이 아니다. 풀이 먼저 .. 2022. 11. 21. 백준 25501번 문제 함수 호출 횟수 계산 -python 백준 문제 단계별로 풀기 중 재귀 단계에 있는 문제이다. 문제 자체는 재귀 함수를 주어주고 푸는 문제라 쉬운데 여기서 함수가 몇 번 호출됐는지 구하는 것이 나와 풀이도 기억할 겸해서 들고 왔다. 백준 25501번 https://www.acmicpc.net/problem/25501 정휘는 후배들이 재귀 함수를 잘 다루는 재귀의 귀재인지 알아보기 위해 재귀 함수와 관련된 문제를 출제하기로 했다. 팰린드롬이란, 앞에서부터 읽었을 때와 뒤에서부터 읽었을 때가 같은 문자열을 말한다. 팰린드롬의 예시로 AAA, ABBA, ABABA 등이 있고, 팰린드롬이 아닌 문자열의 예시로 ABCA, PALINDROME 등이 있다. 어떤 문자열이 팰린드롬인지 판별하는 문제는 재귀 함수를 이용해 쉽게 해결할 수 있다. 아래 코드의.. 2022. 11. 17. 이전 1 ··· 4 5 6 7 8 9 10 11 다음
