profile
코딩하는 군인입니다.
post-thumbnail

[BOJ] 2887번 : 행성 터널(C++)[Gold I]

MST 알고리즘의 시간복잡도는O(ElogV). 모든 행성 간의 터널 연결 비용을 구하려면 O(N^2). 다른 방식의 접근 필요

2021년 5월 24일
·
0개의 댓글
post-thumbnail

[BOJ] 2568번 : 전깃줄 - 2(C++)[Gold I]

남아있는 모든 전깃줄이 서로 교차하지 않는 조건은 LIS(Longest Increasing Sequence)를 찾고 나머지 전깃줄은 없애는 경우와 같다.

2021년 5월 7일
·
0개의 댓글
post-thumbnail

[BOJ] 1562번 : 계단 수(C++)[Gold I]

조건 0에서 9가 모두 등장하는을 무시하고 길이가 N인 계단 수를 먼저 고려해보았다. DFS함수에 Memoization을 적용, 2차원 배열을 이용하여 문제를 해결할 수 있다.

2021년 5월 2일
·
0개의 댓글
post-thumbnail

[BOJ] 1509번 : 팰린드롬 분할(C++)[Gold I]

처음엔 어떤 문자열을 팰린드롬으로 분할하여 나타낼 수 있는 집합의 경우의 수를 묻는 문제로착각하였다. 그러나 최소 몇 개의 팰린드롬으로 문자열을 표현할 수 있는 지를 묻는 문제였다.문자열이 ABACABA인 경우 답은 1이다.

2021년 4월 27일
·
0개의 댓글
post-thumbnail

[BOJ] 9328번 : 열쇠(C++)[Gold I]

지도 전체를 탐색해야 하므로 BFS를 기본으로 사용하였다. 호출할 수 있는 BFS 함수의 시작 위치가 일정하지 않으므로 지도를 약간 변형해 일정하게 BFS(0, 0)을 호출하여 답을 구하였다.

2021년 4월 21일
·
0개의 댓글
post-thumbnail

[BOJ] 2252번 : 줄 세우기(C++)[Gold II]

Solution 주어진 M개의 input으로 그래프를 만들면 DAG가 된다. Topological Sorting : 어떤 일들의 순서(줄 세우기)를 나타내는 알고리즘 Incoming Edge가 0인 Node를 queue에 push한다.

2021년 4월 17일
·
0개의 댓글
post-thumbnail

[BOJ] 2098번 : 외판원 순회(C++)[Gold I]

완전 탐색으로 이 문제를 해결하려면 O(N!)의 시간이 걸려 time limit이 발생하지만 겹치는 경우의 수가 다수 발생하여 memoization 구현시 시간 제한안에 문제를 해결할 수 있다.

2021년 4월 13일
·
0개의 댓글
post-thumbnail

[BOJ] 1208번 : 부분수열의 합2(C++)[Gold II]

Solution 부분수열의 합을 구하는 모든 경우의 수를 고려해야 한다. → Backtracking time limit 발생 N개의 정수로 이루어진 수열을 N/2개의 정수로 이루어진 배열 & N-(N/2)개의 정수로 이루어진 배열로 나누어서 생각

2021년 4월 8일
·
0개의 댓글
post-thumbnail

[BOJ] 1197번 : 최소 스패닝 트리(C++)[Gold IV]

Solution - MST 알고리즘(Kruskal, Prim) 중 Kruskal Algorithm을 사용 - Kruskal Algorithm 중 cycle의 여부는 Union-Find를 통해 확인 - 최적화를 통해 Find 연산의 시간복잡도를 낮춤

2021년 4월 5일
·
0개의 댓글
post-thumbnail

[BOJ] 1005번 : ACM Craft(C++)[Gold III]

Solution 건물순서 X -> Y가 Input으로 주어지는데 Adjacency List에는 X <- Y의 형태로 저장 승리하기 위해 건설해야 할 건물의 번호 W를 start node로 생각 건설시간이 가장 긴 W에서 어떤 노드 E까지

2021년 4월 4일
·
0개의 댓글