Study_Cat

꾸준히 공부하는 고양이가 될게요.

끊임없는 노력은 천재를 이긴다.

코딩/알고리즘 19

[solved.ac] 다이아V 달성과 앞으로의 목표

사실 다이아V 달성한지 쫌 오래됐는데요, 다시 열심히 글을 작성하고자 향후 목표나 다짐을 적어보고자 합니다.   여태까지 solved.ac 티어를 올리는 것을 목표로 했었는데.. 이제는 그냥 취미로 꾸준히 즐기고자 합니다. 대신에 웹 개발이나 데이터 분석같은 다양한 분야에 대해 공부하고 작은 프로젝트들을 진행하고자 합니다. 그리고 앞으로 대학교에서 재밌는 코딩이 나갈 예정이라 후배들을 위해 준비해야겠어요 :D   추가적으로 원래는 대회들을 나갈 생각이 없었는데.. 그냥 경험으로 생각하고 즐겨봐야겠어요!

코딩/알고리즘 2024.10.19

[알고리즘 문제] 1146번 지그재그 서기

출처 : https://www.acmicpc.net/problem/1146 1. 접근1. 키(숫자)는 궁금하지 않다, 즉 (1 2 3 4) 나 (1 5 7 9) 는 같은 상태이다.2. 모든 키가 다르므로 결국 인원 수가 중요하다3. 가장 키가 큰 N을 어디에 배치할지 정하고 나눠진 구간을 subproblem 으로 계산하자!  처음부터 위와 같이 접근한 이유는 다음과 같습니다.1. 상태의 독립성을 나타내기 위한 정보는? -> "인원수"2. subproblem 으로 쪼개고 싶다! -> (3)  2. 고찰N을 배치함에 따라 left, right 영역으로 나눠진다고 할 때 다음과 같은 궁금증이 떠올랐습니다.dt[N] : 지그재그 서는 가지수라고 하고 ( left ) N ( right ) 꼴로 나타날 때,Q. l..

코딩/알고리즘 2024.07.14

[알고리즘 문제] 31063번 - Candy Cane Feast

출처 : https://www.acmicpc.net/problem/31063 해당 문제는 풀이가 굉장히 짧기에 포스팅이 짧지만, 교훈이 매우 중요할 것 같습니다. 1. 접근 과정 문제를 대충 보아하니 O(NM) 으로 TLE가 발생할 것 같다는 느낌이 든다. 따라서 어떤 알고리즘을 사용해서, 어떤 아이디어를 사용해서 최적화할 수 있을까? 를 관점으로 계속 생각하였다.  이전에 포스팅했던 SegmentTree 중 Lazy 하지 않더라도 연산 횟수가 제한된 경우의 문제를 떠올리며 입력의 최댓값을 보아하니 가망이 없겠구나... 싶었다. long long 타입까지 가능성이 있기에 고민하던 중 2^63 이라는 숫자 중 지수 부분을 활용하고자 생각하였고 문제 메커니즘을 다시 살펴보니 맨 앞의 소는 항상 먹을 수 밖에..

코딩/알고리즘 2024.06.26

[알고리즘 개념] Query 문제 테크닉 Mo's 알고리즘

Mo's 알고리즘 이란?구간 질의하는 Query 문제에서 업데이트되지 않는 특수한 상황에서 사용할 수 있는 알고리즘으로 기존의 구간 쿼리는 O(NM)인 반면 Mo's 를 사용하면 O(M sqrt N) 으로 줄일 수 있습니다.  아이디어데이터가 추가적으로 업데이트되지 않는다면, 모든 쿼리에 대해서 항상 전체를 탐색해줄 필요는 없습니다. 이 전에 계산한 구간의 값을 참고하여 답을 구할 수 있습니다.   일단 데이터 길이를 N으로 했을 때 sqrt(N) 의 길이로 그룹을 나눕니다. 위 그림은 N = 10 일때의 그림이며 4개의 구간으로 나눌 수 있습니다. ( 왜 sqrt(N) 으로 나누는지는 아래에 설명하겠습니다 )  만약 위처럼 3가지 쿼리가 주어졌다고 할 때 어떻게 작동하는지 간략하게 그림으로 보고 자세히..

코딩/알고리즘 2024.06.04

[solved.ac] 플래티넘2 달성 소감과 과정, 앞으로의 계획

드디어 플래티넘2에 도착했습니다... 눈치가 빠르신 분은 알아챘을 수도 있습니다. 플3 포스팅을 안한 것과 뒤의 저 프로필이 의미하는 바가 무엇인지.. 플3 찍고 나중으로 포스팅을 미뤘다가 어느세 50%정도 채워져서 그냥 포스팅하지 않았습니다. 그리고 뒤의 프로필을 수열과 쿼리를 여러 문제를 풀면 주는건데... 넴, 세그 트리가 대량으로 과제로 나와서 본의 아니게 날먹했습니다.  티어가 실력을 전부 나타내진 않는다 어느정도 티어를 쌓으면서 위의 말이 공감되기 시작했습니다. 예전에는 티어 올리는 재미로, 티어를 목적으로 공부한 반면 지금은 알고리즘을 공부하기 위해 공부하고, 티어는 그 추가적인 결과물이라고 생각합니다.  예전에는 실버나 골드 하위 문제는 그냥 넘기는 버릇이 있었는데, 이제는 일단 풀어야겠습..

코딩/알고리즘 2024.06.04

[알고리즘 문제] 25402번 트리와 쿼리

출처 : https://www.acmicpc.net/problem/25402   1. 풀이해당 문제는 주어진 S에 대하여 집합 혹은 그룹을 만들고 각 그룹의 인원수를 Combination을 이용하여 푸는 것 임을 바로 알 수 있다. 이 문제에서 중요한 점은 주어진 집합 S에 대해 그룹의 인원수를 파악하는 것이다.  각 질문마다 S집합에 속한 노드를 chk배열에 확인해두고 단순히 dfs를 돌면 시간초과가 날 것이다. 그 까닭은 dfs는 O(N)이 아니라 O(V+E) 이기 때문이다. 이러한 dfs는 해당 노드에 연결된 모든 간선을 탐색하므로 해당 문제에서 최악의 경우 각 질문마다 O(N) 이 발생하며 결과적로 N*O(N) = O(N^2) 이 되며 시간초과가 난다. 위 예시에서 빨간색은 S집합에 속한 노드를 ..

코딩/알고리즘 2024.05.29

[알고리즘] ccw와 선분교차 판정

CCW(Counter-Clockwise) 알고리즘 CCW는 벡터의 외적을 이용하여 한 선분에 대하여 한 점의 위치 관계를 파악하는 알고리즘을 말합니다.직선 AB에 대하여 점 C의 위치 관계 서술한다면 AB벡터와 AC벡터의 외적 값의 부호를 통해 알 수 있습니다. 그리고 이러한 위치 관계를 통해 기하에서 다양한 것들을 할 수 있습니다. ※ 벡터의 외적과 방향성오른손의 법칙을 통해 AB벡터로 손을 가르킨 후 점 C의 방향으로 손을 감을 때 엄지손가락이 위로 가면 반시계 ( 외적값이 + ) 반대로 아래로 가면 시계방향 ( 외적값이 - ) 로 나타납니다.  int ccw(pii v1, pii v2, pii v3){ ll val = (v2.first-v1.first) * (v3.second-v1.second..

코딩/알고리즘 2024.05.12

[알고리즘] 강한 연결 알고리즘 SCC (feat. 2150번)

SCC 알고리즘 목적 해당 알고리즘의 목적은 사이클을 한 개의 노드로 묶는 것을 목적으로 하며 이 알고리즘은 위상 정렬에서 많이 사용됩니다. 위상 정렬은 사이클이 없는 그래프, 즉 dag라는 조건이 있어야 했는데요. 하지만 실제 복잡한 그래프는 사이클이 존재하는 그래프가 매~우 많습니다. 이런 상황을 다루기 위한 테크닉이 바로 SCC 알고리즘이 되겠습니다!강한 연결 요소 Strong Connected Component의 Group에 속하는 노드는 u, v 에 대하여 u->v로 항상 이동이 가능한 집단을 말합니다. SCC알고리즘은 이런 조건을 만족하는 노드를 grouping하는 것입니다!일반적인 그래프(트리 포함) -> Dag(트리 포함x) 변환!  작동 메커니즘문제 출처 : https://www.acmi..

코딩/알고리즘 2024.05.09

[알고리즘 문제] 2316번 도시 왕복하기 2

출처 : https://www.acmicpc.net/problem/2316 1. 아이디어 접근기존의 네트워크 플로우 문제와 달리 추가된 조건이 한 가지 더 존재한다. 그것은 바로 "지난 노드는 더 지날 수 없다" 해당 조건을 구현하기 위해서 기존의 네트워크 플로우와 달리 이상한 방향으로 계획을 세우곤 했는데 해당 문제는 어떤 예제 상황에서 힌트를 얻을 수 있었다.  모든 간선의 최대 용량이 1일 때 1->2 로 가는 최대 유량은 2일 것이다. 하지만 우리가 구하고 싶은 답은 1이다. 여기서 우리가 관찰할 수 있는 것은 3으로 가나 4으로 가나 결국 5라는 공통된 지점이 존재하며 공통된 지점을 지날 때 연산 결과가 답을 도출한다는 결론을 내릴 수 있다.  해당 예시에서 5번은 검문소 혹은 공항과도 같다. ..

코딩/알고리즘 2024.05.01

[알고리즘 개념] Network Flow 최대 유량 알고리즘 (feat. 6086번 풀이)

참고 블로그 : https://blog.naver.com/kks227/220804885235저는 kks227(라이) 님의 블로그를 자주 보는데요. 이번에 최대 유량 알고리즘을 공부할 때도 이 분의 블로그를 메인으로 보고 다른 문서들이랑 같이 봤습니다. 혹시.. 문제가 된다면 내리겠습니다.  개인적으로 이분탐색을 먼저 공부했기에 많이 햇갈렸는데요, 그래서 다른 분들도 최대한 이해하기 쉽게 설명할라고 합니닷.. 1. Main Idea1) 용어 설명용량 : c(u, v) - 정점 u->v로 전송할 수 있는 최대 용량유량 : f(u,v) - 정점 u->v로 흐르고 있는 유량잔여 용량 : r(u,v) - 정점 u->v로 더 흐를 수 있는 유량소스 : 시작점싱크 : 도착점2) 규칙1. 용량 제한 : f(u,v) 2..

코딩/알고리즘 2024.04.29

openipc openipc openipc openipc openipc openipc