Technology/Problem Solving

[BOJ] 18138번: 리유나는 세일러복을 좋아해

18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 256MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1232KB 풀이 설명 - DFS를 이용한 이분매칭에서 셔츠와 카라를 연결하는 조건을 만들어줘야하는 문제 #include #include #include using namespace std; #define MAX 201 // 카라와 티셔츠의 최대개수 vector vt[MAX]; int match[MA..

[BOJ] 6086번: 최대 유량

6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1352KB - 시도 회수 : 6회 풀이 설명 - 최대 유량문제 - Ford-Fulkerson method에서 augmenting path를 DFS순서대로 찾는 Edmonds-Karp Algorithm을 사용하였다. - capacity[u][v] : u에서 v로 갈수있는 해당 파이프의 최대 용량 - flo..

[BOJ] 1162번: 도로포장

1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 100ms - 사용 공간 : 7068KB 풀이 설명 - 우선순위 큐를 이용한 다익스트라 순회를 하는 문제이다. - 또한 포장 횟수를 구분하면서 최소비용을 계산해야하기 때문에 Dynamic Programming을 해야한다. - DP[i][j] : 도로를 j번 포장하여 도시 i번에 도달하는 최소비용 - 위의 DP..

[BOJ] 1738번: 골목길

1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 1388KB 풀이 설명 - 밸맨포드 알고리즘 - 시작점에서 다른 점들까지 최소도달비용을 구할수 있는 알고리즘은 밸맨포드와 다익스트라 알고리즘이 있다. - 밸맨포드는 음의 가중치를 갖고있는 경로또한 계산 가능하므로 이를 사용하였다. - 밸맨포드 알고리즘을 돌리려면 비용이 음의 사이클이 존재해서는 ..

[BOJ] 2152번: 여행 계획 세우기

2152번: 여행 계획 세우기 첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 640ms - 사용 공간 : 15680KB 풀이 설명 - 플레3 문제 너무 어렵다. - directed cyclic graph를 SCC(Strongly Connected Components)로 묶어 DAG(Directed Acyclic Graph)로 바꾼다. - 이후 DAG에서 시작 SCC부터 끝 SCC까지 가..

[BOJ] 16946번: 벽 부수고 이동하기 4

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 512MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 184ms - 사용 공간 : 25992KB 풀이 설명 - Connected Component를 그래프 순회(BFS)를 통해 분류 - Connected Component의 크기는 따로 리스트에 기록 #include #include #include #include using namespace std; int rows, cols;..

[BOJ] 9240번: 로버트 후드

9240번: 로버트 후드 첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다. www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 256MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 180ms - 사용 공간 : 2228KB 풀이 설명 - Graham Scan으로 Convex hull을 구하는 문제 1) 좌하단 점을 기준으로 정점들을 기울기 크기(x축과 각도)로 순으로 정렬한다. 2) 순회하며 ccw로 회전하는 점들만 스텍에 넣는다. 3) 결과적으로 스텍엔 Convex Hull만 남게된다. - Roatating Calipers를 ..

[BOJ] 7620번: 편집 거리

7620번: 편집 거리 가장 짧은 편집 스크립트를 출력한다. 한 명령을 한 줄에 하나씩 출력하며, 문제의 괄호에 나와있는 (a, d, m, c)중 하나를 출력하고, 그 명령을 수행하는데 사용한 글자를 출력한다. (출력할 글자 www.acmicpc.net 제한 조건 - 시간 제한 : 8s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 2292ms - 사용 공간 : 72044KB 풀이 설명 - DP문제 - 메모리 제한을 극복하기 위한 테크닉 연습문제 1) 편집거리: (knapsack에서 배웠던) 1차원 배열 두 줄(2N) 이용 2) 경로 출력을 위한 4가지 연산 저장: int 대신 bitset 등의 자료형에 비트연산 이용해 정보 압축 - 4가지 경우 (a, d, c, ..

[BOJ] 17136번: 색종이 붙이기

17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 512MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 92ms - 사용 공간 : 1176KB 풀이 설명 - 백트랙킹을 이용하여 풀이 - Matrix를 순회하며 1이 존재하는 위치를 찾아 그 위치에 크기 5 종이를 붙혀본다. - 유효했다면 같은 행동을 계속 반복하고, 그렇지 않으면 행동을 되돌리고 더 작은 색종이를 붙힌다. - 정답이 될때까지 반복한다. #include #include #in..

[BOJ] 6236번: 용돈 관리

6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 2008KB 풀이 설명 - 이분탐색을 통한 Parametric Search 방법 - 답을 도출해내는 방법을 찾는게 아니고 계속해서 답을 가정하고 검증하는 방식 - 내가 원하는 인출회수 M번보다 가정한 금액의 인출회수가 적다면 금액을 줄이고, 인출회수가 많다면 금액을 늘린다. #include #include using nam..