알고리즘

알고리즘 구현을 위한 배열을 공부했다. 자바에서의 배열(array)은 원소 추가/삭제가 안되는 등 다른 언어에 비해 strict한 특성을 갖고 있다. 이번 포스팅의 결론부터 말하자면, 내가 생각한 알고리즘에서 배열을 효과적으로 활용하는 방법 중 하나는 바로 “연속

처음 연결리스트 (LinkedList)는 List를 구현하지만, 배열, List 등의 다른 자료구조와 달리, 리스트지만 각각의 원소가 연속성을 갖지 않는다. 쉽게 말하자면 모든 원소가 통째로 저장되어있지 않다. 원소는 node로, 자신의 다음 원소의 주소를 참조

자바에서의 자료구조 스택(stack)에 대해서 공부했다. 스택은 "쌓는다"는 이름대로 데이터를 적재하듯이 저장하고, 쌓인 순서대로 뽑을 수 있는 자료구조이다.(LIFO) 당연하게도 데이터를 추가하고 삭제하는 push와 pop에도 O(1)의 시간복잡도를 요한다. 개념

자바의 큐(queue)를 공부했다. 큐는 이름대로 저장된 요소 중 가장 오래된 요소부터 내보내는 자료구조이다. LIFO인 스택과 반대다. (FIFO : First In First Out) 요소를 pop()하는 순서 외에는 시간 복잡도 등 모두 스택과 동일하다. 추가

스택, 큐에 이어 이번엔 자바에서의 덱(deque)를 공부했다. deque는 Double Ended Queue의 줄임말로, 앞 뒤에서 모두 offer, poll할 수 있는 일종의 큐라고 볼 수 있다. 덱은 인터페이스로서 이를 구현한 클래스는 LinkedList, A

'괄호'로서 구분될 수 있는 스택을 활용하는 문제들을 몇 가지 풀었다. 괄호라고 표현한 것은, 괄호와 같이 서로 다른 두 문자가 만났을 때 지워지도록 하는 연산에 대한 문제들이기 때문이다. 그리고 이 연산에는 스택이 정말 적절한 자료구조다. 아래의 첫 번째 문

bfs란 그림 설명 bfs가 쓰일만한 곳들 기본문제

이전 포스팅의 그림 문제와 거의 같은 문제였다. 2차원 배열을 모두 탐색하며 1을 발견하면, BFS 탐색 후 카운트해주면 됐다.똑같이 영역의 개수를 탐색하는 문제다. 다만 탐색을 두번 하고, 한 번의 탐색에는 R과 G를 구분하지 않아야한다.정상인에 대한 탐색 이후에 b

BFS 응용 문제 풀이

처음 이번에는 재귀(recursion)에 대해서 공부했다. 고등학교 수학을 하면서 재귀, 귀납 등에 대해 들어봤기 때문에, 정확히는 아니더라도 그 느낌이라던가, 쓰임에 대해서는 잘 알고 있었다. 재귀 라는 말의 정의는, 무언가를 정의하는 과정에서 자기 자신을 참

탐색 알고리즘인 백트래킹을 공부했다. 백트래킹의 정의는, 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. BFS는 그래프에서 계층별로 탐색했다면, 백트래킹은 DFS와 비슷한 느낌으로 탐색한다고 이해했다. 백트래킹 역시 DFS와 BFS처럼

백트래킹의 개념을 공부하고 연습 문제를 몇 개 풀어봤고, 이번에는 대표적인 백트래킹 연습문제인 N과 M 문제를 모두 풀어볼 것이다. N과 M 문제들을 풀면서 백트래킹의 동작 원리와 활용에 익숙해질 것이라고 생각한다. 각 문제들에서 요구하는 것이 어떻게 달라지는지와, 이

지난 포스팅에 이어서 구현 문제들을 추가적으로 더 풀었다. 캐주얼 게임 뿌요뿌요를 구현하는 문제였다. 이전 포스팅의 문제처럼 많은 경우를 확인할 필요도 없는 간단한 문제다. 1\. 네 개 이상 인접한 뿌요를 없애기 (BFS), 2. 비어있는 공간을 위의 뿌요들로 채우기

처음 이번에는 "빡구현"이라고 불리는 시뮬레이션, 구현에 대해서 공부했다. 시뮬레이션은 정형화된 방식의 풀이 방법이 있지 않은 문제들을 말한다. 그래서 지금까지 공부했던 알고리즘이나 자료구조들과는 달리 필요한 추가적인 배경지식이랄 것이 없다고 할 수 있다. 시뮬레이션

이번에는 몇 종류의 정렬 알고리즘을 공부했다. 어차피 후술할 알고리즘들을 섞고 발전시킨 정렬 함수가 Arrays나 Collections 클래스에 모두 있지만, 적어도 기본적인 정렬 방법들에는 무엇이 있는지 정도는 알아둬야할 것 같다. 그냥 새로운 종류의 알고리즘을

지난 공부에 이어 정렬과 관련된 백준 연습 문제들을 풀었다.n의 개수가 최대 백만이고, 정수의 범위도 200만 개이기 때문에, 기본적인 O(N^2) 정렬을 사용할 수 없었다. 이전 포스팅에서 구현했던 merge sort의 동작을 테스트할 겸 이 문제에 적용해봤다.Arr

이번에는 다이나믹 프로그래밍에 대해서 공부했다. dp라고 줄여서 부르곤 하는 것 같은데, 이것의 정의는 "구하려는 문제의 해를 더 작은 문제의 해로부터 도출해가는 알고리즘" 이다. 사실 이건 내가 공부하고 문제 좀 풀어보고나서 맘대로 표현해본 것이다. 다르게는 "여러

처음

이번에는 그리디 알고리즘을 공부했다. 그리디 알고리즘의 정의는, 지금 당장 최적인 답을 근시안적으로 택하는 알고리즘이라고 한다. 역시나 정의만 봐서는 감이 잘 오지 않는다. 바로 문제를 풀어 보면서 감을 잡아봤다. DP에서 봤던 문제와 유사해보인다. 차이는 두 가지 인

처음 그리디와 관련된 백준 연습 문제를 추가적으로 풀어봤다. 중간 1. 백준 11399 - ATM i번째 사람에게 필요한 시간 p에 대해서, (n-(i+1))\*p만큼 총 시간이 늘어나기 때문에, p가 작은 순서대로 ATM기를 사용해야한다. 우선순위 큐로 자동으로