알고리즘

알고리즘 기본 중의 기본인 병합 정렬을 정리해야겠다. 개인적으로 알고리즘이던 자료구조던 어떤 방법이 있으면 장 단점을 가지고 있다. 이 장 단점을 아는 것도 중요하겠지만 그것보다 더 중요한건 왜 그 장 단점이 만들어졌냐는 것이다. 병합정렬은 아래와 같은 장점을 가

면접 등에서 가장 많이 출제되는 퀵정렬을 직접 구현해봐야겠다고 생각했다. 가장 빠르다고 알려진 퀵정렬 시간 복잡도는 다른 분할정복 정렬과 다르지 않은데 locality 때문에 비교적 더 빠른 시간내에 정렬이 가능하다.

실3이분탐색 문제이다. 애매하게 자꾸 틀려서 좀 짜증이 났다. 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한

실3같은 이분탐색 내용인 랜선자르기 문제를 풀어보았다.이전에 풀었던 EKO(나무자르기) 문제와 같은 유형의 문제였다.다만 달랐던 것은 탐색값이 target과 같아지는 것이 최대로 자를 수 있는 랜선을 의미하는 것이 아니라는 것이다.이분탐색을 구현하는 부분을 보면 이전에

실1확실히 실버 상위권으로 가니까 문제가 어려워진다.문제는 구글에 풀이를 검색하면 상위에 올라와 있는 글들이 대체 문제를 풀고서 풀이를 올려놓은건지 아닌지도 모를만큼 형편없는 풀이와 코드를 올려놓았다는 것이다.https://velog.io/@seanlion/b

실1어느정도 이분탐색에 감이 잡혔다.하지만 골드급으로 가면 의미 없겠지....이번 문제는 공유기 설치 문제를 풀고 나면 조금 더 쉽게 감이 잡히는 문제이다.가장 먼저 해야할 것은 이 문제가 탐색 문제인지 확인하는 것이다.일단 최소값을 찾아내라 했으니 탐색문제인데 완전탐

골5이분탐색의 풀이 유형이 달라지는 느낌이 드는 문제였다.해결방법은 맨 끝에서 시작해 가운데로 올 수록 0에 가까워지는 수라는 것. 즉 음수쪽에서 가장 작은 값은 가장 첫 값이고, 양수쪽에서 가장 큰 값은 가장 마지막 값이라는 것. (일단 모두 음수의 경우와 모두 양수

실4 dp 문제이다. Ti 는 내가 상담을 할 수 없는 날짜이므로, (상담에 걸리는 날짜) 뒤에서부터 내가 얻을 수 있는 이득을 쌓아가야 한다.해당 문제에서 주어진 예시를 가져와서 예를 들어 내가 7일만 상담을 하려고 한다면, 불가능하다. 왜냐하면 7일에 상담을 시작하

실1해당 문제는 dp의 바텀업 방식으로 풀어내는 문제이다.난이도가 올라갈수록 바텀업을 잘 풀어낼 수 있어야 될 것 같은 직감이 든다.바텀업 방식은 점화식을 만들어서 풀어야 한다고 하는데, 꼭 점화식을 만들 수 있어야 하지는 않다.n을 1부터 하나씩 증가시켜가면서 규칙성

골5dp 문제였지만 완전탐색 느낌으로 조합적으로 풀려고 했다가 실패했다.for 문으로 무게를 돌면서 재귀적으로 해당 무게에서 발생할 수 있는 모든 조합을 검색하려 했지만 당연하게도 시간초과!dp로 풀어보려고 했는데, 뭔가 풀릴듯하면서 풀리지 않았다.이유는 기존에 풀던

실1bfs 문제이다. 특정 목적지로 가는데 최소거리를 구하라고 하는 문제는 bfs 문제일 확률이 높다. bfs의 경우 시작점에서부터 갈 수 있는 모든 목적지를 breadth(너비) 기준으로 탐색하기 때문에, 처음으로 목적지를 만나는 시점이 최소거리로 그 목적지를 갈

실1 bfs 문제이다. 생각보다 간단한 원리로 풀린다.먼저 전체 배열을 순회하면서 1, 즉 익은 토마토를 모두 queue에 삽입한다.이후 queue를 순회하면서 0 (안 익은 토마토) 가 있을 경우 queue에 삽입하는 걸 반복한다. 탐색한 부분은 1로 바꿔줌으로써 더

실1 bfs 문제로 나왔지만 memoization을 이용한 완전탐색 문제에 더 가까운 느낌이다. 얼핏 봤을 땐 이분탐색 문제인가 싶었다.하지만 X가 이동하는 위치를 2배, +1, -1로 지정해주었고, count를 통해 몇 번만에 이동할 수 있는지 찾는 문제이므로 bfs

실2 계속 그래프 문제에서도 bfs 로만 푸는 문제가 나왔었는데 dfs로 풀어볼 문제가 나왔다.해당 문제는 약간 유형이 달랐는데, 기존 문제가 평면상에서 x, y 를 이동시키는 문제였다면 이번은 노드와 관련된 그래프 문제였다.본격적으로 그래프쪽으로 유형이 옮겨가는 느낌

골3 지금 진행하고 있는 알고리즘 스터디에서 당일 풀어야 했던 문제였다.스택 큐 주제를 가지고 진행했던 문제이고, 문제 발제자가 dfs로 해결할 수 있는 문제이다 보니 stack을 적용해서 푸는 것이라고 생각했던 것 같다.하지만 해당 문제는 스택을 이용하기 보단 인접리

골5다익스트라 문제였다.다익스트라는 기본적으로 두 가지 방법으로 풀 수 있는데 첫번째 방법은 O(n^2) 의 시간복잡도가 걸리고, 두번째 방법은 O(nlogn) 의 시간복잡도가 소요된다. 당연히 두번째 방법을 쓰는 게 좋다.중요한 건 다익스트라 알고리즘의 어떤 부분에서

골4다익스트라 알고리즘과 bfs 알고리즘 두가지 방법으로 모두 풀 수 있었다.다만 나는 지금 다익스트라 알고리즘을 공부 중이므로 다익스트라로 풀었다.bfs 로 푸는 방식은 그리디하게 풀게 된다.deque 을 만들어 앞 뒤 푸쉬를 가능하게 한다.먼저 벽을 뚫지 않고 가는

골5multi set과 map을 잘 다룬다면 쉽게 풀리는 문제이지만난 그런걸 잘 몰라서 queue 를 통해서 구현했다. queue를 통해서 구현하면 난이도가 치솟는다.우선 우선순위 큐를 구현하기 위해서는 heap 자료구조를 거의 무조건 사용해야 하니, heap을 이용해

골4queue로 구현하면 거의 실4 까지 난이도가 떨어질 수 있을 것 같다.문제가 간단해서 처음엔 왜 골드인지 이해가 안됬다.하지만 해시를 이용해서 풀 경우 난이도가 올라갈 것 같았다.들어오는 차마다 queue에 넣어주고, 터널 밖으로 나오는 차가 해당 queue에서

골4전형적인 플로이드 와샬 문제 유형 중 하나이다.이차원 리스트를 만들어 노드에서 관계가 발생하지 않는 답을 찾아내는 문제이다.플로이드 와샬은 코드 자체는 그렇게 어렵지 않다.하지만 만약 이 유형을 처음 본다면 플로이드 와샬을 딱 떠올리기 힘들 수 있고, 만약 떠올린다

문제를 해결하기 위한 절차나 방법.컴퓨터 프로그램은 정교한 알고리즘들의 집합이라고 간주할 수 있다. 수학이나 컴퓨터 과학에서 말하는 알고리즘은, 보통 반복되는 문제를 풀기 위한 작은 프로시저(진행절차)를 의미한다. 컴퓨터 시대 이후로는 알고리즘이라고 하면 컴퓨터를 통해

복잡도 알고리즘의 성능을 측정하는 복잡도에는 공간복잡도와 시간복잡도가 있다. 당연히 이 복잡도가 낮을수록 알고리즘은 효율적으로 동작한다. 하지만 이 공간복잡도와 시간복잡도는 일반적으로 trade-off 관계에 있어서 공간복잡도를 희생해 시간복잡도를 효율적으로 만들 수 있다. 반복되는 연산의 경우 해당 값을 저장해, 연산을 줄여서 시간복잡도를 감소시키는...

정렬 알고리즘은 다양한 알고리즘의 기초들을 이용해야 하기 때문에, 이런 부분들을 갖추고 있는지 묻는 면접에서 질문으로 많이 나오게 된다.이런 알고리즘의 기초에는 점근 표기법 분할 정복 알고리즘 (Divide & Conquer)최악의 경우, 최선의 경우, 평균적인 경우같

분할 정복이란 큰 문제를 잘게 쪼개서 해결하는 방식을 말한다. 재귀적인 개념을 내포하고 있고, top-down 방식으로 쪼개서 해결할 수도 있지만, bottom-up 방식으로 반복문을 통해 구현할 수도 있다.또한 문제를 분할하면서 기존의 데이터를 모두 순회해야 했던 문

함수가 자기 자신을 호출하는 것을 재귀 호출이라 한다.분할 정복(Divide & Conquer), 점화식 등을 구현하는 데에 많이 사용된다.재귀 호출을 통해 분할한 후 문제를 해결하면, 모든 원소 O(n)에 대하여 문제를 해결해야되었던 것이, 분할 하는 횟수(logN)

프로그래머스 lev.4 징검다리 이분탐색 문제이다.핵심은 징검다리 배열을 순회하면서 내가 이 징검다리를 지웠을 때, 만들어지는 거리가 얼마인가? 를 파악하는 것이다.예전에도 정리한 적이 있었는데, 이분탐색이 개념 자체는 심플하지만, 그 내부에서 반드시 함수가 필요하고,

탐색은 개념 자체는 어렵지 않다. 현재 가지고 있는 데이터를 얼마나 효율적으로 순회하면서 찾고 있는 데이터를 찾아내느냐의 문제이다.대표적으로 두가지 방법이 있는데, 하나가 선형 탐색이고, 두번째가 이분 탐색이다.이 두가지 방법을 구분하는 대표적인 요인은, 데이터가 정렬

프로그래머스의 베스트앨범 문제였다. 해시를 이용해 빠른 시간복잡도로 풀어내야 되는 문제.두 개의 딕셔너리를 사용해야 한다.먼저 장르를 key로 삼아 각 장르가 몇번씩 플레이 되었는지, 딕셔너리에 저장해준다.each_play 딕셔너리에는 리스트를 저장해 주는데, 이 리스

다익스트라 알고리즘은 특정 노드(start 노드) 에서 나머지 경로로 갈 수 있는 최단경로를 구하는 알고리즘이다. 실제로 네비게이션등에 사용되는 기본 알고리즘이며 이 알고리즘을 최적화 시켜 사용하게 된다.게임에서 자동으로 npc 등을 찾아가게 하는, 퀘스트 fetch

Trie 단어 검색에 최적화된 Tree 기반의 자료구조이다. root에서 부터 현재 목록에 있는 모든 단어에 대한 글자별로 트리를 구성함으로서 단어검색을 최적화 하는 자료구조이다. 시간복잡도 단어의 개수 : N 단어의 길이 : M 먼저 해당 Trie 자료구조를 구

https://www.acmicpc.net/problem/15684길어서 링크로 대체브루트포스로 모든 경우의 수를 계산해보아야 한다.사다리를 조작해 i번째 시작점에서 출발하는 것이 i 번째에 도착하게 만들어야 한다. check 함수를 만들어 현재 사다리 모양으

좋다고 말로만 들었던 비스마스킹 문제를 풀어보았다. 경우의 수가 두 가지 있는데, 해당 내용을 기록해두어야 하는 경우에 사용하면 유용할 것이라고 생각이 들었다. 해당 문제를 보면 특정 수열이 있고, 이 수열 중의 특정 문자는 바뀌었거나, 바뀌지 않았거나 둘 중의 하나이

완전 브루트포스 문제.모든 테트로미노 블록에 대해, 회전, 대칭으로 만들어지는 모든 경우의 수를 계산해서, 시작점에 대한 숫자합을 모두 계산해주면 풀 수 있다.조금 더 효율적인 방법도 가능할 거 같아, 다른 방법도 시도해 볼만할 듯.특히 배열로, 블록모양을 구현해, 주