백준72 [백준][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++] 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++] 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. [백준][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. [백준][C++] 1629번: 곱셈 <187> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 입력으로 받을 A, B, C 모두 int형으로 담을수 있는 값이다. 하지만 A^B를 한다 했을때, 이를 직접 계산하려면 1) 변수 크기도 엄청 커지게 된다. 2) 자료의 크기 1억당 => 1초 정도 걸리기 때문에, 2^2,147,483,647 만 계산하려 해도 21초나 걸린다. 따라서 이를 분할정복으로 해결해야 한다. 예를들어 2^8을 구해야 핸다.. Algorithm/백준 2022. 2. 17. [백준][C++] 16719번: ZOAC <186> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 와 이번문제 나는 어려웠다. 단순하게 A부터 찾아서 추가하는 식으로 해결하기도 어렵다. 왜냐하면 문자는 중복이 가능하기 때문이다. A가 2개 이상이라면 어디부터 시작해야 할까? 이또한 문제이다... 따라서 나는 다음과 같은 알고리즘으로 문제를 해결해 나갔다. (다른분의 풀이를.. Algorithm/백준 2022. 2. 14. [백준][C++] 14601번: 샤워실 바닥 깔기 (Large) <185> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 14601번: 샤워실 바닥 깔기 (Large) 첫 번째 줄에는 바닥의 한 변의 길이를 표현하는 자연수 K(1 ≤ K ≤ 7) 가 주어진다. 이때 바닥의 크기는 2K 가 됨에 유의하라. 두 번째 줄에는 배수구의 위치를 나타내는 자연수 x, y (1 ≤ x, y ≤ 2K) www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 문제를 해결하기에 앞서, 출력하는 부분부터 매우 거슬리는 문제이다. 보통 시작점을 왼쪽 상단으로 두는데, 이번 문제는 시작지점이 왼쪽 하단이다. 이점 또한 주의해야 한다. 우선 이번 문제를 해결하기 위해 L-트로미노에 .. Algorithm/백준 2022. 2. 13. 이전 1 2 3 4 5 6 다음
