본문 바로가기

전체 글159

검색 알고리즘 - (해시법) 휴 이번단원은 정말 코드를 이해하는데 며칠이 걸렸다. 평소에 짧고 쉬운 코드만 보다가 갑자기 이렇게 길고 어려운 코드를 보니 내가 파이썬을 배운게 맞나 싶을정도로 이해가 되질 않았지만 알고리즘을 이해하고 한줄한줄 천천히 살펴보니 어느정도는 이해가 된 것 같다. 앞으로는 이런 코드를 많이 볼텐데 빨리 적응을해서 쉽게 코드를 볼 수 있었으면 좋겠다. 해시법 해시법이란 파이썬의 리스트처럼 인덱스와 위치를 연결하는 것이다. 따라서 한번의 계산만 하면 되기 때문에 인덱스 값이 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.
알고리즘이란? 저번에 공부하던 알고리즘 책이 내 수준에 맞는것 같지 않아 보다 쉬운 책을 하나 더 구매했다. 다행히 지금까지는 충분히 이해할 수 있을 정도의 난이도였고 이전에 공부하던 책도 틈틈히 보며 알고리즘에 대해 더 자세히 공부할 예정이다. 문제1. 세 정수의 최댓값 구하기 a = int(input('정수 a의 값을 입력하시오 :')) b = int(input('정수 b의 값을 입력하시오 :')) c = int(input('정수 c의 값을 입력하시오 :')) max = a if b > max: max = b if c > max: max = c print(f'최댓값은{max}입니다.') 이 알고리즘은 간단하다. 처음 a를 최댓값으로 주어서 만약 b 가 a보다 크다면 b가 최댓값이 되는 것이고 c와 비교를 한 뒤 최.. 2022. 7. 15.
자료구조와 함께 배우는 알고리즘 출처 자료구조와 함께 배우는 알고리즘 카테고리에 있는 모든 글은 BohYoh Shibata 교수님의 '자료구조와 함께 배우는 알고리즘 입문 - 파이썬편 ' (이지스 퍼블리싱) 에서 정리 및 요약 간접 인용한 것임을 밝힙니다. 2022. 7. 14.
선형 자료구조 이번 책에서는 먼저 1장에서 코딩테스트의 기본에 대해 다루고 그 후에 파이썬, 3장부터 자료구조가 나와 책을 시작한지 조금 되었는데도 알고리즘이라는 카테고리에 맞지 않아 블로그 작성이 더뎌졌다. 하지만 이번 장 이후부터는 자료구조와 알고리즘 모두 계속 나오기 때문에 블로그 업로드 속도가 조금 빨라질 것 같다. 빅오 (Big-O) : 알고리즘의 효율성을 표기하는 표기법. 보통 알고리즘의 시간 복잡도(얼마나 빠른지) 와 공간 복잡도(메모리가 얼마나 사용되는지) 를 나타내는데 사용된다. → 입력값이 무한에 수렴할 때 (최악의 경우)알고리즘의 시간/공간 복잡도를 표기한다. 다음은 알고리즘의 효율성이 좋은 순서대로 나열한 빅오 표기법 이다. O (1) : 최상의 알고리즘이다. 입력값이 무한이더라도 항상 같은 시간.. 2022. 7. 14.

티스토리툴바