Algorithm/백준 문제 풀이

    [2578번] 빙고
    Algorithm/백준 문제 풀이

    [2578번] 빙고

    백준 2578번: 빙고 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다. www.acmicpc.net 이 문제는 조금 생각해야 할 게 필요합니다. 제가 틀렸던 과정을 최대한 비슷하게 밟아보겠습니다. 처음에는 단순하게 5X5 크기의 빙고판이니 '브루트 포스' 기법으로 풀 수 있겠다는 확신이 들었습니다. 그러니 대각선과 가로, 세로줄을 검사하여 빙고인지 검사할 함수와 빙고의 개수를 세어주기만 하면 된다고 생각했습니다..

    [2156번] 포도주 시식
    Algorithm/백준 문제 풀이

    [2156번] 포도주 시식

    백준 2156번: 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net [해당 포스팅]과 완전히 같습니다. 달라 보이신다고요? 아닙니다. 잘 살펴봅시다. 위의 포스팅에서 소개된 문제는 "계단 오르기" 문제인데요. 두 문제의 조건 차이는 단 ..

    [2579번] 계단 오르기
    Algorithm/백준 문제 풀이

    [2579번] 계단 오르기

    백준 2579번: 계단 오르기 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 www.acmicpc.net 계단을 오르는데 조건을 만족시키며 지나가는 계단 값들의 합 중 최댓값을 구하는 문제입니다. DP를 이용하여 풀어야하는 느낌이 듭니다. 그래서 아이디어를 생각해봐야 합니다. 현재 밟고 있는 계..

    [5582번] 공통 부분 문자열
    Algorithm/백준 문제 풀이

    [5582번] 공통 부분 문자열

    백준 5582번: 공통 부분 문자열 5582번: 공통 부분 문자열 문제 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들어, 문자열 ABRACADABRA의 부분 문자열은 ABRA, RAC, D, ACADABRA, ABRACADABRA, 빈 문자열 등이다. 하지만, ABRC, RAA, BA, K는 부분 문자열이 아니다. 두 문자열 ABRACADABRA와 ECADADABRBCR www.acmicpc.net LCS 알고리즘에 대해 아시나요? 혹시 모르신다면 [여기]를 참고하시고 다시 와 주세요. 아무튼 이 문제는 LCS 문제와는 약간의 차이가 있습니다. 그때는 각..

    [9252번] LCS 2
    Algorithm/백준 문제 풀이

    [9252번] LCS 2

    백준 9252번: LCS 2 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net [이전 포스팅] 글의 다음 단계라고 할 수 있습니다. 방법은 간단합니다. 이전에는 길이만을 출력하게 했다면, 이번에는 역추적을 통한 검사를 추가로 포함시켜주면 됩니다. 역추적은 만들어진 DP table에서 길이 값이 같거나 하나 줄어드는 방향으로 움직이며 table 기준으로 아래에서 출발하여 위쪽으로 움직일 때마다 그 문자를 저장해주면 됩니다. 그 후에는 출력만 해주면 되겠죠. 기본적인..

    [9251번] LCS
    Algorithm/백준 문제 풀이

    [9251번] LCS

    백준 9251번: LCS 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net "LCS(Longest Common Subsequence, 최장 공통부분 수열) 문제"입니다. DP(Dynamic Programming)으로 풀 수 있는 유명한 문제 중 하나입니다. 사실 이 문제에 대한 알고리즘 설명을 드리고 싶지만 저보다 잘 설명하시고 자료도 많으신 블로거 분들이 많이 계셔서 그중 제가 참고했던 [블로그 하나]를 소개하겠습니다. ㅎㅎ 이 문제에서 얻어갈 것은 LCS 알고리즘..

    [5532번] 방학 숙제
    Algorithm/백준 문제 풀이

    [5532번] 방학 숙제

    백준 5532번: 방학 숙제 5532번: 방학 숙제 문제 상근이는 초등학교에 다닐 때, 방학 숙제를 남들보다 먼저 미리 하고 남은 기간을 놀았다. 방학 숙제는 수학과 국어 문제 풀기이다. 방학은 총 L일이다. 수학은 총 B페이지, 국어는 총 A페이지를 풀어야 한다. 상근이는 하루에 국어를 최대 C페이지, 수학을 최대 D페이지 풀 수 있다. 상근이가 겨울 방학동안 숙제를 하지 않고 놀 수 있는 최대 날의 수를 구하는 프로그램을 작성하시오. 입력 한 줄에 하나씩 총 다섯 줄에 걸쳐 L, A, B, C, D가 www.acmicpc.net '나누기 + 나머지'를 다룰 수 있는지 묻는 문제입니다. 그다지 어렵지 않으니 딱히 설명을 드릴 것이 없군요.. 아쉽네요. [소스 보기]

    [2231번] 분해합
    Algorithm/백준 문제 풀이

    [2231번] 분해합

    백준 2231번: 분해합 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다. 자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그 www.acmicpc.net 분해합: 어떤 자연수 $N$이 있을 때, $N$과 $N$이 이루는 각 자리수의 합 자연수 하나가 주어졌을 때, 다른 자연수의 분해합을 통해 그 자연수가 만들어진다면 만들어지는 다른..

    [4195번] 친구 네트워크
    Algorithm/백준 문제 풀이

    [4195번] 친구 네트워크

    백준 4195번: 친구 네트워크 4195번: 친구 네트워크 문제 민혁이는 소셜 네트워크 사이트에서 친구를 만드는 것을 좋아하는 친구이다. 우표를 모으는 취미가 있듯이, 민혁이는 소셜 네트워크 사이트에서 친구를 모으는 것이 취미이다. 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하시오. 친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말한다. 입력 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계 www.acmicpc.net 이전 포스팅에서 다뤘던 '유니온 파인드'에 대한 변형 문제입니다. 이번에는 각 유니온들의 root 노드들이 기존 배열에서 정수로 된 index를 이용하는 것이 아니라..

티스토리툴바