DonHurry

📖 문제 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 🔎 풀이 투 포인터와 재귀를 이용하여 해결하였습니다. 문제는 단순히 회문만 판별하는 것이 아니라, 한 문자를 삭제했을 때 회문이 되는 경우도 판별해야 합니다. 투 포인터로 탐색하다 두 문자가 다른 경우, 왼쪽 포인터만 혹은 오른쪽 포인터만 옮기는 경우의 수 2가지가 생깁니다. 2가지 경우의 수 중, 더 좋은 결과값을 최종 결과로 반환하면 됩니다. 💻 코드 import sys input=sys.stdin.readline def palindrome(string, i, j, chance):..

📖 문제 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 🔎 풀이 세그먼트 트리를 활용하는 대표적인 문제입니다. 세그먼트를 처음 접하는 분들은 아래 블로그에 개념과 코드 설명이 잘되어 있으니 참고 부탁드립니다. [자료구조] 세그먼트 트리 (Segment Tree) 세그먼트 트리(Segment Tree)란? velog.io 위 블로그에서 개념과 코드를 보고 오셨다면, 해당 문제는 어렵지 않게 풀 수 있습니다. 세그먼트 트리를 만들어주는 함수, 세그먼트 ..

📖 문제 1305번: 광고 세준이는 길 한가운데에서 전광판을 쳐다보고 있었다. 전광판에는 광고가 흘러나오고 있었다. 한참을 전광판을 쳐다본 세준이는 이 광고가 의미하는 것이 무엇인지 궁금해지기 시작했다. 전광 www.acmicpc.net 🔎 풀이 해당 문제를 풀기 위해서는 KMP 알고리즘의 원리에 대해 이해하고 있어야 합니다. 모르시거나 기억이 나지 않는 분들은 아래 블로그 링크 참고하시면 됩니다. https://bowbowbow.tistory.com/6 KMP 알고리즘에서는 접두사(prefix)와 접미사(suffix) 개념이 매우 중요합니다. 이 문제에서 주어진, 전광판에서 가능한 광고의 길이 중 가장 짧은 것을 찾는 방법도 접두사 접미사와 관련이 있습니다. 예를 들어 전광판에서 BAAABA가 보였다면..

📖 문제 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 🔎 풀이 DP 문제로, 점화식을 찾아야 합니다. 우선 홀수인 경우 타일을 채우기가 불가능하므로 경우의 수를 0으로 두고, N이 2의 배수일 때만 생각하면 됩니다. N = 2 일 때는 아래와 같이 3가지 경우로 나눌 수 있습니다. 따라서 dp[2] = 3 이 됩니다. 다음으로 N = 4 일 때에는 아래와 같이 3가지 경우로 생각해볼 수 있습니다. 앞서 dp[2]가 3이었으므로, 경우의 수는 3 * 3 + 2 = 11 가지가 됩니다. N = 6 일 때에는 먼저 dp[N-2] * dp[2] 를 생각할 수 있습니다. 여기에 위에서 보았던 특수한 경우 2가지를 더 생각해야..

📖 문제 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 🔎 풀이 백준 삼성 SW 역량 테스트 기출 문제집에 있는 구현 문제입니다. 풀이는 아래와 같은 과정으로 진행하였습니다. 주어진 K개의 회전 방법을, 순서대로 (번호와 방향을) 꺼낸다. 리스트(deque)를 만들어 번호와 방향을 넣는다. 리스트에서 번호와 방향을 하나씩 뽑아 아래의 과정을 반복한다. 해당 톱니바퀴를 기준으로 좌우 톱니바퀴가 존재하는지, 존재한다면 맞닿아 있는 부분이 같은 극인지 확인한다. 현재 바퀴를 회전시키고, 만약 다른 극을 가지고..

📖 문제 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 🔎 풀이 백준 삼성 SW 역량 테스트 기출 문제집에 있는 문제로, 전형적인 구현 문제입니다. 가장 먼저 찾아야할 것은 주사위가 동서남북 각각으로 이동했을 때, 기존 위치와 어떻게 달라지는 가입니다. 아래 표는 문제에서 주어진 주사위 전개도를 각 방향으로 이동했을 때의 변화를 나타낸 표입니다. 방향 / 인덱스 1 2 3 4 5 6 1 (동쪽) 3 2 6 1 5 4 2 (서쪽) 4 2 1 6 ..

📖 문제 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 🔎 풀이 배낭 문제 풀이법으로 풀 수 있는 DP 문제입니다. 시간 복잡도는 O(M + N)으로 2차원 테이블을 만들어 해결할 수 있습니다. 각 동전의 종류 N가지 만큼 M + 1개의 원소를 가지고 있는 배열을 만들고, 동전 종류 별로 테이블을 채워나가면 됩니다. 아래 코드에서는 1차원 배열만으로도 해결할 수 있습니다. 핵심은 현재 금액(M)에서 동전의 금액을 빼 준 값을 인덱스로 하여, 해당 인덱스의 원소를 더해주는 것입니다. 예를 들어..

📖 문제 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 🔎 풀이 deque를 이용하면 풀 수 있는 문제입니다. deque는 이중연결리스트로 구현되어 있기 때문에 맨 앞이나 맨 뒤의 원소를 제거하는데 O(1)의 시간이 걸립니다. 뱀이 사과를 먹은 경우 앞에 새로운 좌표를 추가하고, 사과를 먹지 못한 경우 뒤에서 좌표를 제거해주면 됩니다. 나머지 부분은 문제의 조건에 따라 구현하면 됩니다. 주의할 점은 사과의 위치가 (1, 1) 부터 시작한다는 점입니다. 문제에서 "맨 위 맨 좌측(1행 1열)에는 사과가 없다." 라고..