ajaaCoding

📌BFS너비 우선 탐색 (Breadth First Search)가까운 노드부터 탐색하는 알고리즘 BFS 구현에서는 선입선출 방식인 큐 자료구조를 이용하는 것이 정석인접한 노드를 반복적으로 큐에 넣도록하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색 진행 📌BFS 동작 방식1. 탐색 시작 노드를 큐에 삽입하고 방문 처리2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입 후 방문 처리3. 2번 과정을 더 이상 수행할 수 없을 때까지 반복  📌BFS 코드from collections import dequedef bfs(graph, start, visited): #큐 구현을 위해 deque 라이브러리 사용 queue=deque([..

📌DFSDepth-First-Search깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 📌그래프 표현 방식1. 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식2. 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식  위 그래프를 각 방식으로 표현한다면 다음과 같다 📌인접 행렬 방식2차원 배열에 각 노드가 연결된 형태를 기록하는 방식파이썬에서는 배열을 리스트 자료형으로 표현할 수 있으므로 인접행렬을 리스트로 구현함INF = 99999999 # 무한의 비용 선언# 2차원 리스트를 이용해 인접 행렬 표현graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0]]print(graph) 연결되어 있지 않은 노드끼..

📌재귀함수자기 자신을 다시 호출하는 함수DFS와 BFS를 구현하려면 재귀함수도 이해해야 함 📌재귀함수 코드def recursive_function(): print("재귀함수를 호출합니다.") recursive_function()recursive_function() 📌재귀함수의 종료 조건재귀함수의 종료 조건을 꼭 명시해야 함자칫 종료 조건을 명시하지 않으면 함수가 무한 호출 될 수 있음 📌코드def recursive_function(i): # 100번째 출력했을 때 종료되도록 종료 조건 명시 if i == 100: return print(i, "번째 재귀 함수에서", i + 1, "번째 재귀 함수를 호출합니다.") recursive_function(i +..

📌탐색많은 양의 데이터 중에서 원하는 데이터를 찾는 과정보통 그래프, 트리 등의 자료구조 안에서 탐색 📌탐색 알고리즘DFS, BFS이를 이해하기 위해서는 먼저 기본 자료구조인 스택, 큐에 대해 이해해야 함 📌오버플로, 언더플로오버플로: 자료구조에 데이터가 이미 가득 찬 상태에서 삽입 연산을 할 때 발생언더플로: 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 할 때 발생 📌스택박스 쌓기처럼 아래에서부터 위로 차곡차곡 쌓는 구조선입후출(First In Last Out) , 후입선출(Last In First Out) 구조 파이썬에서 스택을 이용할 때 별도의 라이브러리 사용할 필요 없음기본 리스트에서 append()와 pop() 메서드 사용 append(): 리스트의 가장 뒤쪽에 데이터 삽..

📌문제예제 4-4 게임 개발게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다.맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고 바다는 갈 수 없다. 매뉴얼1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다.2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면..

📌문제예제 4-3 왕실의 나이트8 x 8 체스판에 나이트가 서 있다. 나이트는 이동을 할 때 L자 형태로만 이동할 수 있으며 체스판 밖으로는 나갈 수 없다.1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오.이때 좌표의 행 위치를 표현할 때는 1~8로 표현하고, 열 위치를 표현할 때는 a~h로 표현한다. 📌풀이나이트의 이동 경로를 steps 변수에 넣는다면steps=[(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)] 나이트의 현재 위치가 주..

📌문제예제 4-2 시각 문제정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 📌풀이3중 반복문(시, 분, 초)을 사용하여 시각을 1씩 증가시키면서 3이 하나라도 포함되어 있는지 확인 00시 00분 00초부터 1초씩 늘리며 시, 분, 초를 문자열 자료형으로 변환하여 합침합친 문자열에 '3'이 포함되어 있는지 검사 📌코드h = int(input())count = 0for i in range(h + 1): # 0시 ~ h시 for j in range(60): # 0분 ~ 59분 for k in range(60): # 0초 ~ 59초 # 매 시각 안에 '3'이..

📌구현완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 유형 📌문제예제 4-1 상하좌우여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위의 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가는 상(U), 하(D), 좌(L), 우(R) 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. L, R, U, D로 이루어진 문자들이 적혀진 계획서를 보고 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.(단, N x N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다.) ..

📌문제예제 3-3 숫자 카드 게임여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임1. 숫자 카드가 N x M 형태로 놓여 있다. N은 행의 개수, M은 열의 개수를 의미2. 먼저 뽑고자 하는 카드의 행을 선택한다.3. 선택된 행의 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다. 📌풀이각 행마다 가장 작은 수를 찾은 뒤 그 중에서 가장 큰 수를 선택하는 방법 min 함수를 사용해서 각 행마다 가장 작은 숫자를 찾아냄이전 행에서 가장 작은 수와 현재 행에서 가장 작은 수를 비교해서 둘 중에 큰 값을 선택 📌코드n, m = map(int, input().split())result = 0# 한 줄씩 입력받아 확인for i in range(n): data = list(map..

📌문제예제 3-2 큰 수의 법칙다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만들어라. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 연속해서 더할 수 있는 최대 횟수 K 📌풀이 1(단순한 방법)가장 큰 수와 두 번째 큰 수만 저장가장 큰 수를 K번(연속으로 더할 수 있는 최대 횟수) + 두 번째 큰 수 1번 + ... 반복 📌코드 1# N, M, K를 공백으로 구분하여 입력받기n, m, k = map(int, input().split())# N개의 수를 공백으로 구분하여 입력받기data = list(map(int, input().split()))data.so..