체크무늬 공대생

. 등장 배경) 인터넷에서 정보들을 찾아볼 때, 한 번쯤은 Ctrl + F 단축어를 통해 특정 글자만 찾아본 경험이 있을 것이다. 그리고 이 작업은, 대부분의 경우에 아주 빠르게 완료되어 몇 개의 특정 글자가 존재하는 지 알려준다. KMP 알고리즘은 이러한 작업의 핵심이 되는 알고리즘으로서, 지금도 널리 쓰이고 있는 알고리즘이다. 아래 예시를 통해, KMP 알고리즘의 필요성을 느껴보자.아이같은아이같은아이작 에서 아이같은아이작 를 찾아보자. 대부분의 경우 아이같은아이.. 에서 멈췄을 것이다. ‘작’이 나와야 할 타이밍에 ‘아’가 나왔기 때문이다. 이렇게 매칭이 실패한 경우 두 번째 글자인 ‘이’부터 탐색을 다시 시작해야 할까? 만약 이렇게 매칭을 하면 정확한 결과는 얻을 수 있다. 브루트포스 알고리즘이기 ..

플레5를 목표로 한 6월 24일 되기 전 3일 전, 어디가서 ”알고리즘 좀 풀어요“ 라고 할 수 있을 정도의 티어인 Platinum5에 드디어 도달했다..! 개인적으로 Class를 4에서 5로 올린 것과 KMP 알고리즘을 공부해 이를 응용한 플레티넘 수준의 문제들을 많이 풀어 본 게 점수 상승에 큰 도움이 되었던 것 같다. 그 동안 티어 상승에 집중하느라 블로그 포스팅이 뜸해졌는데, 다시 열심히 달려봐야겠다!

벌써 블로그를 시작한 지 한 달 정도가 지났다. 아직 글이 많지는 않아 검색으로 들어오는 방문자의 수는 적지만, 꾸준히 계속한다면 언젠가 검색했을 때 1페이지 안에 들거라 믿는다!! 백준 사이트에서 코딩 공부 또한 열심히 병행하였다. 그 결과 상병 목표였던 Platinum5까지 남은 포인트가 이제 겨우 59p 남았다. Class도 4에서 5로 올랐다! 남은 기간 동안 지금처럼 꾸준히 노력해 목표달성에 힘써야겠다.

. 문제)https://www.acmicpc.net/problem/11032소설가인 김대전은 여러 파일로 나눠진 소설을 합쳐 최종적으로 하나의 파일로 합치려 한다.두 개의 파일을 합칠 때 필요한 비용이 두 파일 크기의 합이라 가정한다.예를 들어 C1,C2,C3,C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 40,30,30,50 이라 하자.첫 번째 방법으론 C2와 C3을 합친 뒤, C1과 합친다. 마지막으로 C4를 합친다.이 때의 비용은 60+100+150 = 310이다. 두 번째 방법으론 C1과 C2를 합치고, C3와 C4를 합친 뒤 두 파일을 서로 합친다.이 때의 비용은 70+80+150=300이다.따라서 두 번째 방법이 좀 더 저렴하고, 위처럼 각 파일의 크기가 주어졌을 때 이들..

. 등장 배경) 개발하는 데에 있어서 수많은 데이터 중 원하는 값이 어디 있는 지 알아내는 건 매우 중요하다. 그리고 이것을 얼마나 빠르게 알아내는 지는 곧, 우리가 흔히 말하는 최적화와 연관되어 있다. 본 글에서는 편의상 원하는 값을 target, 데이터 리스트를 data_list 라고 표기하겠다. 이분 탐색(Binary Search)가 등장하기 전까지는, 아래 그림과 같은 순차 탐색을 진행했다.그러나 이와 같은 방식은 data_list를 처음부터 target 값이 나오기까지 하나하나 비교하기에 속도가 매우 느리다. 예를 들어 데이터의 개수 N이 100만개라고 가정한다면, 최악의 경우 100만개의 데이터들을 비교해야 한다. 그렇기에 순차 탐색보다 획기적으로 시행 시간을 단축시킬 수 있는 알고리즘의 사용..

. 문제) https://www.acmicpc.net/problem/1300 세준이는 크기가 NxN인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j]=ixj 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 NxN이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. (배열 A와 B의 인덱스는 1부터 시작한다.) . 접근) 가장 직관적인 방법은 단순히 B를 정렬 후, B[k]를 반환하는 것이라 볼 수 있다. 그러나 이 경우 quick sort를 기반으로 하는 파이썬의 라이브러리 sort 함수를 사용해도 O(NlogN)이기에 시간초과가 발생한다. 따라서 이 문제는 정렬 알고리즘을 사용하는 게 아닌, 이중탐색(Binary Search) 알고리즘의 사용이 핵심이다. 그렇다면 이중탐색의 탐색할 ..

. 문제)https://www.acmicpc.net/problem/211 수직선 상에 있는 N개의 집 좌표와 설치할 공유기 개수 C가 주어진다. 이후 가장 인접한 두 공유기 사이의 거리를 최대로 하여 설치하려 한다. 이를 만족하게 설치했을 때 가장 인접한 두 공유기 사이의 거리를 출력하시오.Input) Output) 5 3 3 1 2 8 4 9. 접근)처음 이 문제를 보고 든 생각은, 양 끝 지점에 무조건 공유기를 설치 후 가장 긴 구간의 중간 지점마다 공유기 설치를 하면 되는 거 아닌가? 였다. 그러나 모든 지점에 집이 존재하는 것이 아니므로 정확히 2등분이 될 수 없고, 매 경우마다 N개의 집 사이 거리를 계산해줘야 하기에 시간초과가 난다. 따라서 이 문제는 주어진 정보를 통해 적절히 이분탐색을 해야..

2024년 05월 06일 백준 티어 기록 블로그 개설 후 첫 포스팅이다. 군대 안에서 똑같은 일상을 반복하며 게을러지는 걸 막기 위해 목표를 세웠다. 06월 24일, 병장 진급 전 까지 Plantinum5 승급이 목표다! 며칠 전까지 TOEIC 공부하느라 감을 잃은 느낌이 없지 않아 있지만 힘내보자!!