개발놀이터

이번 포스팅에선 스택의 오랜 친구인 Queue (이하 큐)에 대해서 알아보는 시간을 가져보겠습니다. 우선 이번 포스팅에서는 큐에 대한 개념과 핵심 메서드에 대해서 알아보고, 그 이후에는 자바에서 제공하고 있는 구현체에 대해서 알아보고 마지막으로 큐가 thread-safe한지에 대해서 알아보겠습니다. Queue 자바에서 큐는 일반적인 도로와 같은 느낌입니다. 제일 먼저 들어온 것이 제일 먼저 나가는 구조이지요. 이것을 FIFO (First In First Out)라고 부릅니다. 큐의 일반적인 느낌은 위와 같습니다. 핵심 메서드 큐는 인터페이스인데요. 큐를 구현하는 모든 구현체들은 아래의 세가지 핵심 메서드를 포함해야합니다. offer() : 큐의 뒤쪽에 새로운 값을 삽입합니다. poll() : 큐의 앞쪽에..

이번 포스팅에서는 자료구조 중 가장 유명하다고 해도 과언이 아닌 스택에 대해서 알아보도록 하겠습니다. Stack 스택은 가장 전형적인 LIFO (Last In First Out) 구조로서 개발자들에게 사랑받는 자료구조 중 하나입니다. 스택이 사용되는 것은 가장 대표적으로 홈페이지의 뒤로가기 버튼과 ctrl + z인 undo 기능 계산기의 계산알고리즘 등이 있습니다. 하지만 요즘은 스택을 사용하기 보단 Deque (이하 데크)를 사용하는 것을 더 추천하긴 합니다. Deque는 Double Ended Queue의 약자로 상황에따라 해당 컬렉션을 스택으로 쓸 수도 큐로 쓸 수도 있는 인터페이스입니다. 데크는 LIFO 실행에 있어서 더 완벽하고 일관성있기 때문에 최근에는 스택 대신 사용하게 되었습니다. 하지만 ..

이번 포스팅에서는 자바의 컬렉션 프레임워크 중 하나인 Set에 대해서 알아보는 시간을 가져보도록 하겠습니다. 우선 자료구조 Set은 뭘까요? 음... 깊게 알고싶지 않다면 Set은 중복을 허용하지 않는 자료구조라고만 알고 계셔도 무방할 것 같습니다. 하지만 이번 포스팅에선 좀 더 깊은 내용을 다룰 예정입니다. HashSet을 사용하면 Hash값을 가지고 값을 찾을텐데 어떻게 중복을 방지하는 것인지, TreeSet은 어떤 알고리즘으로 정렬을 지원하는지. 이런 내용에 대해서 다룹니다. 들어가기 전에 말씀드리자면 자료구조 Set에 대한 전반적인 내용을 다루는 포스팅이기 때문에 사용방법에 대해서는 다루지 않습니다. 메서드에 대한 내용은 따로 알아보시는 것을 추천드립니다. Set Set은 데이터를 비순차적으로 저..

이번 시간에는 전 시간에 이어서 컴퓨터 사이언스에서 가장 사랑받는 자료구조 중 하나인 Tree에 대해서 알아보도록 하겠습니다. 이번 포스팅에서는 Tree의 개념, Tree 구조에서 가장 많이 사용하는 구조인 이진 트리, 이진 탐색 트리에 대해서 알아보도록 하겠습니다. Tree 트리의 구조는 위의 사진과 같습니다. 나무가 가지를 뻗듯이 데이터를 저장한다고 하여 붙여진 이름이 바로 트리입니다. 트리의 이러한 구조는 데이터의 저장보다는 저장된 데이터를 효과적으로 탐색하기 위해서 사용합니다. 따라서 Heap Space가 트리로 구현되어 있고, 컴퓨터에서 디렉토리를 분류할 때에도 트리 구조를 사용합니다. 트리의 개념에 대해 알아봤으니 용어를 알아보도록 하겠습니다. 루트 노드 (root node) : 부모가 없는 ..

컴퓨터 사이언스에서 대표적인 자료구조인 Hash는 key-value로 값을 찾는 알고리즘에 있어서 가장 빠른 속도를 보여줍니다. 때문에 많은 언어에서 Hash 자료구조를 구현해서 사용하고 있습니다. 이번 포스팅에서는 Hash는 무엇이고 어떻게 값을 찾는지, 자바에서는 어떻게 활용하고 있는지에 대해서 알아보도록 하겠습니다. Hash Hash란 무엇일까요? Hash는 특정한 숫자 혹은 문자 혹은 둘의 혼합으로 이루어진 key라고 생각하시면 됩니다. 보통 어떤 값은 Hash Function에 의하여 해쉬로 바뀝니다. 그리고 그 Hash를 key로 하는 저장 공간을 만들고 나중에 해당 값을 찾으려면 그 값의 Hash값을 대응해서 찾습니다. Hash Function은 key를 고정된 길이의 해쉬로 변경해주는 역할..

오늘은 알고리즘 문제에서도 많이 사용하고 실전에서도 많이 사용한다고 알려져있는 Map에 대해서 알아보도록 하겠습니다. Map 맵은 사전과 비슷합니다. people이란 단어에 "사람", baseball이란 단어에 "야구" 라는 뜻이 부합되듯이 Map은 Key와 Value라는 것을 한 쌍으로 갖는 자료구조입니다. Map은 리스트나 배열처럼 순차적으로 해당 요소 값을 구하지 않고 Key를 통해서 Value를 얻습니다. Map의 가장 큰 특징은 Key로 Value를 얻어낸다는 것입니다. people이라는 단어의 뜻을 찾기 위해서 사전의 내용을 순차적으로 검색하는 것이 아니라 해당 단어가 있는 곳만을 펼쳐보는 것이죠. 우리가 잘 아는 Map은 List와 마찬가지로 인터페이스입니다. Map인터페이스를 구현한 Has..

Two-Pointers-Algorithm two pointers algorithm (이하 투 포인터 알고리즘) 알고리즘은 말 그대로 포인터를 사용해 배열에 쉽게 접근할 수 있게 해줍니다. 자바에서도 배열에 쉽게 접근하기 위해 포인터를 사용하는 경우가 종종 있습니다. 보통 lt (left), rt (right) 혹은 s (start), e (end) 혹은 p1, p2 이런식으로 포인터를 정해서 값을 하나씩 증가시키면서 배열을 참조합니다. 투 포인터 알고리즘을 사용하는 문제는 비교적 자주 만나볼 수 있으며 한번 익혀두면 나중에 써먹기 정말 편하다고 합니다. 물론 저는 세번밖에 안써봤습니다. 먼저 문제를 확인해보시죠 문제를 해석하자면 N개로 된 수열에서 N개의 부분집합 중에서 M이 되는 개수가 몇개냐라고 물어..

이번 시간에는 코딩테스트 준비를 하면서 문제를 풀다가 흥미로운 알고리즘을 발견해서 해당 내용을 포스팅하려고 합니다. 바로바로 '에라토스테네스의 체' 라는건데요. 이번에도 흥미로운 내용이 있으니 한번 둘러보고 가세요! 에라토스테네스의 체란? 에라토스테네스의 체는 말 그대로 어떤 물질을 걸러주는 '체'를 의미합니다. 여기서는 소수를 걸러주는 체가 되겠네요. 소수에 대해서 아주아주 간단하게 설명하고 넘어가도록 하겠습니다. 소수는 1과 자기자신으로밖에 나눠지지 않는 수를 말합니다. 2 3 5 7 ... 이런 숫자들을 말하죠 1과 자기자신으로밖에 나눠지지 않는 수라는 것은 소수를 공부했던 사람이라면 누구나 떠올릴 수 있는 개념입니다. 이것을 코딩으로 구현하려면 어떻게 해야할까요? 정말 우리가 흔히 알고있는 개념으..

시간복잡도 시간복잡도란 내가 만든 코드가 얼마나 효율적인지를 나타내는 척도입니다. 시간복잡도를 계산하면 코드의 어느 부분에서 시간을 많이 잡아먹고 있는지 대략적으로 알 수 있으며 코드를 리팩토링 할 때도 좋은 영향을 미칠 수 있습니다. 문제를 해결하기 위한 알고리즘의 로직을 코드로 구현할 때 시간 복잡도를 고려한다는 것은 무슨 의미일까요? 바로 '입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마나 걸리는가?'를 고려한다는 의미입니다. 효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다는 의미입니다. 그리고 이 시간복잡도는 빅-오 표기법을 사용해 나타냅니다. 빅-오 표기법 빅-오 표기법 말고도 빅-오메가 표기법, 빅..