Algorithm/백준79 [백준][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. [백준][Python] 10282번: 해킹 (265) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이번 문제는 다익스트라를 알면 금방 해결할 수 있는 문제이다. 문제는 다익스트라인 것을 어떤 부분에서 눈치챌 수 있을까? 사실 문제만 읽으면 최단경로를 구해야 한다는 점이 명확하게 보이지 않을 수 있다(적어도 나는 그랬다.. Algorithm/백준 2023. 2. 14. [백준][C++] 18808번: 스티커 붙이기 (264) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 이게 생각보다 쉬운것 같으면서 약간 구현이 빡신 문제이다. 애당초 생각을 많이 하기보다는, 문제 그대로 구현만 계속 하면 되는 문제이다. 배열의 크기도 최대 40*40 이라 brute force 방식으로 해결하면 된다 .. Algorithm/백준 2023. 2. 13. [백준][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] 2156번: 포도주 시식 (255) 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 우선 dp[i]에 대한 정의부터하고 시작해야겠다 생각했다. 우리의 dp[i]는 i번째 포도주 까지 마셨을때의 최대값 을 나타낸다. 그럼 연속된 3개가 오지 않으면서 i번 째 최대로 마시려면 어떠한 경우들이 있을까? 총 .. Algorithm/백준 2022. 10. 14. [백준][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. 이전 1 2 3 4 ··· 7 다음
