미로찾기 문제

문제의 의미미로찾기란 시작점에서 종료지점까지의 경로를 찾는 문제이다.아이디어시작지점에서 종료지점까지 가려면 현재지점에서 다음에 갈 수 있는 지점들을 탐색해야한다.그림에서 1은 벽으로 갈 수 없는 곳, X는 이미 지나온 곳, O는 갈 수 있는 곳이다. 현재지점이 종료지점인지 검사한 후, 아니라면 지나온 곳으로 표시하고 주변 지역들을 탐색할 곳으로 탐색리스트에 등록을 한다.탐색리스트에서 후보를 하나 꺼낸 후 종료지점인지, 종료지점이 아니라면 갈 수 있는 곳인지 여부를 확인하고 종료지점에 도달할 때까지 로직을 반복한다.설계while true 후리스트에서 후보 하나 꺼내기 if 종료지점 종료 if !벽 and !지나온 곳 지나온 곳 표시 주변 지역을 후보로 후보리스트에 등록후보리스트에 등록할 때 재귀호..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 11. 20.

순환과 반복

#1 정의어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다.#2 내부동작순환을 이해하기 위해서는 함수의 호출 과정을 이해하고 있어야한다. 함수가 자기 자신을 호출하는 것은 다른 함수를 호출하는 것과 과정이 동일하다.함수 호출내부 동작 실행실행 중 함수를 호출하게 됨해당 함수를 실행이하 생략…#3 알고리즘의 구조순환 알고리즘은 자기 자신을 순환적으로 호출하는 부분과 순환 호출을 멈추는 부분으로 구성되어 있다.def factorial(n:int): if n #4 순환과 반복반복이란 for, while과 같이 반복구조로 되풀이되는 방법이다. 순환은 순환적인 문제나 자료구조를 다루는 프로그램에 적합하다. 반복은 순환으로 순환은 반복으로 표현할 수 있다. 특히 순환이 꼬리 순환으로..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 28.

순차탐색과 정렬의 효과

순차탐색원하는 값이 존재하는 지 확인을 하기 위해 배열의 앞에서부터 뒤까지 탐색하는 과정이다. 값이 존재한다면 그 위치를, 없다면 -1을 반환한다.int SequentialSearch(int *arr, int n, int x) { for (int i = 0; i 배열의 정렬 시 순차탐색의 효율성배열이 정렬되어 있는 경우에 순차탐색을 더욱 빠르게 할 수 있다. 목표 값을 찾는 경우에 배열의 순회를 중단할 수 있기 때문이다.활용: 값의 개수 세기값의 개수를 셀 때 배열을 정렬한 후에 순차탐색을 하는 것이 효율적이다.int SequentialSearch(int *arr, int n, int x) { for (int i = 0; i = 0) return SortedCountHelper(a..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 24.

삽입정렬

개념삽입정렬은 배열을 정렬 된 영역과 정렬되지 않은 영역으로 본다. 정렬 된 영역의 옆에 붙은 원소를 정렬 된 영역을 앞에서부터 순회하면서 맞는 자리에 삽입하는 방식이다.작동방식오름차순으로 정렬할 때 작동방식은 다음과 같다. 인덱스 i에 있는 원소 a를 정렬할 차례일 때, 0 부터 i-1까지는 이미 정렬되어 있는 상태다. 정렬 된 영역의 원소를 하나씩 a와 비교하면서 a보다 크다면 shift를 하고 a보다 작다면 a를 삽입한다.동작과정파이썬def insertion_sort(my_list: list): for i in range(1, len(my_list)): key = my_list[i] j = i while j > 0 and my_list[j - 1] > ke..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 23.

다이나믹 프로그래밍

#1 동적 프로그래밍이란?① 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 ② 이를 재귀호출로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법이다.#2 문제의 조건최적하부구조부분문제들 간의 중복 존재최적하부구조큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있다.큰 문제와 작은 문제 간의 관계를 점화식으로 표현 가능하다.예: 펙토리얼 함수부분문제들 간의 중복 존재재귀호출로 문제를 해결할 때 중복되는 연산이 존재중복 연산에 의한 엄청난 비효율 발생#3 구현전략다이나믹 프로그래밍을 적용하는 방식으로 탑다운 방식과 버텀업 방식이 있다.탑다운 방식은 재귀호출을 사용하고 버텀업 방식은 재귀호출 대신에 반복문을 사용한다.양 방법 모두 중복되는 연산의 결과를 따로 저장한다.계산결과를..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 21.

추적값(pivot)을 활용한 분할 알고리즘

문제특정 값을 기준으로 배열을 두개의 영역으로 분할하려고 한다. 특정값을 pivot이라고 하자. pivot을 기준으로 pivot보다 작은 값들과 pivot보다 큰값들이 모인 영역으로 배열을 분할한다. 아이디어구현의 편의상 배열의 맨 끝 원소를 pivot으로 삼는다. pivot보다 작지만 가장 마지막에 배치 된 원소의 인덱스를 i, 배열을 순회하는 인덱스를 j, 배열의 첫번째 인덱스를 lo, 마지막 index를 hi라고 하자.포인터 j가 배열 전체를 순회한다.j가 가리키는 값이 pivot보다 작다면 i를 값을 1만큼 증가한 후에 j의 값과 교체한다. 교체 후에 j를 전진시킨다.j가 가리키는 값이 pivot보다 크다면 j를 전진시킨다.j가 pivot에 도달할 때까지 반복한다.j가 pivot에 도달하면 i +..

• format_list_bulleted 컴퓨터과학/자료구조와 알고리즘
• · 2024. 10. 15.