DFS , BFS
미로찾기 알고리즘 미로찾기 예제) 아래 그림과 같은 미로가 있다. 16*16 행렬의 형태로 만들어진 미로에서 흰색 바탕은 길, 노란색 바탕은 벽을 나타낸다. 가장 좌상단에 있는 칸을 (0, 0)의 기준으로 하여, 가로방향을 x 방향, 세로방향을 y 방향이라고 할 때, 미로의 시작점은 (1, 1)이고 도착점은 (13, 13)이다. 주어진 미로의 출발점으로부터 도착지점까지 갈 수 있는 길이 있는지 판단하는 프로그램을 작성하라. 아래 예시는 도착 가능한 경우 [입력] 각 테스트 케이스의 첫 번째 줄에는 테스트 케이스의 번호가 주어지며, 바로 다음 줄에 테스트 케이스가 주어진다. 총 10개의 테스트케이스가 주어진다. 테스트 케이스에서 1은 벽을 나타내며 0은 길, 2는 출발점, 3은 도착점을 나타낸다. [출력]..
2022. 8. 25.
2차원 배열
2차원 배열의 선언 : Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능 arr = [i for i in range(2, 9) if i % 2 == 0] # [2, 4, 6, 8 ] brr = [[1,2,3]] * 3 # [[1, 2, 3],[1, 2, 3],[1, 2, 3]] crr = [[i, j] for i in range(3) for j in range(2)] # [[0, 0],[0, 1],[1, 0],[1, 1],[2, 0],[2, 1]] 델타를 이용한 2차 배열 탐색 : 특정 원소의 상하좌우에 접근 -> 존재하지 않을 경우가 있으므로 index 체크 # 상하좌우 dy = [0, 0, -1, 1] dx = [-1, 1, 0, 0] 전치행렬 arr = [[1, 2, 3],[4, 5,..
2022. 8. 23.
1차원 배열
버블 정렬 : 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동 def bubbleSort(): for i in range(N-1, 0, -1): for j in range(i): if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] return arr arr = [0, 4, 6, 1, 3, 2, 5] N = len(arr) 카운팅 정렬 : 항목들의 순서를 결정하기 위해 각 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여 선형시간에 정렬하는 효율적인 알고리즘 1. 데이터에서 각 항목들의 발생 회수를 세고, 정수 항목들로 직접 인덱스 되는 카운트 배열에 저장 2. 카운트 배열의 누적합 구하기 3. 뒤에서부터 해당 인덱스의..
2022. 8. 23.
