계수 정렬(Count Sort)이란?특정한 조건이 부합할때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 + 가장 큰 데이터와 가장 작은 데이터가 백만정도 이하의 차이일때 효율적인 정렬 알고리즘이다.모든 범위를 담을 수 있는 크기의 리스트를 선언하여 구현한다.데이터의 개수가 N, 데이터 중 최대값이 K일 때 최악의 경우에도 수행 시간 O(N + K)를 보장한다. 예시를 통해 계수 정렬 이해하기아래의 표와 같은 성적을 가지고 있는 학생들이 있다고 가정하고, 오름차순으로 아래 성적을 정렬한다고 생각해보자. 누가 어떤 성적을 가지고 있는지는 중요하지 않다고 할 때, 계수 정렬을 이용하여 정렬하는 것이 가장 빠른 정렬 방법이다.7..
Algorithm
오랜만에 작성하는 알고리즘 포스팅:)오늘은 정렬중에 병합정렬 즉, 머지소트를 작성해보고자 한다.때때로 알고리즘 시험중에 외부 라이브러리를 사용할 수 없어 직접 구현해야하는 경우가 있다.그러니 이번기회에 개념을 정리하며 나와같이 머리에 넣어보도록 하자! 😚🧁 병합 정렬(merge sort) 알고리즘?존 폰 노이만(John von Neumann)이라는 사람이 제안한 방법병합 정렬은 분할정복 방식과 재귀 알고리즘을 이용한 정렬알고리즘이다.즉, 주어진 배열을 원소가 하나밖에 남지 않을 떄까지 계속 둘로 쪼갠 후에 다시 크기순으로 재배열 하면서 원래 크기의 배열로 합치는걸 반복한다.병합정렬의 구조상 최대한 작게 문제를 쪼개어 앞의 부분 리스트부터 차례대로 합쳐나가기 때문에 안정정렬 알고리즘이기도 하다. 😀?..
문제 원문 링크 바로가기문제 읽기 벽이 존재하는 N*M 필드의 (1, 1)에서부터 (N, M)까지 도달할 수 있는 최단 경로의 길이를 구해내는 문제이다. 여기까지만 읽으면 단순한 BFS 문제이지만, 문제는 '벽을 부술 수 있다'는 점에 있다. 만일 벽을 부수고 지나갈 때 경로가 더 짧아진다면, 벽을 부술 수도 있다. 단, 최대 K회까지 가능하다. 그러니까, 단순히 벽에 가로막히고 말고만을 따지는 단순한 BFS로는 문제를 풀 수 없다는 것이다. 이런 문제는 어떻게 풀어야 할까?BFS의 본질 우선, 우리가 최단경로를 구하기 위해 BFS를 수행하는 과정을 생각해보자. BFS를 수행하는 과정을 간단히 서술해보면 다음과 같다.시작 지점을 큐에 넣고, 방문 표기를 한다.이후, 큐가 빌 때까지 다음을 반복한다 : ..
🎈 시작하기에 앞서 ..오늘은 어떤걸올릴까 생각하다가 예전부터 그래프 알고리즘에 대한 개념을 정리해서 머리속에 박아 넣어놓고 싶었기 때문에 그래프 알고리즘을 하나씩 정리해 보고자 한다. 개인적으로 그래프 알고리즘은 문제에 맞는 알고리즘 기법을 아느냐 모르느냐에 따라 문제 접근시간과 풀이에 큰 차이가 있다고 생각한다.그러므로 만약 그래프 알고리즘에 대한 정리가 되어있지 않다면! 이 글을 읽으며 함께 정리해 보는 시간이 되었으면 좋겠다 🥰그렇다면 그래프 알고리즘에는 어떤것이 있을까?어떤 알고리즘이 있는지 알아보기 전에 그래프 알고리즘은 어떤 유형으로 나오는지 알아보자면..🎈 그래프 알고리즘의 유형두 정점 사이의 최단 경로찾기다익스트라 알고리즘(Dijkstra's Algorithm)벨만-포드 알고리즘(B..
서론이분 탐색 알고리즘은 이해하는 것은 어렵지 않은 알고리즘이라고 생각합니다. 주로 정렬되어 있는 배열에서 특정 값이 존재하는지 찾는 데 매우 유용한 알고리즘이고 선형탐색으로 O(N)의 시간복잡도가 걸리는 작업을 O(logN)으로 해결할 수 있습니다.하지만 막상 구현에 들어가게 되면 맞게 구현한 것 같은데, 원하는 결과가 나오지 않는 경우가 종종 있어 검색을 통해 이분 탐색의 정확한 정의와 구현 방법을 배우고자 하였습니다. 그 과정에서 정리가 매우 잘 되어 있는 글을 찾게 되었고, 이번 글은 https://www.acmicpc.net/blog/view/109 을 올려 주신 jinhan814님의 글을 보고 정리한 글입니다.해당 글에 정말 자세하게 이분 탐색 알고리즘에 대해 정리되어 있으니 참고하시면 큰 도..
문제 읽기문제 원문 링크 바로가기 문제 내용을 읽어보면, 뭔가 알 수 없는 주기로 반복되거나 뒤집히는 문자열이 무한히 이어질 때, 특정한 자리 k에 오는 숫자가 0인지 1인지를 알아내는 문제라는 걸 알 수 있다. 문제를 이해하는 건 어렵지 않지만, 난해한 규칙을 기반으로 연장되는 무한한 문자열을 어떻게 구성해야할지가 상당히 고민되는 문제이다. 정말로 10의 18승만큼 투에-모스 문자열을 나열할 수도 없는 노릇이니... 어떻게 규칙을 통해 k번째자리 숫자를 알아내야할까? 라는 것이, 이 문제를 처음 보았을 때가 내가 고민한 문제였다.결론 미리보기 다른 풀이를 찾아보았거나 풀어보았다면 알겠지만, 이 문제의 풀이 코드는 생각보다 간단한 편이다. 나의 풀이를 간단하게 정리해 결론부터 말해보자면, 다음과 같다.자..
토요일 아침 알고리즘 스터디에서 새롭게 배운 문제 풀이 방식인데, 연결 리스트에 Soft delete를 접목하여 계산 시간을 최적화하는 아이디어이다. (이 스터디에 관심 있는 사람들의 연락을 기다리겠다.) 일단 해당 알고리즘 문제에 대해서 간략하게 소개하자면 객체를 관리하는 메서드를 5가지 정의하는 문제이다. 메서드들은 다음과 같다.1. 객체를 추가하는 메서드2. 객체를 삭제하는 메서드3. 특정 객체의 데이터를 변경하는 메서드4. 특정 그룹의 객체들의 데이터를 모두 변경하는 메서드5. 특정 그룹의 가장 큰 데이터를 가진 객체를 조회하는 메서드 그냥 보기에는 단순하게 CRUD를 구현하면 되는 문제 같지만 5번 메서드를 제외한 나머지 메서드의 호출 횟수는 100,000번 이하라는 조건 때문에 1번부터 4번..
🧶 LCS란 무엇일까?문자열 알고리즘 문제중에는 연속된 혹은 연속되지 않은 부분 문자열을 찾는 문제가 종종 나온다.LCS 알고리즘은 그러한 부분 문자열을 찾을때 사용하는 알고리즘이다😋LCS는 최장 증가 부분 수열과 같이 DP(Dynamic Programming)를 기반으로 한다.최장 공통 문자열 (Longest Common Substring)연속된 문자열을 확인하는 방법공통 문자열은 부분이 아니기 때문에 한번에 이어져 있는 문자열만 가능함.최장 공통 수열(Longest Common Subsequence)연속되지 않은 부분문자열을 찾는 방법문자사이를 건너뛰어 공통되면서 가장 긴 부분 문자열예를들어 "ABCDFGO"라는 문자열과 "BCDHIGLO"라는 문자열이 있다면..최장 공통 문자열은 연속된 한번에 ..
문제 해석 😀구현문제를 풀때 가장 중요한 것은 두가지이다.1. 메서드 분리메서드를 분리해야 디버깅을 하기 편함각 메서드는 본인의 역할”에만” 충실할 것2. 헷갈리지 않도록 심플하게 구현할 것구현문제 ⇒ 보통 문제의 볼륨이 큼주사위 굴리는 부분처럼 헷갈릴 수 있는 부분은 최대한 단순하게 나의 풀이 ✒1. 주사위 객체가 메서드를 갖도록 하자2. 점수를 미리 계산해두자점수를 얻는 계산을 할때, 굴리고 점수 계산하고, 굴리고 점수 계산하지말고한번에 DP 테이블을 계산을 다 해준 다음에, 주사위를 굴리면서 점수 계산을 하는 방향이 바람직하다고 생각했다. 적용 알고리즘 🎯bfs, 완전탐색, 구현 나의 코드 💻package BJ;import java.io.BufferedReader;import java.io.I..
