# A Maze Problem - 목표: 입구로부터 출구까지의 경로를 찾음 - 조건: 0은 지나갈 수 있고, 1은 지나갈 수 없음. 직진이나 대각선 방향으로 이동이 가능 > 한 개의 프로그램은 한 개의 미로 경로를 탐색 > 현재 위치에서 이동 가능한 모든 방향 (북쪽부터 시작 → 시계방향으로 이동) 대하여 이동 가능 여부 판단 > 처음 발견한 이동 방향으로 마우스의 좌표를 수정 > 이동 가능한 방향이 없을 경우, 이전 위치로 되돌아감 > 스택을 이용하여 이동했던 위치를 기록하고 이전 위치로 찾아감. 만일 백 트랙을 시도했으나 스택이 비어있다면 결과는 실패 # 미로 찾기 스택 구현 - 구현: 경우의 수를 진행할 때는 스택 안에 쌓고, 벽에 막히면 pop하여 이전 단계까지 돌아옴 # 미로 문제의 특성 - a..

자료구조 개념 및 구현 Chapter 4. 알고리즘 분석 - 연습문제 Q1. 점근적 표기법(asymptotic notation)을 사용하는 이유를 적으시오. - 알고리즘의 성능을 비교하기 위해 사용함. 입력의 수가 매우 커질 때, 알고리즘의 복잡도가 증가하는 패턴을 살펴봄 Q2. 시간 복잡도와 공간 복잡도는 각각 무엇을 의미하는가? - 시간 복잡도: 프로그램이 수행을 완료하는데 걸리는 시간 - 공간 복잡도: 알고리즘 실행에 필요한 메모리 Q3. 시간 복잡도에 대한 점근적 표기법의 세 가지 종류를 각각 설명하시오 - 상한선(Big-Oh) 표기법: 시간 복잡도 함수 f(n) = Ο(g(n))이라고 표기할 수 있다면, 이 알고리즘의 수행 시간은 상한선 c·g(n)을 넘지 않는다는 의미 - 하한선(Big-Ome..

# 알고리즘의 성능 분석 - 설계된 프로그램의 구현이 완료될 때 프로그램 성능 평가 과정이 수행됨 - 프로그램은 여러 개의 알고리즘으로 구성될 수 있으므로 알고리즘의 성능 평가라고 부를 수 있음 - 일반적인 성능 평가 질문의 예: 기준이 모호하고 구체적이지 않으므로 객관적인 평가 방법으로 사용하기에 적합하지 않음 더보기 · 프로그램이 본래의 요구 사항들을 만족하고 있는가? · 오류 없이 올바르게 동작하는가? · 효율적으로 구현되었는가? - 실행 가능한 성능 분석 기준: 공간 복잡도(space complexity), 시간 복잡도(time complexity) - 실행 가능한 성능 분석 기준은 알고리즘 간의 성능 비교가 가능함 → 측정 가능한 구체적인 수치를 제공하기 때문 # 공간 복잡도(Space Comp..

# 소프트웨어와 자료구조 - 자료: 측정되거나 수집된 값의 모음 → 한 가지 데이터로 다양한 문제 해결 가능 - 정보: 수집된 데이터를 분석하여 새롭게 알아낸 사실 - 알고리즘: 주어진 문제 해결에 필요한 절차를 체계적으로 구성해 놓은 명령어 - 프로그래밍: 프로그램을 설계, 구현하는 작업 - 컴퓨터 과학: 컴퓨터 하드웨어만을 다루지 않으며 컴퓨터를 활용하여 주어진 문제를 해결하기 위한 소프트웨어 이론과 방법에 대해 연구하는 학문 > 목표: 주어진 문제를 해결하기 위한 절차인 알고리즘을 개발하는 것 - 자료구조: 프로그램을 통해 다량의 데이터를 효과적으로 저장, 관리, 처리하기 위해 사용되는 구조체 및 방법론 Linear Data structures Array, Stack, Queue Non-Linear..