알고리즘 (100) 썸네일형 리스트형 백준 13913 숨바꼭질 4 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net queue와 stack을 이용해서 풀었다. /* 숨바꼭질 4 */ #include #include #include #include #include #define pp pair using namespace std; int N, K; int arr[200001]; void input(); void solve(); int main(void) { ios_base::.. 백준 1963 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 문제 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 www.acmicpc.net bfs와 그리디하게 풀면 된다. 요즘 고급 알고리즘 공부를 많이 접하다보니까 이 문제를 특정 알고리즘으로 풀려다가 시간을 많이 날렸다... 밸런스가 중요한 것 같다. /* 소수 경로 */ #include #include #include #include #include #define INTMAX 10000 + 1 using namespace std; string a, b; int check[INTMAX]; .. 백준 11438 LCA2 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net Segment Tree를 이용한 LCA로 이 문제를 풀 수 있다. /* LCA2 */ #include #include #include #include #define pp pair #define INTMAX 2100000000 using namespace std; int N, first_touch[100001], path_idx; vector path, seg_tree; vector ed.. 백준 1949 우수 마을 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, �� www.acmicpc.net Tree Dp 문제 돌이켜생각해보면 tree는 참 재밌는 구석이 많은 자료구조같다. 지름 구하는 것도 참 신기하고... 양방향 간선이므로 어떤 노드를 root로 선택해도 된다. 그래서 생각하기 편하도록 1번 노드를 Root 노드로 잡았다. 어떤 분은 트리 순회하는 순서를 처음부터 vector에 저장하시던데, 내 코드는 그러진 않았다. 코드를 보면 이해가 더 잘되실 것 같다. /* 우.. 백준 3109 빵집 https://www.acmicpc.net/problem/3109 3109번: 빵집 문제 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴� www.acmicpc.net 그리디 알고리즘 문제다. 처음엔 DP를 끝에서부터 하다가 실패해서 그리디 알고리즘으로 다시 했다. 아이디어는 '성공할 수 있는 경로는 누가 와도 성공할 수 있다.'이다. 예를 들어서 .xx.. ..x.. ..... ...x. ...x. 문제는 다음과 같은 예시를 제공한다. 첫 행의 네 번째 열의 .까지 도착하면 바로 성공할 수 있다. 출발점이 무엇이든간에 저기에 도착하면 성공한다. 마찬가지로 성공으로 갈 수 .. 백준 2263 트리의 순회 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net In-Order와 Post-Order를 보고 Pre-Order를 유추하는 문제다. Post-Order의 제일 마지막 Node가 그 Tree의 Root Node가 된다. 해당 문제는 다음과 같은 예시를 제공한다. In Order : 1 2 3 Post Order : 1 3 2 Post Order의 제일 마지막에 있는 2가 root 노드이다. 그러면 In order에서 2를 찾는다( 각 노드번호는 고유하다) In Order에서 2를 .. 백준 11437 LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA라는 새로운 알고리즘을 도입했다. Segtree를 이용해서 풀었는데 코드가 좀 지저분하다. LCA 알고리즘에 대한 공부를 하고, 그것을 연습하기에 좋은 문제라 생각한다. /* LCA */ #include #include #include #include #define pp pair #define MAX_NODE 50000 + 1 using namespace std; int N, max_.. 백준 2493 탑 C++ https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net DP로 풀 수 있고 Stack으로도 풀 수 있다. 둘 다 어렵지 않은 풀이지만, Stack 풀이가 뇌용량을 덜 쓴다. 우선 Dp로 풀었다. 만약 탑이 6 4 5 7 3 순으로 배치되어있다면 답은 "0 1 1 0 4" 이다. 여기서 '5'를 잘 봐야하는데, 5는 일단 바로 앞의 값을 본다. '4'다. 본인보다 높이가 낮으므로 전파가 닿지않는다. 무식하게 할 경우 여기서 6을 보게 된다. 운 .. 백준 10868 최솟값 https://www.acmicpc.net/problem/10868 10868번: 최솟값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는 www.acmicpc.net 세그먼트 트리를 활용하는 문제다. 문제를 읽다보면 대놓고 세그먼트 트리를 활용하라는 것 같다... /* 최솟값 */ #include #include #include #include using namespace std; void solve(); int seg_init(int s, int e, int node); int seg_find(int s, int e, in.. 백준 2104 부분배열 고르기 https://www.acmicpc.net/problem/2104 2104번: 부분배열 고르기 문제 크기가 N(1≤N≤100,000)인 1차원 배열 A[1], …, A[N]이 있다. 어떤 i, j(1≤i≤j≤N)에 대한 점수는, (A[i]+…+A[j])×Min{A[i], …, A[j]}가 된다. 즉, i부터 j까지의 합에다가 i부터 j까지의 최솟값을 곱한 �� www.acmicpc.net 세그먼트 트리를 활용한 문제다. 그냥 재귀를 활용할 수도 있지만 만약 가장 작은 수가 배열의 양 끝일 경우 O(N^2)가 되기 때문에 시간초과에 걸린다. 그리고 자료형도 신경써야한다. pair를 활용한 세그먼트 트리로 해결했다 /* 부분 배열 고르기 */ #include #include #include #include .. 이전 1 ··· 3 4 5 6 7 8 9 10 다음