https://www.acmicpc.net/problem/2162문제조건N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 그룹의 수, 가장 크기가 큰 그룹에 속한 선분의 개수를 구하시오.접근방법 선분끼리 만나는 경우를 하나하나 모두 체크를 해줘야하는지 생각해봤다.그리고 선분끼리 교차하는 건 코드로 어떻게 나타낼지 감이 안와서 검색을통해 알아냈다.https://bowbowbow.tistory.com/17 [기하] 외적을 이용해서 선분과 선분의 교차점 구하기[기하]외적을 이용해서 선분과 선분의 교차점 구하기 목차 [기하]외적을 이용해서 ..

https://www.acmicpc.net/problem/2463문제조건가중치그래프가 존재한다.서로다른 정점 u, v에 대해서 경로가 있다면 경로가 없을때까지 최소 가중치 간선을 제거한다. u 접근방법 딱봐도 MST(최소비용신장트리)와 정말 유사하게 동작하는 문제였다. 그리디한 접근법인 Prim, Kruskal 알고리즘을 떠올렸는데, 이 알고리즘의 핵심은 서로소 분리 집합으로 초기에 모든 노드(정점)을 각각 독립적인 집합으로 초기화 시킨후, 집합이 하나가 될때까지 최소비용인 간선들을 더해가는 것이다. Kruskal 알고리즘과 이 문제의 차이점은, 최대 가중치를 가진 간선부터 그래프에 추가한다는 점이다. 간선의 가중치를 내림차순으로 정렬한다.임의의 간선부터 시작해서 정점이 속해있는 집합이 서로다른 경우에만..

https://www.acmicpc.net/problem/1446문제조건D킬로미터의 고속도로 길이 주어진다.지름길의 시작위치, 도착위치, 지름길의 길이가 주어진다.고속도로 끝지점까지 가는 최소거리를 구해라.접근방법 Brute Force로 봐야하나,,? 평소에 잘 접하지 않은 유형의 문제여서 당황스러웠다.최단거리를 구한다고 하면 다익스트라가 떠올랐지만 어떻게 적용시키지,,,? 계속 생각이 안나서 검색의 힘을 조금 빌렸다.  Dijkstra 최단경로를 구하는 대표적인 알고리즘이다.이중 for문을 이용한것과, priority_queue를 이용해서 구현을 선택할 수 있는데, 우선순위 큐가 시간복잡도가 훨씬 작으므로 우선순위 큐를 사용한다.알고리즘의 동작과정은 이와같다.방문하지 않은 노드 중에서 최단거리가 가장 ..

https://www.acmicpc.net/problem/2152문제조건  총 M(1 ≤ M ≤ 100,000)개의 비행로가 존재각각의 비행로는 한 방향으로의 서비스만을 제공S(1 ≤ S ≤ N)번 도시에서 시작해서 T(1 ≤ T ≤ N)번 도시에서 여행을 끝냄  최대로 방문할 수 있는 도시의 개수 각각의 도시는 여행 중에 몇 번이든 방문할 수 있으며, 같은 항공로를 여러 번 이용할 수도 있다.접근방법 문제를 읽고 나서 든 생각은 띠용(?) 이게 뭐야,,, 였다,,문제 조건중 몇 번이든 같은 도시를 방문할 수 있다는 점을 이해하기가 어려웠다.그리고 같은 항공로를 여러 번 이용한다는 말에서 조금 감이왔다. "이거 순환이 될수 있으니까 뭔가 묶어볼수 있지않을까?"우연치 않게 학교 강의에서 들었던 SCC(S..

https://www.acmicpc.net/problem/16946 문제조건N×M의 행렬로 표현되는 맵0 : 이동가능, 1 : 벽각각의 벽에대해 해당 벽을 부수고, 이동가능한 장소로 바꾼뒤 그 위치에서 이동가능한 칸의 개수접근방법 처음에는 정말 단순하게 모든 벽에 대해서 BFS를 돌렸다가 시간초과가 났다.최악의 경우 1000^3 이면 10억인데,, 대략 10초가량 소요되는 것이다.그래서 어떻게 하면 시간을 줄여가며 해결할까 고민 한 결과,,, visited 배열을 각각 벽에대해 초기화 시켜주는 작업을 안해주면 시간제한에 안걸릴것이라고 생각했다. 그래서 벽을 탐색하는 것이아니라, 맵에서 이동가능한 부분인 0인 값에서 부터 BFS를 진행해서 인접한 벽에 누적으로 값을 더하고, visited배열을 초기화해줄 ..

https://www.acmicpc.net/problem/2234 문제조건 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, 동쪽에 벽이 있을 때는 4를, 남쪽에 벽이 있을 때는 8을 더한 값이 주어진다.이 성에 있는 방의 개수가장 넓은 방의 넓이하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기를 각각 구하시오접근방법 전체 맵을 탐색한다는 점에서 BFS를 떠올릴 수 있었고, 1(2^0), 2(2^1), 4(2^2), 8(2^3) 로 진행할수 있는지 판단해야한다는 점에서 나에겐 조금 생소한 비트마스킹이 생각났다. 이 문제에서 핵심은 비트를 1부터 왼쪽으로 Shift연산을 통해 벽에 대해 나타낸 숫자와 &연산으로 겹치는 지..

https://www.acmicpc.net/problem/2580 문제조건스도쿠판을 채우자각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.접근방법 문제를 보자마자 떠오른 생각은 N-Queen 문제와 상당히 유사한 문제라는 생각 이었다. 물론 Brute Force로 모든 경우의 수를 탐색해서 구할 수도 있겠지만, O(2^n) 이상의 시간소요로 시간초과가 날 것이 분명했고, N-Queen문제와 같이 백트래킹으로 접근했다.유망한지 판단하고, 유망하다면 DFS를 진행하는 백트래킹 방식에서 시간단축이 됨을 인지하고, 가로, 세로, 3x3 크기의 칸에서 같은 숫자가 하나도 없는지 체크하고 그..

https://www.acmicpc.net/problem/17136 문제조건  1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류의 색종이가 있다.각 종류마다 5개씩 가지고 있다. 10×10인 종이에 색종이를 붙인다. 각각의 칸에는 0 또는 1이 적혀 있다. 1이 적힌 칸은 모두 색종이로 덮여져야 한다., 0이 적힌 칸에는 색종이가 있으면 안 된다. 필요한 색종이의 최소의 개수?모두 덮는것이 불가능한 경우 -1을 출력 접근방법 하나씩 범위를 넓혀주는 BFS 방법을 써야하나,,? 라는 생각이 들었지만 정형화 시킬 방법이 떠오르지 않았다. 따라서 DFS측면으로 접근했는데, 한변의 길이가 1일때부터 5일때 까지 하나씩 판단해야하고, 그럴려면 중복을 방지 하기위해 visited 배열을 활용해야한다. 이 ..

https://www.acmicpc.net/problem/2254 문제조건 감옥의 좌표 (px,py)가 주어진다.담 기둥의 좌표들이 주어진다.감옥과 담 기둥은 일직선상에 위치할 수없다.각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다겹치지 않는 최대의 중첩된 담의 겹 수?접근방법 처음보는 유형의 문제라 생각만 2시간이상하다가 검색을 통해 도움을 얻었다,,,,역시 구현이나 어떤 알고리즘을 쓰는가 보다는 기하학적으로 접근해야하는 문제였다.정말 오랜만에 다시 보는 벡터의 외적이 쓰인다니,,, 역시 배운게 다 쓰이긴 한다. Convex Hull 알고리즘 이 문제에서 사용된 알고리즘이다.convex hull이 그래서 대체 뭐냐? 2차원 좌표 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제조건 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이는? 접근방법 시간제한도 타이트하고, 입력값도 크게 주어지길래, 단순히 for문 두번 돌려서 O(n^2) 으로 시간이 걸리게 된다면 당연히 시간초과가 날 것이라고 생각했고, 문득 저번에 이런 비슷한 문제를 푼 경험이 떠올랐다. 2024.03.21 - [Algorithm/구현, 시뮬레이션..