본문 바로가기

전체 글135

재귀 알고리즘 (2) - (하노이의 탑, 8퀸 문제) 하노이의 탑 하노이의 탑은 큰 원판이 작은 원판 위로 올 수 없다는 규칙을 가지고 있으며 모든 원판을 지정한 기둥으로 옮기면 되는 문제이다. 이 문제의 해결법은 아래 그림과 같이 가장 큰 원판을 제외한 모든 원판을 2번째 기둥에 놓고 가장 큰 원판을 목표 기둥에 놓으면 된다. 그렇게 된다면 중간 기둥에 큰 원판을 제외한 다른 원판을 쌓는 과정이 문제가 된다. 하지만 다시 생각해보면 이 과정도 중간 기둥을 목표 기둥이라 놓고 가장 큰 원판을 목표기둥(2번째 기둥) 에 놓기만 하면 된다. 이렇게 점차 줄여나가면 결국 하노이의 탑 문제를 풀 수 있는 것이다. 아래는 하노이의 탑 코드이다. def move (no, start, target): if no > 1: move(no - 1, start, 6 - sta.. 2022. 7. 27.
재귀 알고리즘 (1) 이번 단원은 정말 생각보다 많이 어려웠다. 어제 나름 집중도 잘하고 열심히 공부했다고 생각이 들었음에도 완벽히 이해하지 못해 오늘까지 시간이 필요했다. 재귀의 개념을 이해하더라도 코드를 어떻게 구현하는지, 실행과정이 어떻게 되는지를 알아야하기 때문에 상당한 시간이 필요했지만 앞서 먼저 공부한 친구의 도움을 빌려 어찌어찌 잘 해낸것 같다. 재귀 알고리즘 재귀란 어떠한 함수 또는 행동에서 자기 자신을 포함하고 다시 자기 자신을 사용하며 그로 인해 작업을 수행하는 것을 말한다. 하지만 자기 자신을 무한히 참조하기 때문에 무한 루프에 빠지지 않으려면 반드시 제어문이 필요하다. 일상생활 속에서 컴퓨터 화면이 자신의 화면을 출력한다면 그 출력물에서도 아래 사진과 같이 또 다른 자신의 화면을 호출할 것이다. 이것이 .. 2022. 7. 27.
스택과 큐 이번 단원은 OS 에서 배웠던 기초 지식이 있었던 탓인지 코드가 길어도 이해하기 쉬웠고, 코드를 읽으며 이해가 바로바로 되니까 재미가 붙었던 단원이다. 그랬던 탓인지 딱히 궁금증이 생기거나 막히는 부분 없이 무난하게 잘 공부했던 것 같다. 스택 스택이란 데이터를 임시저장하는 자료구조로서 후입선출 (LIFO : Last In First Out) 방식을 띄고있다. 한마디로 가장 먼저 들어간 데이터가 가장 마지막에 나온다는 뜻이다. 스택에서 데이터를 넣을 때 쓰는 용어는 푸시 (PUSH), 데이터를 꺼낼때는 팝 (POP) 이라고 한다. 스택을 구성하는 코드는 다음과 같다. from typing import Any class FixedStack: class Empty(Exception): # 비어있는 스택에 팝.. 2022. 7. 25.
검색 알고리즘 - (해시법) 휴 이번단원은 정말 코드를 이해하는데 며칠이 걸렸다. 평소에 짧고 쉬운 코드만 보다가 갑자기 이렇게 길고 어려운 코드를 보니 내가 파이썬을 배운게 맞나 싶을정도로 이해가 되질 않았지만 알고리즘을 이해하고 한줄한줄 천천히 살펴보니 어느정도는 이해가 된 것 같다. 앞으로는 이런 코드를 많이 볼텐데 빨리 적응을해서 쉽게 코드를 볼 수 있었으면 좋겠다. 해시법 해시법이란 파이썬의 리스트처럼 인덱스와 위치를 연결하는 것이다. 따라서 한번의 계산만 하면 되기 때문에 인덱스 값이 1인 값을 구하는 과정과 인덱스값이 100,000인 값의 차이가 없다는게 장점이다. from __future__ import annotations from typing import Any, Type import hashlib class No.. 2022. 7. 24.
검색 알고리즘 - (이진 검색) 이번 글에서 해시법과 이진검색을 같이 포스팅하려 했지만 해시법을 공부하는데 시간이 많이 소요될 것 같아 이진검색 따로 먼저 포스팅 하려한다. 이진검색을 업다운 게임을 예로 들자면 업다운 게임도 원하는 값을 최대한 적은 횟수로 찾아내는 것이다. 그럴 때 가장 좋은 방법은 범위의 중간값을 계속해서 물어보는 것이다. 이번 단원은 이러한 원리를 잘 알고 있으면 이해하는데 큰 어려움은 없을 것 같다. 이진검색 이진검색이란 데이터가 정렬 된 상태에서 선형 알고리즘보다 빠르게 검색할 수 있는 알고리즘이다. 앞서 쉽게 설명을 했었는데 다시한번 정확히 개념을 설명하자면 배열이 정렬된 상태에서 원하는 값과 배열의 중간값을 비교해본다. 이 때 중간값과 같지 않다면 대소비교를 통해 범위를 점점 좁혀나가는 것이다. 다음은 실행.. 2022. 7. 22.
검색 알고리즘 - (선형 알고리즘) 이제 정말 알고리즘에 대해 시작하는 느낌이다. 선형 알고리즘이 가장 기초가 되는 방법인 것 만큼 크게 어렵지 않아 쉽게 공부할 수 있었다. 이해가 안되는 코드도 단원을 마치고 다시 생각해보니 크게 어려웠던 내용이 아니고 내가 이해를 못했었던 것 같다. 앞으로도 초심을 잃지말고 지금처럼만 공부를 하면 좋은 코드를 만들 수 있는 사람이 될 수 있을거라고 생각을 하며 공부해야겠다. 선형 알고리즘 선형 알고리즘이란 검색값(key)을 배열의 0번 인덱스부터 마지막까지 찾아보는 알고리즘이다. 배열의 모든 인덱스를 하나하나 찾아보기 때문에 알고리즘 자체의 효율성은 좋지 않을 수 있지만 간단하고 확실하기 때문에 많이 사용되기도 한다. 다음은 선형 알고리즘의 코드이다. # while 을 이용한 선형 알고리즘 def se.. 2022. 7. 21.
기본 자료구조와 배열 이번 장에서는 자료구조의 정의와 자료구조의 기본형인 배열에 대해 알아보았다. 배열은 그동안 공부했었던 모든 책에서 한번 이상은 다뤄보았기 때문에 개념에 대해서는 쉽게 이해할 수 있었지만 배열의 알고리즘이 나온 이후로 머리가 너무 아프다. 나는 문제를 먼저 내가 한번 풀어보고 책에서는 어떻게 풀었는지 내 코드와 비교해가며 공부하고있는데 정말 내가 생각하지 못했던 방법이 이렇게 많고 내가 만든 코드는 정말 초라하다는 생각이 많이 들었다. 빨리 실력이 늘어 어려운 알고리즘 문제도 쉽게 풀 수 있는 안목이 생겼으면 좋겠다. 1. 자료구조와 배열 자료구조란 여러개의 값을 하나의 변수 안에 저장해 놓을 수 있어서 코드를 쉽고 효율적으로 작성할 수 있다. 대표적인 자료구조의 형태는 배열이 있다. 배열은 변수의 개수를.. 2022. 7. 21.
반복하는 알고리즘 (2) 문제 6. 특정 수가 나오면 중단하는 프로그램 import random n = int(input('난수의 개수 입력 :')) for i in range (n): r = random.randint(10,99) print(r, end=' ') if r == 13: print('\n프로그램 종료') break else : print('\n난수생성 종료') 파이썬의 라이브러리인 random 을 이용해 랜덤한 수를 만드나 특정 수 (8) 가 나오면 자동으로 종료되는 프로그램이다. 이 때 프로그램 종료와 난수 생성 종료 2가지가 있는데 난수 생성 종료는 n가지를 전부 실행하고 종료하는 것이고 만약 n 가지를 실행 하던 중 13이 나오면 바로 종료되는 것이 프로그램 종료 (break) 이다. 문제 7. 특정 수를 건.. 2022. 7. 18.
반복하는 알고리즘 (1) 알고리즘을 잘 이해하기 위해서는 정말 문제를 많이 풀어봐야 하는 것 같다. 문제를 많이 풀어보면서 비슷한 유형의 문제가 나오면 풀었던 기억을 돌아보며 그 알고리즘에 대입하는 것도 좋은 방법이지만 새로운 방식을 이용하여 가장 좋은 알고리즘을 생각해내는 창의성인것 같다. 문제 1. 1부터 n까지 정수의 합 구하기 n = int(input('n값 입력 : ')) sum = 0 for i in range(1,n+1): sum += i print(f'{sum}입니다') 이 방법은 내가 풀었던 방법이였는데 책에는 while을 이용한 방법도 있었다. 이 문제는 반복문의 기초를 배우기 위한 문제인것 같으므로 패스하겠다. ㅋ 문제 2. 연속하는 정수의 합 구하기 # 책에서 나온 코드 print('a부터 b까지 정수의 합.. 2022. 7. 15.

티스토리툴바