반응형 Algorithm/BAEKJOON145 [백준/C++] 가장 가까운 공통 조상 (No. 3584) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 트리가 주어지면 특정 노드들 간의 공통조상을 구하면 되는 문제다. 처음부터 자식노드와 부모노드를 알려주기 때문에, 두 노드 a, b 의 공통조상을 구하기는 쉽다.왜냐하면 두개의 노드를 따라서 부모노드를 찾아가면 공통 조상들을 찾을 수 있기 때문이다. 여기서 우리는 가장 가까운 공통 조상을 찾아야한다. 가장 가까운 공통 조상을 찾는 방법도 간단하다. 먼저 a 노드에서 출발해 최상위 조상까지 올라가며 어떤 노드가 a 노드의 조상인지 파악한 뒤 방문 처리를 한다.그러면 이제 b에서 출발해 조상을 찾아가며 처음으로 .. 2024. 8. 2. [백준/C++] 문제집 (No. 1766) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 위상정렬을 이용하고, 어떤 경우에 문제를 빨리 출력할지 구분하면 쉽게 해결할 수 있는 문제다. 조건에 따르면 더 쉬운 문제를 먼저 풀 수 있다면 먼저 풀어야 한다.그러므로 1번 문제부터 사전에 풀어야 하는 문제가 몇 개인지 파악한다. 이제 위상정렬을 떠올리면, i번 문제를 풀 수 있는 경우 i번 문제를 풂으로써 i번째를 사전에 풀어야하는 문제들은 사전에 풀 문제가 1개씩 줄어든다는 사실을 알 수 있다. 이를 이용해 for 문으로 1번 문제부터 사전에 풀어야 하는 문제가 0인지 미리 풀어야 하는 문제가 있는지 .. 2024. 7. 15. [백준/C++] 최종 순위 (No. 3665) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 풀기 전에 위상 정렬 문제를 풀었었다. 위상 정렬의 특징은 정렬할 때, 특정 노드로 들어오는 간선의 수를 이용하면 노드간의 상대적인 우선 순위를 이용해 정렬을 할 수 있다는 특징이 있었다. 그래서 이 문제도 위상정렬의 특징을 이용해 풀었다. 이 문제의 핵심은 모든 팀의 확실한 순위를 알게 되는지 판단하는 것이다. 확실한 순위를 알기 위해서는 처음에 특정 노드로 들어오는 간선이 0인 노드가 1개여야하며, 서로 다른 팀 간에 우선순위를 확실하게 알아야 하기 때문에 특정 노드에서 출발하는 간선을 하나씩 지울때 마다.. 2024. 7. 8. [백준/C++] 색상환 (No. 2482) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 저번에 풀었던 RGB거리 2와 사실 크게 다르지 않은 문제다"> HTML 삽입미리보기할 수 없는 소스 단지 차이점이 있다면, 저번 문제에서는 가중치를 구해야 했다면, 이번 문제는 경우의 수를 구하는 것이다. 문제의 핵심은 색을 칠하기 위해서 i번째 색을 선택하면 i-1번째 색과 i+1번째 색을 선택할 수 없다는 것이다. 그러므로 i-1번째 색을 사용했다면, i번째 색을 사용할 수 없고 i-1번째 색을 사용하지 않았다면 i번째 색을 사용할 수 ㅣㅆ다는 점을 이용해 N번째 색에 도달할 동안 몇 개의 색을 선택했는.. 2024. 7. 3. [백준/C++] RGB거리 2 (No. 17404) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 N번째 집이 N-1번째 집과 N+1번째 집의 색과 다르게 색칠하는 경우 최소의 비용을 구하는 문제다. 단, 1번 집과 N번째 집도 서로 색이 달라야 한다. 즉, 처음과 끝이 연결된 원탁과 같은 경우다. 하지만 처음과 끝이 연결됐다고 해서 크게 어려운 문제는 아니다.처음과 끝의 경우를 고려해 탐색하면 쉽게 풀 수 있는 문제다. i번째 집을 색칠하기 위해서는 마지막에 색칠된 i-1번째 집과 i번째 집의 색이 다르면 된다.그러므로 i번째 집을 R로 색칠하기 위해서는 i-1번째 집을 G, B로 색칠하는 경우만 고려하.. 2024. 7. 1. [백준] Solved.ac 랜덤 마라톤 (No. 6903, 11896, 15410, 11501, 9335, 6207, 2467, 12796) Solved.ac 랜덤 마라톤 풀기 링크 ">HTML 삽입미리보기할 수 없는 소스 문제 + 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 후기] A. Trident (9분)문제 링크" data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 간단하게 문제의 조건에 따라 삼지창을 그리면 된다.for문을 이용하면 쉽게 그릴수 있는 문제다. 더보기 구현#include #include #include #include #include #include #include using namespace std;int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); i.. 2024. 6. 28. [백준/C++] 박성원 (No. 1086) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 매우 큰 수를 입력받아 처리를 해야하는 문제다. 이외에도 N이 15로 큰 값이기 때문에 (15!)을 전부 계산하면 시간 초과가 나게 된다. 그래서 이러한 반복을 줄이는 방법은 나머지를 이용하는 방법이다. 예를 들어 아래와 같은 경우를 생각해보자. 그러면 17, 6 순서로 정수를 만드는 경우와 6, 17 순서로 정수를 만드는 경우는 나머지가 1로 같다. 이를 이용하면 176333과 617333의 나머지가 같음을 알 수 있다.(왜냐하면 176과 617의 나머지가 1이였으므로, 333을 뒤에 붙이면 1333 이 .. 2024. 6. 27. [백준/C++] 외판원 순회 (No. 2098) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 외판원 순회 문제의 풀이에 대한 개념은 예전에 공부해서 알고 있었다. 하지만 이를 실제로 문제에 적용해 보는 것은 처음이라 머릿속에서 바로 구현이 떠오르지 않았다. 맨 처음 푼 방법은 [시작마을][직전에 방문한 마을][방문한 마을을 표시하는 비트] 정보를 저장할 3차원 vector를 만들어 BFS로 탐색을 하는 것이었다. 실제로 이렇게 풀었더니 매우 직관적이어서 쉽게 구현이 됐다. 이후에 다른 사람들의 코드를 보고 시작마을을 정하고 탐색을 시작해도 된다는 사실을 깨달았다. 생각해보니 A 마을에서 시작해 A 마을로 돌아오.. 2024. 6. 24. [백준/C++] 집합 (No. 11723) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 DP문제를 풀기 전 비트마스킹에 익숙해지라고 나온 문제다. 사실 이 전에 N-Queen 문제와, SWEA의 XOR 문제를 풀면서 익숙해졌기 때문에 쉽게 풀 수 있는 문제였다. 이 문제에서 숫자가 1~20밖에 없으므로 시프트 연산을 이용해 특정 자릿수에 해당하는 수가 집합에 있는지 없는지 찾으면 된다. 이 과정에서 숫자를 추가할 때는 or 연산으로 추가하고 Check를 하는 과정은 and 연산으로 해결했다. 예를 들어 2^3과 num이라는 수를 or 연산하면 3번째 자리는 수가 켜지게 된다. 또한 2^3과 nu.. 2024. 6. 23. [백준/C++] 최고의 초콜릿 성지순례 (No. 31461) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 그리디하게 풀 수 있는 문제다. 문제의 조건에서 한번 들린 초콜릿 가게는 다시 들릴 수 없으며, 출발점과 도착점이 정해져있다. 이를 이용하면 초콜릿 가게를 어떤 순서로 방문할지 쉽게 파악할 수 있다. 왜냐하면 최종적으로 초콜릿 맛의 점수가 가장 높도록 방문할 경우 점수가 가장 높은 값만 구하면 되기 때문이다.위 그림을 보면 S에서 E로 도착하기 위해서는 보라색 구간은 필수로 지나야하는 구간이다.반면, S의 왼쪽과 E의 오른쪽은 지나도 되고 지나가지 않아도 되는 구간이다. 이를 이용하면 S의 왼쪽 구간의 점수가.. 2024. 6. 21. [C++/백준] 두 원 (No. 7869) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 삼각형의 선분과 사잇각에 대해 알고 있으면 쉽게 풀 수 있는 문제다. 처음에 직접 교점의 좌표를 구해서 풀어야 하나? 생각이 들었지만, 다시 생각해보니 r1, r2, 두 원점사이의 거리를 알고 있기 때문에 쉽게 풀 수 있겠다는 생각이 들었다. 아래 그림을 보며 어떻게 경우를 분류할지 생각해보자 먼저 아래 경우는 두 원이 겹치지 않는 경우다. 중점사이의 거리 d가 r1+r2보다 크거나 같으면 두 원은 겹치는 적이 없다. 아래는 두 원 중 한 원이 다른 원에 포함되는 경우다. 두 원 중 큰 원의 반지름 r1.. 2024. 6. 20. [백준/C++] 선분 그룹 (No. 2162) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 선분 교차 3와 크게 다를게 없는 문제다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스단순히 여기에 union_find가 합쳐진 문제다. 먼저 n개의 선분에 대해 선분 a가 다른 선분들과 교차하는지(만나는지) for문으로 체크를 해준다. 이때, 선분이 교차하는지 확인은 외적을 이용할 수 있다. 위 그림처럼 선분 a와 b가 교차한다면 외적한 값 v1, v2의 부호가 다름을 알 수 있다.이때, 하나의 선분을 기준으로 판단을 하면 안된다. 왜냐하면 오른쪽 그림처럼 외적 했을 때, a선분을 기.. 2024. 6. 19. [백준/C++] 집으로 (No. 1069) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제는 단순히 거리를 계산하면 쉽게 풀 수 있는 문제다. 먼저 점프해서 이동하는 이동거리 D를 이동 시간 T로 나눈 값이 1보다 작다면 걸어가는 것 보다 느리기 때문에 점프를 이용할 이유가 없다. 반대로 점프할 경우가 이득이라면 3가지 방법으로 나눌 수 있다. 그전에 n은 (0, 0)에서 목적지인 A 점 까지의 이동거리를 D로 나눈 값이다.여기서 n을 계산하는 이유는 A점까지 n번 점프하고 남은 거리를 걸어가는 방법을 계산하기 위해서다. 1. (0, 0)에서 직선거리로 점프를 n번 한 다음 걸어서 목적지인 A지점에 .. 2024. 6. 18. [백준/C++] 선분 교차 3 (No. 20149) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이전에 풀었던 선분 교차 2에서 교점의 좌표만 추가된 문제다." data-ke-type="html">HTML 삽입미리보기할 수 없는 소스그렇기 때문에 이전의 코드에서 좌표를 계산하는 부분만 추가했다. 이전 코드에 교점이 있는 경우 그 교점의 범위가 선분의 범위에 들어오는지 체크하기 위해 교점의 좌표를 x, y로 직접 구했었다. 그래서 실제 교점을 찾기 위해서는 이전에 구한 x좌표, y좌표를 이용하면 된다.여기서 주의해야할 점은 허용오차가 매우 작기 때문에 double형을 사용해야하며 부동소수점으로 인한 오차가 커지지 않.. 2024. 6. 17. [백준/C++] 선분 교차 2 (No. 17387) 문제 문제 설명 ">HTML 삽입미리보기할 수 없는 소스 풀이 " data-ke-type="html">HTML 삽입미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 풀 때 단순히 연립 방정식을 이용해 풀었다. 연립 방정식을 만들면 교점인 x축의 좌표를 계산할 수 있는데, 이 때 x축의 분모가 0이면 평행하다는 뜻이다.(행렬식인 det를 계산해 det가 0인지 판단하는 방법과 동일) 여기서 중요한 점은 기울기가 같아도 교점이 있는 경우가 있다. 기울기가 같은데 교점이 있다는 것은 일차함수로 바꿨을 때 겹친다는 뜻이다. 여기서 겹치는지 확인하는 방법은 간단하게 y절편을 기준으로 y절편 값이 같은지 확인했다.만약 y절편이 같다면 두 선분은 하나의 일차함수에 겹치는 선분이.. 2024. 6. 16. 이전 1 2 3 4 5 6 ··· 10 다음 반응형
