컴공과컴맹효묘의블로그

일반적인 문자열 비교 알고리즘은 시간 복잡도가 $O(NM)$으로 매우 느리다.$$ O(NM) $$$$ O(N+M) $$하지만 KMP 알고리즘을 사용하면 $O(N+M)$에 가능하다.KMP 알고리즘의 아이디어문자열 s와 패턴 p가 주어졌을 때 단순 무식한 방법으로는 O(s*p)가 걸린다.KMP알고리즘은 이 과정에서 낭비되는 정보를 이용하자는 아이디어에서 시작된다.예를 들어보자INDEX : 0 1 2 3 4 5 6 7 8 9 0 1TEXT : A B C D A B C E K O I PPATTERN : A B C D A B E ^주어진 문자열과 패턴을 단순 무식한 방법으로 비교할 때 인덱스6에서 일치하지 않아 비교에 실패했다면, p를 한 칸 뒤로 옮겨 비교할 것이다..

https://gazelle-and-cs.tistory.com/12 쾨니그의 정리 (Kőnig's Theorem)이 글은 홀의 정리 (Hall's Theorem)와 밀접한 연관이 있습니다. 필요한 경우에는 이를 참조하세요.2019/01/28 - [조합론적 최적화] - 홀의 정리 (Hall's Theorem) 무언가를 최적화시키는 문제를 보면 생각보gazelle-and-cs.tistory.com

언어: C/C++시간: 13:00 ~ 17:30 총 4시간 30분문제: 코테 5문제 + CS 10문제제출: 2.5 제출 1. Stage단순한 dp문제. 별로 어렵진 않았다. 체감상 실버1~골드4 2. Excavate일반적인 코테보단 API문제느낌. 비결적 함수에 대해서 최적의 결과를 도출해야한다. 처음엔 문제가 이해가 안돼서 binsearch로 풀어봤다가, 이것 저것 결합한 방식 즉, 휴리스틱으로도 해봤다가 답을 찾을 수 없어 결국 포기했다. 나중에 찾아보니까 dp문제인듯하다. 3. Cactus2D Segment문제처럼 보였다. 하지만 구현하는 방법을 까먹어서.. 부분점수만 제출했다. 4. 배열 속 배열특정 패턴을 찾아야하는 수학 문제. 접근만 하면 난이도는 크게 어렵지 않은듯. 5. 선로구현문제. ..

언어: C/C++시간: 13:00 ~ 18:00 총 5시간문제: 7문제제출: 3.5 제출 문제를 유출하면 안되기에 간단하게만 적어보겠다.괄호 안에 적힌 것은 (유형, 내가 푼 시간, 체감 난이도-프로그래머스 기준)으로 적었다. 1. 스포 방지 문제 (구현, 30min, lv1)문제를 좀 복잡해보이게 쓰여있는데, 어려운 문제는 아니었다. 주어진 조건이 쓸모 없는 조건이 좀 있어 복잡해 보였다.2. 신호등 문제 (구현, 40min, lv1)주기 계산 문제다. 수학적 스킬을 쓰지 않고 완전 탐색으로 풀어도 시간 안에 풀 수 있어서 완전탐색으로 풀었다.3. 최적 분배 트리 (트리?, 50min, lv4+)특별한 조건이 있는 트리를 만드는 것이다. 트리 몇 개를 나열하며 들여다 보면 패턴이 보이지 않을까 싶어 ..

https://www.acmicpc.net/problem/1086 모든 탐색을 돌면 $15!$가지 경우의 수가 나온다.하지만, 입력된 $N$개의 원소를 가지는 집합 $S$가 있을 때 부분집합 $s\subset S$이 있다고 하자.부분집합 $s$로 합칠 수 있는 숫자들을 $num_i$라고 하면 $\text{cache}[\text{s}][\text{num}]$에 모듈러 연산을 했을 때 0이 되는 경우의 수를 저장할 수 있다. 어떤 부분집합 $s, (a\not\in s)$에 대해 조합한 $\text{num}$에서 $a$를 오른쪽에 추가했을 경우 다음과 같이 모듈러 연산을 할 수 있다.$$\text{num} := (\text{num}*10^{len_a-1}\mod k+a)\mod k$$$len_a$는 a의 길..

백준 문제를 풀던 도중 이분 매칭 알고리즘이라는 것을 처음 접했다. 두 집합에 대해서 서로가 매칭할 수 있는 간선이 있을 때, 겹치지 않고 최대로 많은 매칭을 구하는 것이다. 정확히 말해 이분 그래프에 대해서 각 정점이 하나의 간선만 소유하는 것. DFS를 사용하면 O(VE), Hopcroft-Karp알고리즘을 사용하면 O(sqrt(V)E)이다. 처음에 이해가 잘 가지 않아서 코드와 그림을 step by step으로 이해하며 분석했다.해당 알고리즘은 다음과 같다.현재 노드가 연결할 수 있는 노드에 연결했을 때 이전에 매칭된 노드들을 끊어지지 않게 재배치할 수 있다면 현재 노드의 연결을 허용한다. 만약 재배치가 불가능하다면, 현재 노드가 연결할 수 있는 또다른 노드를 찾아 위를 반복한다.각 노드에 대해서 ..

https://www.acmicpc.net/problem/1395이 문제는 특정 구간을 스위치하거나, 특정 구간의 켜진 스위치의 합을 구하는 문제이다.구간합 문제로 생각했고, segment tree를 최적화하면 풀 수 있다고 생각했다.하지만 최적화를 위한 아이디어를 바로 떠올리긴 어려웠다.일반적인 segment tree에서 단일 원소 갱신은 $log{N}$이므로 단순 구간 갱신은 $N log{N}$이 될 것이다. 다른 방법을 찾아봐야한다. 처음엔 각 원소가 0과 1을 갖는 단순한 특징 때문에 단순히 특정한 수학적 연산으로 가능할 줄 알았다. 그렇게 해서 떠올린 것의 시간복잡도는 결국 $log^2N$이었다. 결국 인터넷에서 답을 찾았고 lazy segment tree 아이디어를 사용해야했다. 아이디어는 이..

4학년 졸업 작품으로 맛집 검색 서비스를 개발하고있었다. 맛집 검색이라는 서비스는 이미 수년 전에 많은 사람들이 했던 진부한 그런 프로젝트였다. 리뷰 요약 서비스는 이 서비스에서 뭔가 특별한 우리만의 서비스는 없을까 고민하다가 나온 아이디어다.대부분의 사람들은 식당 선택에 있어 때 별점과 리뷰를 결정적인 요인으로 보는 경향이 있다(1). 나 또한 경험적으로 1차로 별점을 확인하고, 2차로 리뷰를 확인한다.기술- Language: Python- Framework: FastAPI- Architecture: Docker, Spring Cloud- KoNLPy(Okt): 한국어 형태소 분석 및 어간 추출- 감정 사전(SentiWord_Dick.txt): 단어별 polarity 점수- Sentence-Transf..

https://www.acmicpc.net/problem/11066 이 문제를 봤을 때 Priorty Queue로 풀 수 있을 줄 알았다. 하지만 제약 조건에서 "연속이 되도록 파일을 합쳐나가고, ..."라는 인접 제약조건이 있기 때문에 인접 조건을 무시하는 Priorty Queue로 풀 수 없었다. DP문제라는 사실을 알아도 풀지 못해 정답을 찾아봐도 처음엔 이해하기 어려웠다... 풀이DP[i][j]를 파일 i번부터 j번까지 합쳤을때 최소비용 이라고 정의하자. 이러면 DP[1][N]이 정답이다.그리고 SUM[i][j]는 파일 i번부터 j번까지 파일을 합친 크기라 정의하자. 그러면 다음과 같은 수식을 구할 수 있다.DP[i][j] = min(DP[i][m] + DP[m+1][j] + SUM[i][m] +..

2025년 2월 B형 역량테스트 시험을 보라고 연락이 왔다. 원래 A형을 취득한 사람만 볼 수 있었는데, 나는 A형은 없었지만 SSAFY 입과 코딩 테스트에서 좋은 결과가 있으면 바로 B형 응시가 가능하다고 했던 것 같다. 입과 테스트를 잘 봤나보다. 당시에 나는 허리디스크 통증이 너무 심해져서 앉기는 커녕 걷기도 힘들어했다. 하지만 B형 시험이 얼마 남지 않았고, SSAFY를 그만두더라도 이 시험은 보고 나오고 싶었다. 그래서 25년 1차 테스트를 신청했고, 평소에 알고리즘 풀이에 익숙한 언어는 cpp로 응시했다. 시험을 본지 5일 뒤인 목요일에 합격 연락이 왔다.개인적으로 B형 테스트는 꼭 통과하고 싶어서 2주동안 열심히 준비했는데, 다행이 합격통보를 받았다. 합격 통보 메일 1시간 뒤, 합격 수기를..