팔랑귀 블로그

이진 탐색 알고리즘 (Binary Search Algorithm) 우리가 특정 값을 찾을 때 자료를 확인해서 특정 값에 도달하는것을 탐색이라고 한다. 만약 임의의 숫자를 지정해 놓고 찾으라고 한다면, 0부터 1, 2, 3..... 순으로 계속 확인 한다고 하자 이 경우 통상적인 숫자 (적당한 숫자, 100 이하라고 하자) 인 경우 금방 답이 나오겠지만, 높은 숫자 (100000....)의 경우에는 굉장히 오랜 시간이 걸릴 것이다. 탐색 알고리즘은 특정 값을 찾는데 걸리는 시간을 줄이면서 우리가 원하는 값을 내놓기 위해 만들어졌다. 이진 탐색 알고리즘은 앞에서 예를 든 숫자 업다운 과 동일하다고 보면 된다. 만약 5~200까지 숫자 중 182를 찾는 경우라고 생각해 보자 위의 그림에서 5~200 범위의 숫..

완전 탐색 알고리즘 (부르트포스 / Brute-Force Algorithm) 부르트포스 알고리즘은 단순하게 특정 값을 구하기 위해 가능한 값을 처음부터 끝까지 다 넣는것이라고 보면 된다. 예를들어 자물쇠 번호를 잊어버렸을 때, 자물쇠 버튼을 000~999까지 눌러보면서 맞는 숫자 나올때 까지 돌리는 것과 비슷하다. 자물쇠 버튼 누르는건 내 손의 빠르기에 달려있는 것 처럼, 부르트 포스 알고리즘은 컴퓨터의 성능에 달려 있다. 모든 가능성을 시도해서 답을 찾아내는 것이기 때문에 공간복잡도(알고리즘 구현하는데 사용되는 메모리 크기)와 시간 복잡도를 신경쓰지 않는다. 부르트포스를 쓰는 이유는 앞서 특정한 값을 찾거나 할 때 최악의 경우의 수시행 하더라도 답을 찾기 위해 사용된다. 부르트포스는 크게 두가지 경우에..

구현 / 시뮬레이션 우리가 코딩테스트를 볼 때 유형 중에 구현, 시뮬레이션 유형이 있다. 일단, 알고리즘을 푼다는 것은 근본적으로 "내가 이 문제를 내가 생각반 방식대로 프로그래밍으로 구현 할 수 있다."를 보여주는 것이다. 일단 뭐든지 목표기능을 구현하는 코딩테스트를 출체 하는목적은 "본인이 선택한 프로그래밍 언어의 문법을 정확히 알고 있어야 하고, 문제 요건에 부합하는 코드를 빠르게 작성하는것"이 목표이다. 뭔소리냐고? 그냥 하나 오래걸리거나, 조건 많은거 던져 두고 그거 만들게 시킨다 이말이다. 그런데, 조건이 많아서 이것저것 문법을 사용해야 한다거나, 코드 길이가 줄줄줄길어져서 말 그대로 빡 구현을 해야 한다 이말이다. 구현/ 시뮬레이션 문제는 코딩체스트 지문을 잘 읽고 놓치는 조건없이 모두 코드..

탐욕 알고리즘 (Greedy) Greedy는 직역하면 "탐욕스러운, 욕심이 많은"이라는 뜻이다. 탐욕 알고리즘(Greedy Algorithm)은 당장 퇴적의 상황만을 채택하여 최종적인 결과를 내는 알고리즘이다. 탐욕 알고리즘으로 문제를 해결하는 방법으로는 다음과 같이 3 단계가 있다. 선택 절차 : 현제 상태에서 최적의 해답을 선택 적절성 검사 : 선택된 값이 문제의 조건을 만족하는지 검사 해답 검사 : 원래 문제가 해결되었는지 검사, 미해결 시 선택 절차(1번)으로 돌아가 위의 과정을 반복 글로 쓰니까 모르겠는데? 할 수 있다. 사실 우리가 실생활에서 그리드 알고리즘은 종종 사용했다. 바로 동전 거슬러 줄때 사용한다. 편의점에서 일하든, 마트에서 일하든 거스름돈을 줄 때 가장 적은 동전을 활용해 잔돈을..

시간복잡도(Time Complexity) 시간복잡도의 예시, 아주 대표적이고 중요한 사진이다. 머릿속에 기억하자 종종 코딩문제를 풀때, for문으로 풀때는 덜한데, while문으로 풀 때 "출력 나오는데 생각보다 오래걸리네" 하는 경험이 있을 것이다. 컴퓨터는 기본적으로 연산하는 놈인데, 연산 횟수가 많으면 자연히 오래걸린다. 우리는 이럴때 자연스럽게 "이거 생각보다 오래걸리는데, 더 빨리하게 못하나?" 하는 생각을 할 때가 많다. 시간 복잡도는 이러한 생각을 수치적으로 나타내는 지표 라고 볼 수 있다. Big-O 표기법 일단, 위의 그림을 보면 우리가 학창시절에 배웟던 익숙한 그래프가 보인다. 일단 시간 복잡도는 "입력값의 변화에 따라 연산을 실행 했을 때, 연산횟수에 비해 시간이 얼마나 걸리는가"를 ..

BFS / DFS 그래프에서 탐색은 배열에서 나열된 요소들을 보는것과 달리 마치 무작위로 흩뿌려져 있는것들을 일일히 들여다 보는것과 비슷한 형태를 띈다. 그래서 특정한 값을 찾고 싶거나, 최단거리를 찾고싶거나 하면, 모든 정점들을 한번씩 방문해봐야 알 수 있다. 우리가 길찾기 어플을 쓸때 최단거리를 알려주는것 처럼, 특정 정점을 거쳐 원하는 결과를 가져다 준다. BFS (너비 우선 탐색) BFS 예시 (출처 : 코드스테이츠) 너비 우선탐색은 루트기준으로 가까운 정점부터 탐색하게 된다. 마치 경로를 타고 한줄로 죽 가서 보는게 아니고 일일히 하나하나 옆으로 옮겨가면서 보는것과 비슷하다. 위의 GIF는 미국으로 가는 목적지의 최단거리를 찾는 것인데, 경유횟수가 적은 경로가 가장 최단거리임을 알 수 있는 경우..

1. Binary Search Tree 트리구조는 편리한 구조를 전시하는것 이외에 효율적인 탐색을 위해 사용되기도 한다. 대표적으로 이진 트리가 있다. 이진 트리는 자식 노드가 최대 2개씩만 존재하는 노드로 구성된 트리이다. 이진 트리의 자료 삽입, 삭제 , 노드 배치에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리로 분류된다. 3가지 이진 트리의 예시 (출처 : 코드스테이츠) 이진 트리 종류, 및 특징 (출처 : 코드스테이츠) 위의 이진 트리를 이용한 이진 탐색 트리 또한 자주 사용된다. 이진 탐색 트리는 모든 왼쪽 자식의 값이 부모보다 작고, 모든 오른쪽 자식의 값이 루트, 혹은 부모의 값보다 큰값을 가진다. 이 특징으로 특정 수들을 배치하는것으로 데이터를 분류하거나 정렬 및 탐색 알고지름을..

Graph 그래프, 그래프는 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 우리가 아는 그래프는 X축, Y축 나눠서 선 그리고 함수 그리고 하는거였는데, 컴퓨터에서 그래프는 다른의미를 갖는다. 마치 거미줄처럼 복잡한 네트워크 망과 같다. 자료구조 그래프 예시(출처 : 코드스테이츠) Graph의 구조 단순한 그래프의 예시 (출처 : 코드스테이츠) 점(데이터)를 정점 이라고 한다. 데이더와 데이터가 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 한번에 연결 안되고 몇 개의 점, 선에 걸쳐 이어진다 (옆자리 사람이 친구의 친구 같은 느낌이다. 몇 다리 건너건너서 아는사람 같은거) Graph의 표현방식 인접 행렬 간단한 그래프 형태(출처 : 코드스테이츠) ..

Tree Tree(트리)는 말 그대로 나무와 비슷한 형태를 가진 자료구조이다. 그런데 우리가 아는 나무가 아니고, 거꾸로 서있는 나무 모양이다. (약간, 토너먼트 대진표랑 비슷한 형태라고 생각하면 된다.) 토너먼트의 대진표, 적절한 예신른 아님, 작동방식이 다름 트리는 단방향 그래프의 한 구조로, 하나의 뿌리(root)에서 가지가 뻗어나온 형태로, 나무와 닮아 붙여진 이름이다. Tree 자료구조의 예시 (출처 : 코드스테이츠) 위의 그림을 보면 A~J까지 데이터가 여러개 들어있는 자료구조임을 알 수 있다. 그런데, 우리가 사용하는 배열 등은 쥬루룩 정령되서 들어가는데, 트리는 좀 다르다. 데이터를 순차적으로 나열한 선형구조가 아니라, 하나의 데이터 아래에 여러개의 데이터가 존재할 수 있는 비선형 구조이기..

자료구조 자료구조란 쉽게 말해서 일종의 주머니다. 우리가 intm String등등의 자료를 사용 했는데 이들 모두 자료구조의 일종이다. 한개의 값을 가질때는 단순구조인 int, char 형 변수 등이 사용되고, 여러개의 값을 가질 때에는 배열로 짤짤이로 다 저장 가능하다. 우리가 담으려는 데이터에 따라 그에 맞게 담기는 부분이 더 적합한게 있다는 소리다. 쉽게 비유하면, 자료 = 데이터 = 물건 자료구조는 물건을 담는데 적합한 형태를 띄는 주머니의 형태라고 보면된다. 하나하나 담고 싶을때는 칸칸이 나뉘어진 통에, 짤짤이로 담는 파츠 케이스 뭉탱이로 담고싶으면 포대를 쓰는 것 처럼 밀가루를 짤짤이로 담지 않는다, 포대를 쓴다 담고자 하는 물건 (데이터)에 따라 적합한 주머니(자료구조)가 따로있다! 라는것만..