본문 바로가기

Algorithm/BAEKJOON145

[백준] Solved.ac 랜덤 마라톤 (No. 27323, 15406, 22935, 5839, 14011, 23380, 14731, 1990) Solved.ac 랜덤 마라톤 후기 링크 ">HTML 삽입미리보기할 수 없는 소스 마라톤이 갱신 돼서 다시 풀어봤다. 이번에는 마지막 문제가 골드라 어떤 문제일까 기대하며 문제를 풀었다. 문제 + 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 후기] A. 직사각형 (1분)문제 링크" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 이 문제는 진짜 단순히 A*B를 출력하는 문제라 어려울 게 없는 문제였다... 더보기 구현#include using namespace std;int main() { int A, B; cin >> A >> B; cout B. Check the Check (14분)문제 링크".. 2024. 6. 15.

[백준/C++] 기말고사 작품전시 (No. 28094) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 작품마다 순서가 있어서 어떤 작품A가 작품 B보다 앞에 있는 경우 점수 V를 얻는 문제다. 여기서 A작품이 B작품이 앞에 있을 경우만 점수 V를 얻으므로, 두 작품을 비교하는 경우를 2차원 vector에 저장해 두고 작품의 순서가 정해지면, 순서가 vector[A][B]의 값을 구하면 된다. 그림을 통해 생각해 보면vector[A][B]는 A가 B보다 앞에 있는 경우 얻는 점수의 총 합이다. 그리고 점수를 얻는 경우 중 최대값을 구하고, 그 최대값을 얻는 경우가 총 몇 개인지 출력하면 된다. 모든 경우의 수는.. 2024. 6. 15.

[백준/C++] 보석 도둑 (No. 1202) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때, 정렬을 이용해 가장 가치가 높은 보석부터 가방에 넣을 수 있는지 확인하고, 무게가 가장 비슷한 가방에 넣으면 되겠다는 생각을 했다. 하지만, 문제는 사용한 가방에 있었다.이분 탐색으로 적절한 가방을 찾는 과정에서 이미 사용한 가방을 삭제하지 않고 처리할 적당한 방법이 떠오르지 않았다.(만약 삭제할 경우 삭제하는 과정에서 O(N)의 시간복잡도가 필요하기 때문에 문제의 시간복잡도는 O(N^2)이 된다.) 그래서 반대로 가방의 무게를 기준으로 보석을 찾도록 방법을 바꿨다. 하나의 가방에는 하나의 보.. 2024. 6. 12.

[백준/C++] 다각형의 면적 (No. 2166) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 말 그대로 다각형의 면적을 계산하는 문제다. 최근에 그래픽스를 공부하며 벡터에 대해 공부했기 때문에 쉽게 풀 수 있는 문제였다. 다각형의 넓이를 구하기 위해서 아래 그림과 같이 다각형을 분리한다. 위 그림의 파란색 부분의 넓이를 구하는 방법은 행렬식을 쓰면 된다. 1번 점에서 2번 점으로 가는 벡터와, 1번점에서 3번점으로 가는 벡터의 행렬식을 구하면 그 값의 절반이 삼각형의 넓이가 된다. $$ v1 = (x2-x1, \,y2-y1) \;\;\;\; v2 = (x3-x1, \,y3-y1) $$와 같이 벡터를.. 2024. 6. 11.

[백준/C++] 우수 마을 (No. 1949) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 사실 잘 보면 트리의 독립집합 문제와 크게 다를게 없는 문제다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 문제의 조건을 정리하면 우수 마을이 아닌 마을은 주변에 적어도 하나의 우수마을이 있어야 하며, 우수 마을인 마을은 인접한 마을에 우수 마을이 있으면 안된다. 그림을 보며 조건에 대해 생각해보자 위 그림과 같은 트리가 있을 경우 A마을이 우수 마을이면 B,C,D 마을은 우수 마을이 되면 안된다.그러므로 A마을이 우수 마을인 경우에는 B, C, D 마을이 우수마을이 아닌 경.. 2024. 6. 10.

[백준/C++] 트리의 독립집합 (No. 2213) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 아무 생각 없이 하나의 노드를 기준으로 두번 검사하면 되겠다는 생각을 했다. 하지만 예제의 입력을 보자마자 착각했다는 것을 깨닫고 다시 풀었다... 새로 푼 방법은 두가지 경우로 나눠서 계산하는 방법으로 트리를 그리면서 계산하는 방법이다. 먼저 그래프가 트리의 형태이므로 한 정점을 기준으로 트리를 그린다. 이후 현재 노드와 하위 노드들(자식 노드들)의 값을 포함해 만들 수 있는 독립집합의 최대값을 DP라는 배열에 저장한다. DP라는 배열을 그리는 이유는 중복된 계산을 줄이기 위해서다. 어떤 .. 2024. 6. 9.

[백준/C++] 최솟값 찾기 (No. 11003) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 보자마자 map의 정렬을 이용해 개수를 세면 O(N*logN)으로 쉽게 해결되겠다는 생각이 들었다. 그런데 막상 문제를 풀어보니 계속 시간초과가 났다... 결국에 priority_queue부터 Map, Set, 등의 여러 방법을 사용하다가 Map과 priority_queue는 삽입하는 과정이 느렸던게 생각나서 Union Find를 이용해 문제를 해결했다. + Union Find로 문제를 해결한 후 deque를 이용한 더 좋은 O(N)의 풀이가 있다는 것을 발견했다 ㅠㅠ 사실 Union Find를 이용한.. 2024. 6. 6.

[백준] Solved.ac 랜덤 마라톤 후기 (Feat. C++) Solved.ac 랜덤 마라톤 후기 링크 ">HTML 삽입미리보기할 수 없는 소스 이번에 새로 랜덤 마라톤 컨텐츠가 생겼다는 소식을 듣고 달려가서 해봤다. 티어가 낮아서 그런지 A문제를 뺀 나머지 문제가 전부 실버였다 ㅜㅜ 랜덤 문제는 지금까지 한 번 밖에 풀어본 적이 없어서, 이번 기회에 태그나 힌트를 안보면 문제를 얼마나 잘 풀지 확인 차 마라톤을 시작했다. 문제 + 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 문제를 풀 때 시간이 얼마나 걸리는지 같이 측정해야 실력이 어느정도 가늠이 될 것 같아서 시간을 재면서 풀었다. [문제 후기] A. Anti-Palindrome (17분)문제 링크" data-ke-type="html".. 2024. 6. 5.

[백준/C++] ACM Craft (No. 1005) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 건물을 짓기 위해서 다른 건물을 먼저 지어야 된다는 선행조건이 있는 문제다. 이때, 각 건물은 동시에 지을 수 있다. 그러므로 특정 건물을 짓기 위해 필요한 시간을 아래와 같이 표현할 수 있다.Build(X) = max( Build (X건물을 짓기 위해 사전에 지어야 하는 건물) ) + (X 건물만 짓는데 걸리는 시간)그러므로 이 문제는 DP 문제로 생각할 수 있다. X건물을 짓기 위한 다른 건물을 짓는 시간을 알면, X건물을 짓는데 걸리는 시간을 알 수 있기 때문이다.(즉, 작은 문제를 해결함으로써 큰.. 2024. 6. 4.

[백준/C++] 트리와 쿼리 (No. 15681) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 루트노드가 주어지면 그 노드를 기준으로 트리를 그리면 되는 문제다. 단지 그냥 트리를 그리는 것과 다른 점이 있다면, 자식 노드의 수가 몇 개 인지 쿼리를 통해 출력한다는 점이다. 여기서 매번 쿼리가 들어올 때 마다 자식 노드의 수를 계산한다면 매우 많은 반복이 생기게 된다. 그러므로 애초에 트리를 그릴 때 자식노드가 몇 개 인지 return을 해준다면 한번의 트리를 그림으로써 모든 노드의 자식의 수를 알 수 있게 된다. 이제 아래 그림을 통해 어떻게 진행되는지 알아보자 위 그림과 같은 트리가 있을 경우 트리.. 2024. 6. 3.

[백준/C++] 전력난 (No. 6497) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 모든 집에서 다른 집으로 이동하기 위해서는 길에 가로등이 켜져있어야 하며, 다른 집을 거쳐서 이동할 수 있다. 이때, 가로등을 최소로 켜두면 얼마만큼의 비용을 절약할 수 있는지 계산하는 문제다. 즉, 모든 집들이 연결되어 있을 경우의 최소 비용을 구해 총 비용에서 빼면 절약한 비용이 나오므로, MST 문제임을 알 수 있다. 제한 사항을 보면 m과 n이 200,000이므로 prim 알고리즘이나 크루스칼 알고리즘을 이용해 문제를 풀면 된다. 나는 모든 간선을 우선순위 큐에 넣어서 최소 비용을 구하는 방법으로 문제.. 2024. 6. 2.

[백준/C++] 우주신과의 교감 (No.1774) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 풀었을 때, 단순히 크루스칼 알고리즘으로 풀었다. 외계신들 간의 거리만 계산해 priority_queue에 넣으면 매우 쉽게 풀 수 있기 때문이다. 문제는 크루스칼 알고리즘이나 heap을 이용한 prim알고리즘은 시간복잡도가 O(ElogV)인데, 이 문제에서 E=V^2이기 때문에 O(V^2)의 prim알고리즘을 사용하면 더 빨리 문제를 해결할 수 있다. O(V^2)의 prim알고리즘을 간단히 설명하면 정점은 {현재 방문한 노드}와 {아직 방문하지 않은 노드}의 두 집합으로 나눌 수 있다. 여기서, 현재.. 2024. 6. 1.

[백준/C++] 다리 만들기 2 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 보면 섬의 개수도 적고 격자의 크기도 생각보다 작기 때문에 풀이 방법만 잘 생각하면 여유롭게 풀 수 있는 문제다. 먼저 섬과 다른 섬의 연결은 오직 직선으로 만들어진 다리로 연결되어야 하며, 이 때 다리의 길이는 2 이상이어야 한다. 위 조건에 맞게 섬끼리 연결되는 다리의 길이만 계산하면 Prim 알고리즘이나 크루스칼 알고리즘을 이용해 모든 섬이 연결되는데 드는 최소 비용계산할 수 있다. 그렇다면 어떻게 섬끼리 연결되는 다리의 길이를 계산할지 알아보자. 먼저 하나의 섬에는 같은 번호가 오도록 아래 그림과 같.. 2024. 5. 31.

[백준/C++] 별자리 만들기 (No. 4386) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 이름만 다르지 사실 이전에 풀었던 최소 스패닝 트리 문제와 다를게 없다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 왜냐하면 모든 별을 잇는 최소 비용을 계산하는게 목적인 문제이므로, 각 별 들을 잇는 간선의 비용을 계산해 어떤 별들을 잇는 간선인지 저장하면 MST 문제가 된다. 두 점의 거리를 계산하는 방법은 (x1, y1), (x2, y2) 일 경우 두 점의 거리 s^2 = (x1-x2)^2 + (y1-y2)^2 를 이용해 계산하면 된다. 이제 두 점의 거리를 계산하.. 2024. 5. 30.

[백준/C++] 최소 스패닝 트리 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 최소 스패닝 트리를 구하는 문제로 모든 노드가 연결되어 있어야 한다. 단순히 비용을 기준으로 정렬을 한 다음 두 노드가 연결될 경우에 방문 처리를 하면 떨어진 섬과 같은 경우가 발생하기 때문에 방법을 생각해 봤다. Union-Find를 사용하면 떨어진 경우를 제외할 수 있을 것 같았지만, 굳이 그럴 필요가 없을 것 같아서 그냥 priority_queue를 이용해 단순하게 풀었다. (나중에 찾아보니 Prim 알고리즘 방식이었다..) 이 priority_queue는 비용을 기준으로 오름차순 정렬 되어 있다. 먼.. 2024. 5. 30.

이전 1 2 3 4 5 6 7 ··· 10 다음

티스토리툴바