Algorithm/백준79 [백준][C++] 2467번: 용액 <206> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 투포인트 알고리즘을 적용하면 된다. 1) left = 0, right = n-1로 시작해 두 용액의 합을 찾습니다. 2) 두 용액의 합에 대해 절댓값이 기존의 값보다 더 작다면 현재 합을 갱신해줍니다. 그리고 정답에 대한 값 또한 갱신해줍니다. 3) 현재 left과 right의.. Algorithm/백준 2022. 3. 28. [백준][C++] 16953번: A → B <205> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16953번: A → B 첫째 줄에 A, B (1 ≤ A HTML 삽입 미리보기할 수 없는 소스 이번 문제는 예전에 비슷한 문제를 푼 경험이 있어 금방 해결하였다. 역으로 해결해 나가면 된다! 예를 들어 다음과 같은 예시가 있다고 해보자 2 162 이를 역으로 162 -> 81 -> 8 -> 4 -> 2 가 될수 있다. B부터 시작하여 A를 만들어 간다고 생각하면 편하다. B에서 마지막 숫자가 1로 끝나면 => 기존 A의 수에 1추가 연산으로 B가 된것 B에서 마지막 숫자가 1이 아니고, 2로 나누어 떨.. Algorithm/백준 2022. 3. 25. [백준][C++] 11779번: 최소비용 구하기2 <204> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 간단한 다익스트라 문제이다. 다만 역으로 추적하면서 지나온 경로를 기록하는 방식을 설명해볼까 한다. 이름이 road인 1차원 배열을 하나 만들었다. road[now] = prev 의 의미는 "now번 정점에 최소 비용으로 도달하기 위해서는 prev정점으.. Algorithm/백준 2022. 3. 24. [백준][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++] 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. 이전 1 2 3 4 5 6 7 다음
