Segment Tree+KMP
백준 3308번 Matching 문제풀이 [3308 Matching] https://www.acmicpc.net/problem/3308 . 문자열에서 패턴을 찾을 때 KMP를 이용하는데 세그트리와 접목한 문제를 풀어보자! 내 블로그에 포스팅할때도 KMP랑 Segment tree를 비슷한 시기에 올린 것 같은데 그 둘을 접목한 문제가 있다는...
백준 3308번 Matching 문제풀이 [3308 Matching] https://www.acmicpc.net/problem/3308 . 문자열에서 패턴을 찾을 때 KMP를 이용하는데 세그트리와 접목한 문제를 풀어보자! 내 블로그에 포스팅할때도 KMP랑 Segment tree를 비슷한 시기에 올린 것 같은데 그 둘을 접목한 문제가 있다는...
백준 18186번 라면사기(large) 문제풀이 [18186 라면사기(large)] https://www.acmicpc.net/problem/18186 . 그리디하게 문제를 해결해보자! 사람들이 많이 푼 다이아 문제 중 하나라서 언젠가 꼭 풀어봐야지 했던 문제다. 좀 보면 그리디라는 건 쉽게 알아차릴 수 있다. 근데 다른사...
백준 4196번 도미노 문제풀이 [4196 도미노] https://www.acmicpc.net/problem/4196 . SCC를 이용하여 서로 영향을 미치지 않는 것의 개수를 구해보자! SCC를 배우니까 플레 문제들이 쓱삭 풀린다. SCC구하는 알고리즘으로는 타잔 알고리즘, 코사라주 알고리즘이 대표적인데 나는 아직 코사라주밖에...
백준 3176번 도로 네트워크 문제풀이 [3176 도로 네트워크] https://www.acmicpc.net/problem/3176 . LCA를 구하고 그 때 Sparse table을 이용해보자! 구간 최대, 최소를 구할 때 놀랍게도 전처리를 해두면 O(1)에 구할 수 있는 방법이 있다. 그것이 바로 sparse table이고 ...
백준 16367번 TV Show Game 문제풀이 [16367 TV Show Game] https://www.acmicpc.net/problem/16367 . 문제를 2-SAT문제로 변환해서 풀자! 2-SAT를 이용해서 여러 논리 관계들이 모순이 있는 지 없는지 알 수 있다. 문제상황 파악하기. 참가자들이 각각 3개의 추측을 낼 수 있고...
백준 21162번 뒤집기 K 문제풀이 [21162 뒤집기 K] https://www.acmicpc.net/problem/21162 . 해시를 이용해 접두어가 같은 부분을 빠르게 찾아내자! 신촌 ICPC 알고리즘 캠프를 이번 방학에 신청했다. 강사님이 필수과제로 내준 문제이고 솔직히 풀이를 안들었으면 못풀었을 것같다. jhna...
ps5 게임 : 페르소나 5 더 로열 리뷰 개요 알고리즘 공부를 시작한지 6개월이 되어가고 블로그에도 글이 한 30개 정도 쌓였다.(굳굳) 해보고 싶은건 내 블로그도 꾸며보고 싶고, 앱도 개발해보고 싶고, 게임도 개발 해보고 싶고, 알고리즘도 많이많이 풀고 싶었지만…. 실상은 알고리즘 한 문제에 끙끙대다가 한문제 풀고나면 에이 힘들...
codeforce round #811(div 3), #812(div 2), CodeTon round 2 업솔빙 Codeforces Round #811, #812, #CodeTon 개요 너무 귀찮아서 3개를 한꺼번에 포스팅한다. 기술 블로그 쓰는 분들이 정말 대단하다. 공부하기도 바쁜데 기록까지… 최근 라운드들은 그래도 그린퍼포나 민트퍼...
codeforce round #808(div 2), #803(div 2, virtual) 업솔빙 Codeforces Round #808, #803 개요 일단 지금 808 보고 난 직후 이고 역시나 2솔ㅠㅠ c, d만 몰아서 업솔빙 해볼 것이다. 이번 808은 너무 힘들었다. A가 잟안 풀려서 B를 해야하나 A를 해야하나 고민도 많이 됐고...
백준 10167번 금광 문제풀이 [10167 금광] https://www.acmicpc.net/problem/10167 . 세그먼트트리 대표 다이아 금광을 풀어보자! 연속합과 쿼리 위 문제를 풀고 나니 금광도 풀 수 있다고 해서 호다닥 달려왔다. 근데 뭐가 풀 수 있다는 건지 짱짱 어려웠다. 좌표압축도 같은 ...