개발자 블로그

컴퓨터에서 숫자를 기억하는 방식은 2진수 즉, 0과 1로만 모든 것을 표현한다. 이 때문에 오는 오차가 있어 사용 시 주의해야할 상황이 있는데 이는 float 타입을 사용할 때이다. 예를들어, 0.1이라는 숫자를 컴퓨터가 저장하는 방식은 이진수로 나타낸다면, 무한히 반복되는 숫자가 되버린다. 하지만 컴퓨터는 이러한 수를 근삿값으로 저장한다. 떄문에 정확한 값을 저장하지 않는다는 말! 이러한 문제를 해결하기 위해 파이썬에서는 decimal.Decimal, round() 등 여러가지 메소드를 통해 부동소수의 한계를 해결하는 방법 등이 있긴하다. 하지만, 이 또한, 완벽히 문제를 해결하는 방법이 아닐 수도 있으니, 사용할 시 주의하고 상황에 맞는 방법을 활용하도록 하자! 결론, 정확한 소수점 계산을 해야할 때..

DFS # 위의 그래프를 예시로 삼아서 인접 리스트 방식으로 표현했습니다! graph = { 1: [2, 5, 9], 2: [1, 3], 3: [2, 4], 4: [3], 5: [1, 6, 8], 6: [5, 7], 7: [6], 8: [5], 9: [1, 10], 10: [9] } visited = [] # 방문한 걸 저장하기 위한 배열 1. 우선 탐색 시작 노드를 1로 잡겠습니다! 2. 현재 방문한 노드인 1을 visited 에 추가합니다. # visited -> [1] 3. 인접한 노드들인 [2, 5, 9] 에서 방문하지 않은 것들은 [2, 5, 9] 입니다. 2 에 방문합니다. 4. 현재 방문한 노드인 2을 visited 에 추가합니다. # visited -> [1, 2] 5. 인접한 노드들인 [..

컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 데이터를 다루는 기법 중에 하나로 데이터의 검색과 저장이 아주 빠르게 진행된다. 해쉬 자료구조는 파이썬에서 딕셔너리와 같다. key값으로 빠르게 해당하는 value를 찾고 저장할 수 있는 자료구조이다. key와 매핑된 벨류를 반환하기 때문에 모든 배열을 돌아보지 않고 조회가 가능하므로 상수 시간의 시간 복잡도를 갖고 있다. 알고리즘 문제를 풀다보면 시간 복잡도를 줄이기 위해 index()라는 함수보다 딕셔너리로 값들을 저장하곤 한다. 하지만 딕셔너리도 다소 메모리가 더 잡히는 부분 때문에 이러한 부분도 ..

Array vs LinkedList 상황 Array LinkedList 특정 원소 조회 O(1) O(N) 원소 삽입, 삭제 O(N) O(1) 원소 추가 데이터 추가 시 공간이 찼다면 새로운 메모리를 할당 받아야한다. 모든 공간이 차도 맨뒤에 노드만 동적으로 추가한다. 정리 데이터 조회가 빈번하다면 Array! 삽입과 삭제 또는 데이터 추가가 빈번하다면 LinkedList! *그렇다면 파이썬의 경우 리스트는 링크드 리스트인가? pyhton의 리스트는 array로 구현되어 있다. 하지만 append의 경우 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1)의 시간 복잡도가 걸리도록 설계가 되어있다. 따라서 python의 배열은 링크드 리스트로 쓸 수 있고, 배열로도 쓸 수 있게 만든 효..