요세푸스 문제

요세푸스 문제란마지막 한명이 남을 때까지 규칙에 따라 자신들을 죽이는 문제다. 로마군이 패배 직전에 집단자살을 감행했을 때 살아남고 싶었던 요세푸스의 이름을 본따 만든 문제다.주어진 사람의 수에서 정해진 사람의 수가 뒤로 줄을 가게되고 그 후에 남은 사람이 자살한다.아이디어앞에서 사람들이 빠져서 뒤로 사람들이 줄을 서기 때문에 원형큐의 구조와 동일하다. 따라서 큐를 활용하여 문제를 푼다.구현while (q.Size() != 1) { for (int i = 0; i

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

1.1 정보는 비트와 컨텍스트로 이뤄진다

소스프로그램소스프로그램은 아래와 같이 표현된다.#include int main(){ prinf("Hello, world\\n"); return 0;}시스템 상에서 텍스트 파일의 형태로 저장된다.비트: 정보의 표현컴퓨터 시스템 상에서 모든 정보는 파일의 형태로 저장된다. 파일 내의 데이터는 0 또는 1로 표현된다. 0 또는 1로 표현되는 기본 단위를 비트라고 한다. 8개의 비트가 모이면 바이트다. 하나의 바이트는 아스키코드에 따라 텍스트 문자 하나에 대응될 수 있다. 따라서 모든 파일은 비트로 표현된다.컨텍스트: 정보의 구분파일의 종류와 무관하게 정보는 비트로 기록된다. 하지만 동일한 비트라도 해석을 적용하는 기준에 따라 의미가 달라진다. 이때 해석을 적용하는 기준을 컨텍스트라고 한다.gamsahabnid..

• format_list_bulleted 컴퓨터과학/컴퓨터구조
• · 2024. 11. 20.

1장. 컴퓨터 시스템으로의 여행

왜 배우는가?컴퓨터는 하드웨어와 소프트웨어의 조합이다. 각 구성요소를 컴포넌트라고도 한다. 컴포넌트들의 상호작용이 프로그램의 정확성과 성능을 결정한다. 따라서 개발자는 효율적인 프로그램을 작성하기 위해서는 컴퓨터 구조에 대한 이해가 필요하다.어떻게 배우는가?프로그램의 생명주기를 추적하고 이해하면서 시스템에 대한 개념, 용어들을 학습한다. 책에서는 hello 프로그램이 텍스트 파일로 생성 된 후에 컴퓨터가 실행하기까지의 과정을 소개하면서 관련 개념들을 설명한다.#include int main(){ prinf("Hello, world\\n"); return 0;}

• format_list_bulleted 컴퓨터과학/컴퓨터구조
• · 2024. 11. 20.

하노이탑 문제

하노이탑 문제란큰판이 작은판보다 반드시 아래에 배치되어야하는 규칙을 지키면서 탑을 한 지점에서 다른 지점으로 옮기는 문제이다.아이디어하노이탑 문제는 분할정복 기법으로 접근하여 풀 수 있다. 즉, 하나의 큰 문제를 여러개의 작은 문제로 쪼개어서 풀 수 있다.설계# 디스크 옮기기def move(from, to): disk = tower[from].top() tower[from].pop() tower[to].push(disk)# 하노이 탑 옮기기def hanoi(n, from, temp, to): if n == 0: return hanoi(n -1, from, to, temp) move(from, to) hanoi(n -1, temp, from, to) 하노이탑 문제는 세개의 작은 문제로 쪼갤 수 있다.① ..

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

미로찾기 문제

문제의 의미미로찾기란 시작점에서 종료지점까지의 경로를 찾는 문제이다.아이디어시작지점에서 종료지점까지 가려면 현재지점에서 다음에 갈 수 있는 지점들을 탐색해야한다.그림에서 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.