백준72 [백준][C++] 16120번: PPAP (266) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 입력이 1,000,000까지라 O(NlogN), O(N) 안에 해결해야겠다는 생각부터 들었다. 그런데 경험상 이런 문자열 처리는 대부분 O(N)에 처리하는 문제였기에, 문자열을 처음부터 끝까지 한 번만 탐색해서 처리하는 방식을 생각하게 되었다. 문제는 이해만 하면.. Algorithm/백준 2023. 3. 21. [백준][C++] 6987번: 월드컵 (263) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6987 6987번: 월드컵 월드컵 조별 최종 예선에서는 6개국으로 구성된 각 조별로 동일한 조에 소속된 국가들과 한 번씩, 각 국가별로 총 5번의 경기를 치른다. 조별리그가 끝난 후, 기자가 보내온 각 나라의 승, 무승부 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 보자마자 떠오른 방식은, 모든 팀은 게임을 할때마다 3가지 경우(승리, 비김, 패배)중 하나의 경우가 나온다 생각하였다. 또한 6개팀이 승부하는 경우의 수는 15가지 이다. A: {B, C, D, E, F} B.. Algorithm/백준 2023. 2. 9. [백준][Java] 22868번: 산책 (257) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/22868 22868번: 산책 (small) 첫 번째 줄에는 정점의 개수 $N$과 두 정점 사이를 잇는 도로의 개수 $M$이 공백으로 구분되어 주어진다. 두 번째 줄부터 $M + 1$ 번째 줄까지 정점 $A, B$가 공백으로 구분되어 주어진다. 정점 $A$와 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 최근 들어 가장 삽질 많이한 구현 문제인것 같다... 우선 풀이는 다음과 같다. S -> E로 가는 모든 경로를 완전탐색한다. (다익스트라도 가능할 것 같다) 이런 문제같은 경우 인접 .. Algorithm/백준 2022. 12. 9. [백준][C++] 2632번: 피자판매 (256) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 2632번: 피자판매 첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 (3 ≤ m, n www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 연속된 부분합의 수를 잘 구해야 하는 문제이다. 우선 input 범위가 1000 까지라고 명시되어있으니, 그냥 O(n^2) 방식으로 2중 for문 돌면서 구하는 방식으로 합을 구하면 된다. (ps O(n^2) 알고리즘은 input이 1만까지 안정권 이라 알고.. Algorithm/백준 2022. 11. 2. [백준][C++/Python] 2225번: 합분해 (254) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 솔직하게 이거 나는 DP인거 생각 못했다. 그냥 BFS로 완전탐색 해야 하나? 이런 생각부터 들었던것이 사실이다. 해결방법이 딱 떠오르지 않아 다른 분들의 글을 좀 읽어본 후에서 야 DP임을 깨닫고 풀이방법을 읽어보게 되었다. 우선 DP배열을 정의해야 한다. DP[a][b] 는 숫자 a개로 합이 b가 되는 경우 를 의미한다. DP[3][.. Algorithm/백준 2022. 10. 12. [백준][C++/Python] 1912번: 연속합 (253) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 일단 처음에 보고 딱 DP를 생각하지는 않았다. 다만 input값이 100000 까지라는 점이 매우 거슬렸다. 나또한 맨처음에는 2중 for문 도는 방법이 생각났지만, 그러면 100000,00000 O(n^2) 까지라는 소리인데.. Algorithm/백준 2022. 10. 12. [백준][C++/Python] 14002번: 가장 긴 증가하는 부분수열 4 (252) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제의 핵심은 역추적을 어떤 방식으로 진행할것이지? 이다. 우선 점화식을 세워보면, DP[i]는 A[1] ... A[i]까지 수열.. Algorithm/백준 2022. 10. 11. [백준][C++/Python] 1655번: 가운데를 말해요 (251) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 사실 다행이도 문제를 보자마다 Heap이 가장 먼저 떠올랐다. 각각 최소힙과, 최대힙 을 사용하여 잘 처리하면 될것같은데? 라는 생각을 하였다. 우선 짝수, 홀수 순서로 나누어 삽입연산을 진행한다. 숫.. Algorithm/백준 2022. 10. 10. [백준][C++] 스타트와 링크 (246) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이번 문제는 백트래킹 알고리즘의 대표적인 문제라 생각되어 정리해본다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 vec1, vec2 각각에 모든 사람의 번호를 집어넣어서 가능한 모든 케이스를 구하되 애당초 불가능 경우 바로 return 하면 됩니다. 이게 무슨 의미일까요? 불.. Algorithm/백준 2022. 9. 22. [백준][C++] 6593번: 상범 빌딩 <242> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 너무나 단순한 BFS 탐색 문제이다. 우선 우리는 좌표와 몇분이 걸리는지를 저장하기 위해 Position이라는 Class를 다음과 같이 정의하자. class Position { public: int x, y, z; i.. Algorithm/백준 2022. 9. 5. [백준][C++] 7569번: 토마토 <241> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번문제는 Queue를 얼마나 잘 활용하는지가 핵심이다. 보통 BFS문제는 (!Q.size)동안 반복문을 돌게 된다. 문제는 이렇게 한번에 다 BFS탐색을 돌면, 하루안에 모든 과일이 익은것 처럼 코드가 작동한다. 우리는 하루마다 이미 익어있는 토마토에 인접한 토마토만 익도록 만들어야 한다. 따라서 BFS도 하루 단위로 동작해야 한다. 그래야 총 몇일이 소모됬는지 확인할 수 있다. 이를 위해서는 Queue의 사이즈를 이용해야 한다. 문제의 input을 보자. 5 3 1 0 -1 0 0 0 -1 -1 0 1 1 0 0 0.. Algorithm/백준 2022. 9. 1. [백준][C++] 2410번: 2의 멱수의 합 <240> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 1. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 동전1 문제와 매우 유사한 문제입니다. 우선 DP[i] : i를 2의 멱수로 표편하는 방식의 수 라고 정의합시다. DP[i]를 구하는 방법은 DP[i-1] + DP[i-2] + DP[i-4] + DP[i-8] + ... + DP[0] 로 구할수 있습니다. 예를 들어 문제의 예시인 7을 구한다 생각해봅시다. 2^0(1) 일때의 모든 DP 배열을 채우면 다음과 같다 1로만 각 수를 만들수 있는 경우는 전부 1가지 이다. i = 1 2 3 4 5 6 7 DP[i] 1 1 1 1 1 1 1 2^1(2) 일때의 모든.. Algorithm/백준 2022. 8. 18. 이전 1 2 3 4 ··· 6 다음
