백준문제풀이36 [백준][C++] 1238번: 파티 <203> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 다익스트라를 딱 2번만 적용하면 되는 문제이다!! 문제는 처음에 각 정점에서 X로 가는 비용을 구하려면, 각 정점의 수만큼 다익스트라를 진행해줘야 된다는 점 이다. 다익스트라의 시간 복잡도는 O(ElogV) 인데, 총 정점의 수만큼 돌면 =.. Algorithm/백준 2022. 3. 23. [백준][C++] 10830번: 행렬 제곱 <202> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이런 N승 문제는 기본적으로 진짜로 N승 해버리면 대부분 못푼다. 지금 까지 내가푼 대부분의 N승 문제의 결론은 O(logN) 안에 해결되도록 코드를 구서해야된다는 점 이다. 예를 들어 A의 6승을 구해야 한다면 A를 진짜 6번 곱하는 것 이 아니라, A의 3승을 2번 곱하면 된다. => (A*A*.. Algorithm/백준 2022. 3. 22. [백준][C++] 1504번: 특정한 최단 경로 <201> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 나의 생각 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 최단거리를 구하는 문제니 다익스트라 알고리즘이 떠올랐다. 문제는 특정한 지점 A, B 를 반드시 지나쳐야 한다는 점 이다! 가능한 case는 다음과 같다. 1) start -> A -> B -> end 2) start -> B -> A.. Algorithm/백준 2022. 3. 17. [백준][C++] 1043번: 거짓말 <200> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 Union Find 알고리즘을 알아야 해결하기 쉽다. 관련 내용을 정리한 글이 있으니 먼저 읽어보기를 권장한다! 그 파티에서 거짓말을 할 수 있다! 각 파티의 경우마다 오는 사람들의 번호를 vector adj 에 담아주었다. 총 2번 사용하게 되기 때문이다. 1) 처음 사람들을 union 시킬때 2) 거짓말을 할 수 있는 파티인지를 확인할 때 맨 처음 모두 자신의 부모로 자기 자신을 가리키도록 해준다. parent[1]은 1, parent[2] 는 2 ... 이런식으로 말이다! 이후 각 파티를 돌면서 Union 연.. Algorithm/백준 2022. 3. 16. [백준][C++] 12581번: 숨바꼭질 2 <199> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 생강의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기존 숨바꼭질 문제에서는 한번 방문한 지점은 다시 큐에 넣지 않았었다. 하지만 숨바꼭질 2 문제에서는 방법의 가지수까지 고려해야하므로 Queue에서 pop할 때 해당 지점을 방문했다고 표시하는 것이 핵심이다. 예를 들어, N=1 K=4를 입력할 경.. Algorithm/백준 2022. 3. 14. [백준][C++] 5693번: 이진 검색 트리 <197> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 이번 문제는 예전에 비슷한 문제를 풀어본 적 있어서, 보자마자 분할 정복(재귀) 방식의 풀이를 떠올렸다. 우선 전위 순휘를 나열해보면 50 30 24 5 28 45 98 52 60 전위 순회에서 root노드는 50이 되고, 앞에서 부터 순서대로 읽어을 때, 50 보.. Algorithm/백준 2022. 3. 8. [백준][C++] 1865번: 웜홀 <196> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 워프를 통해서 시간을 되돌릴 수 있다는 말을 보자마자 생각난것은 음의 가중치를 갖는 간선 이였다. 이 문제는 음의 가충치를 갖는 사이클이 있는지 확인해야 하는 문제이다. 따라서 벨만 포드 알고리즘이 적합하다. 벨만포드 알고리즘의 sudo 코드는 다음과 같다. // 입력: 가중치 그래프 G // 출력: dist 배열, dist[u]는 v에서 u까지의 최단거리 BellmanFord(G, v) { for each u ∈ V dist[u] Algorithm/백준 2022. 3. 6. [백준][C++] 2749번: 피보나치 수 3 <194> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이 문제는 피사노 주기 에 대한 개념이 있어야 풀 수 있다. 다음 문제를 먼저 풀어보기를 권장한다. HTML 삽입 미리보기할 수 없는 소스 피보나치 수열을 구하는 방식으로 " data-og-host="blogshine.tistory.com" data-og-source-url="https://blogshine.tistory.com/269" data-og-url="https://blogshine.tistory.com/269" data-og-image="https://scrap.kakaocdn.net/dn/lfBxO/hyNA.. Algorithm/백준 2022. 3. 2. [백준][C++] 9471번: 피사노 주기 <193> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 피보나치 수열을 구하는 방식으로 수들을 구를 구하되, 나머지 연산을 중심으로 생각해야 한다. 나머지들이 얼마나 부분수열을 이루는지 알아야 하기 때문이다. 주어진 M으로 나눠주면서 vector에 push 하였고, 벡터의 맨 마지막 원소가 0 그리고 마지막 바로 한칸 앞 원소가 1 일 때 종료한다. 다시 피보나치 수열이 1부터 반복하게 된다. 나의 코드 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 #include using namespace std; int P; int pisano(int nu.. Algorithm/백준 2022. 3. 1. [백준][C++] 9663번: N-Queen <190> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이번 문제를 스스로 다 해결하지 못해 아쉬움이 남는다... 정리라도 잘 해두어야 겠다. Queen은 가로, 세로, 대각선으로 이동이 가능하다. 이 문제는 이러한 Queen을 배치시킬 수 있는 총 경우의 수를 구해야 한다. 또한 Back Tracking 알고리즘을 적용해야한다. 탐색을 진행하다가.. Algorithm/백준 2022. 2. 23. [백준][C++] 9251번: LCS <189> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이 문제는 두 개의 문자열이 주어졌을 때, 최장 공통 부분 수열(Longest Common Subsequence)을 찾는 문제이다. 마지막 글자를 비교한다고 생각하면서 풀면 편하다. 두 문자열 "ABCDE"와 "ABDHE"를 생각해 보자... Algorithm/백준 2022. 2. 21. [백준][C++] 2206번: 벽 부수고 이동하기 <188> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 진짜 중요한 점을 배웠다. 그냥 단순 BFS로 생각하면 막히는 문제이다. 분명 논리적으로 맞는것 같지만, 기존 BFS 보다 한끝 더 생각해야 하는 중요한 부분이 있다. 핵심부터 말하면 visited[1000][1000][2] 과 같이 3차원 배열.. Algorithm/백준 2022. 2. 20. 이전 1 2 3 다음
