본문 바로가기

전체보기

 (168)
백준 14425 문자열 집합 https://www.acmicpc.net/problem/14425 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어� www.acmicpc.net 문자 prefix, suffix 어느 문자 집합에 넣는다는 류의 문제는 트라이를 생각해봄직하다(+ 공간복잡도가 널럴할 때) 이 문제도 트라이를 이용해서 풀 수 있다. /* 문자열 집합 */ #include #include using namespace std; struct trieNode { bool is_terminal; trieNode* trie[26]; tri..
백준 2437 저울 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓� www.acmicpc.net 그리디 알고리즘을 이용한 문제다. 부분합을 이용할 생각을 하다가 '에이 아니겠지' 했는데 부분합을 이용하는 문제여서 반성하게 된다. 수학 문제를 풀 때도 그랬지만 Try가 중요한 것 같다. 내 생각에 대해서도 자비의 원칙을 적용했다면, 이 문제를 수월하게 풀수도 있지 않았을까. /* 저울 */ #include #include #include using namespace std; vector chu; int..
백준 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을 보게 된다. 운 ..

티스토리툴바