분류 전체보기
-
[SW 정글 17일차] 오늘 배운 점들기타/SW 사관학교 정글 2021. 8. 18. 23:08
오늘은 지난 날들처럼 어떠한 주제를 잡고 정리하는 것이 아닌 알고리즘 문제를 풀면서 마주했던 오류를 해결하거나 코드를 바꿔보면서 알았던 내용을 정리하려고 한다. 1. TypeError: unhashable type: 'list' 위 에러는 list를 set으로 바꿀 때 나온 것이다. 정확히 말하면 list 안의 요소는 또 다른 list로 이루어져 있는 상태이다. 나는 list에 들어있는 원소들의 중복 제거를 하고 싶었고 for문을 돌리면서 조건문을 써도 되지만 set이라는 배열의 특징을 이용했다. set의 특징은 중복 원소를 허용하지 않는다는 것과 순서가 없다는 것(인덱스 접근 불가)이다. 그래서 중복 값이 들어있는 list를 set으로 형변환을 해준다면 자동으로 중복 값을 제거할 수 있다. 그래서 se..
-
[SW 정글 16일차] Locality는 무엇일까기타/SW 사관학교 정글 2021. 8. 17. 23:19
오늘은 컴퓨터 시스템 3판을 읽으면서 Locality라는 말을 접하게 되었고 설명이 없어 구글링을 하며 찾아본 내용들을 정리하려고 한다. 1 ~ 4주차는 알고리즘과 자료구조 공부기간이지만 1주일마다 컴퓨터 시스템 3판 읽을 분량을 정해준다. 엄청 어렵거나 세부적으로 파고드는 부분들이 아니여서 내가 이전에 배운 OS 지식을 리마인드하고 locality같은 개념이 확실히 잡히지 않은 용어를 정리해보는 시간으로 생각하며 책을 읽었다. 1. Locality란? 프로그램은 항상 메모리의 특정 주소를 찾아가서 데이터를 읽어오고 특정 주소로 찾아가서 데이터를 쓰는 행위들이 기본이다. 여기서 locality라는 개념이 적용되는데 locality는 프로그램이 data나 instructions를 사용하려고 할 때, 이전에..
-
[SW 정글 15일차] 세그먼트 트리기타/SW 사관학교 정글 2021. 8. 16. 23:14
오늘은 분할 정복 문제를 풀면서 다른 사람의 코드를 찾아보는 일이 많았다. 다른 사람들의 문제 풀이에 대한 설명에서는 세그멘트 트리라는 용어가 종종 보였고 이것에 대한 개념 자체가 없어서 오늘 공부한 것을 바탕으로 정리해보려고 한다. 1. 세그먼트 트리 (Segment Tree) 세그먼트 트리는 데이터의 합을 가장 빠르고 간단하게 구할 수 있는 자료구조로 여러 개의 데이터가 연속적으로 존재할 때 특정한 범위의 데이터의 합을 구하고자 할 때 사용한다. 세그먼트 트리를 쓰지않고 특정한 범위의 데이터의 합을 구할 때는 선형적인 방법을 사용할 것이다. 선형적인 방법이라 함은 어떠한 배열이 있을 때 인덱스 i ~ j까지 요소의 합을 구하려면 해당 범위의 요소를 하나씩 더해나가는 것이다. 이렇게 되면 시간복잡도가 ..
-
[SW 정글 14일차] 분할 정복기타/SW 사관학교 정글 2021. 8. 15. 23:00
1. 분할 정복 분할 정복은 주어진 문제를 원래 문제와 유사하지만 크기가 작은 몇 개의 부분 문제로 분할하고 부분 문제를 재귀적으로 풀고 찾은 해를 결합하여 원래 문제의 해를 만들어 내는 방법이다. 분할 정복으로 해결할 수 있는 예시는 하노이탑이 대표적일 것이다. 세 개의 기둥이 있고 n개의 원판이 있으면 규칙을 지키며 첫 번째 기둥에서 세 번째 기둥으로 옮겨야한다. 우리는 여기서 1 ~ n-1개의 원판을 두번째에 옮기고 n번째 원판을 세 번째 기둥으로 옮기고 마지막으로 1 ~ n-1개의 원판을 세번째 기둥으로 옮기면 문제가 해결된다. 즉, 전체 문제를 풀어해치는 것이 아닌 분할하여 재귀적으로 답을 얻어내는 것이다. 분할 정복은 세 가지 단계로 구성된다. ① 분할: 현재의 문제를 같은 문제를 다루는 다수..
-
[SW 정글 13일차] 트리 구조와 이진 트리기타/SW 사관학교 정글 2021. 8. 14. 23:47
1. 트리 구조 트리 구조는 데이터 사이의 계층 관계를 표현하는 자료 구조로 노드(node)와 가지(edge)로 구성되어있다. 간단한 트리 구조를 아래의 그림으로 표현해 보았다. 그림을 보며 각각의 단어들이 어떠한 것을 뜻하는지 알아보자. - 루트(root): 트리의 가장 위쪽에 있는 노드를 뜻하며 트리 하나에 루트는 오직 1개만 존재한다. - 리프(leaf): 리프는 자기 자신으로부터 더 이상 가지가 뻗어나가지 않는 노드를 의미한다. 리프는 다른 말로 단말 노드, 외부 노드라고도 한다. - 비단말 노드(non-terminal node): 비단말 노드는 트리 내에서 리프를 제외한 노드를 의미한다. 다른 말로 내부 노드라고도 한다. - 자식 노드(child node): 노드와 노드가 가지로 연결되어있을 때..
-
SW 정글 1주차 (하루 늦은)회고기타/SW 사관학교 정글 2021. 8. 14. 02:36
지난 4일차, 0주차를 마치고 주어진 특별한 과제를 할 겸 0주차 회고를 같이 작성했다. 이번에도 12일차에 1주차가 마무리되고 2주차가 시작되면서 1주차에는 어땠는지에 대해 작성하려고 했다. 12일차에 같이 쓰려고 했으나 내가 배운 내용들과 함께 글을 써보니까 내용이 너무 많아지고 글의 주제가 여러 개다 보니까 읽기 싫어지는 글처럼 보였다. 그래서 이렇게 각 주차별 회고는 따로 작성하려고 한다. [1주차 회고] 2021년 08월 12일 목요일, 오늘부로 SW 사관학교 정글에 들어온지 11일차, 1주차가 마무리 되고 2주차가 시작하는 날이다. 지난 주 목요일(08월 05일)에 나는 소규모 면담에 참여하여 운영진님들과 코치님에게 질문을 드렸다. Q. 전체적인 프로세스가 CS에 맞춰져있어서 기술적인 역량을 ..
-
[SW 정글 12일차] 스택과 큐 알아보기기타/SW 사관학교 정글 2021. 8. 13. 22:30
오늘은 스택과 큐에 대해 정리해보려고 한다. 스택과 큐가 대충 어떠한 성격의 자료구조인지는 알고 있었지만 세세하게 알아본 적은 없었다. 기본적인 자료구조인 만큼 내가 공부한 내용을 정리하며 개념을 제대로 잡고자 한다. 1. 스택 (stack) 스택은 데이터를 임시로 저장하는 자료구조로 후입선출(LIFO)방식이다. 후입선출(LIFO)은 먼저 들어온 데이터가 나중에 나간다는 의미이다. 이렇게 말로만 설명하면 감이 잘 안올텐데 프링글스를 생각해보자. 단, 깨진 짜잘짜잘한 조각들은 생각하지 않고 프링글스를 만들 때는 과자칩을 하나하나 통에 넣을 것이다. 이렇게 하나, 둘 쌓인 과자칩은 우리가 가게에서 사게 될 것이고 우리는 프링글스를 위에서부터 하나씩 꺼내서 먹을 것이다. 위에서부터 꺼내 먹게 되면 들어온 순서..
-
[SW 정글 11일차] 검색 알고리즘기타/SW 사관학교 정글 2021. 8. 12. 23:22
오늘은 2주차 시작으로 검색 알고리즘에 대해 공부를 시작했다. 검색 알고리즘에 대해 거의 모르다시피 살고 코딩테스트에서는 in 을 써서 값이 배열 안에 있는지 없는지 확인만 하는 수준이였다. 오늘부로 검색 알고리즘 개념을 잡고자 한다. 1. 선형 검색 (linear search) 선형 검색은 배열에서 원소를 검색하는 방법 중 가장 기본적인 알고리즘이다. 원하는 값을 찾기 위해 배열의 맨 앞부터 순서대로 확인하며 검색하는 것이다. 어떠한 방식으로 검색이 이루어지는지 아래의 그림을 보며 이해해보자. 배열의 맨 앞부터 순서대로 3인지를 확인하고 아니면 다음 원소로 넘어가면서 3인 원소를 찾았을 때 검색을 멈추게 된다. 선형 검색의 종료 조건은 2가지가 존재한다. - 찾고자하는 값을 찾지 못하고 배열의 맨 끝을..