Algorithm115 [백준][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++] 9935번: 문자열 폭발 <198> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 처음에는 Stack을 직접 사용하면서 해결하려 했는데, 맨 뒤 문자열을 삭제하는 과정이 조금 힘들어 졌다. 따라서 다른 분의 글을 좀 참고하여 String 자체를 stack으로 생각하고 해결하는 방식으로 풀었다. 우선 비어있는 res라는 String에 한 글자씩 넣어 .. Algorithm/백준 2022. 3. 9. [백준][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++] 11444번: 피보나치 수 6 <195> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 이번문제는 저의 머리로는 생각하지 못한 방식이라 다른 분들의 글들을 확인하면서 해결하였습니다. 정리라도 잘 해놓기 위해 글을 작성해 봅니다. 현재의 피보나치 수와 이전 피보나치 수를 각각 1행, 2행에 배치한 2X1 행렬을 생각해보자. 다음으로 오는 피보나치 수를 구하려면 두 수를 더한 수를 첫 번째 행에, 기존의 첫 번째 행에 있던 피보나치 수는 두 번째 행으로 이동시킨다 이런 동작은 아래와 같은 행렬 곱셉으로 간단하게 수행할 수 있다. 즉, 점화식을 행렬로 만들어 보면 다음과 같아진다. Fn+2 즉, 다음으로 오는 .. Algorithm/백준 2022. 3. 4. [백준][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++] 10826번: 피보나치 수 4 <192> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 바로 생각나는 방식은 DP를 활용하면서 long long 형 변수를 사용하는 방식이였다. 하지만 이와 같은 방식으로 해결하려 하면 숫자가 너무 커져서 해결할수가 없다. 따라서 string을 사용하는 방식으로 변경해야 한다. 두 string을 더하는 함수가 핵심이다. string sum(string a, string b){ int num = 0; int carry = 0; string result = ""; reverse(a.begin(), a.end()); reverse(b.begin(), b.end()); while(.. Algorithm/백준 2022. 3. 1. [백준][C++] 2263번: 트리의 순회 <191> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구해야 하는 문제이다. 다음 이진트리를 우선 살펴보자. 중위 순회 : 8 4 9 2 5 1 6 3 7 후위 순회 : 8 9 4 5 2 6 7 3 1 우리는 후위 순회를 통해 root 번호를 알수가 있다. 후위 순회의 마지먹 번호인 1이 root에 해당.. Algorithm/백준 2022. 2. 24. [백준][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. 이전 1 ··· 4 5 6 7 8 9 10 다음
