본문 바로가기

💪🏻코딩테스트

(7)

[구현, 시뮬레이션] 20061 : 모노미노도미노 2 python 📄 20061 : 모노미노도미노 2 📄 www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 🤔 문제 풀이 🤔 "구현"과 "시뮬레이션"을 푸는 방법은 자신감인 것 같다. 문제 조건이 굉장히 복잡하고 구현하자니 귀찮은 부분들이 많이 보이기 때문에 문제 풀이를 하기 싫어지게 된다. 하지만 이런 구현 문제를 많이 풀다보면 구현에 대해 두려움이 사라져서 여러가지 시도를 쉽게 해볼 수 있는 것 같다. 이 문제에서 어려웠던 점은 fill_block()함수에서는 '..

[LCS] Longest Common Subsequence (최장 공통 부분 문자열) LCS 알고리즘이란..? 한국말로 번역해보면 "최장 공통 부분 문자열"이다. 여기서 Subsequence와 Substring의 차이에 대해 이해해야만 한다. 둘의 차이는 연속성이다. 연속된 부분 문자열을 만족하는 것은 Substring이고 연속되지 않은 부분 문자열이라면 Subsequence이다. "ACAYKP" "CAPCAK" 가장 긴 Substring은 CA이고 가장 긴 Subsequence는 ACAK이다. LCS 를 구하는 방법 (다이나믹 프로그래밍) 먼저 dp배열을 만들어준다. 0열 0행을 추가적으로 만들어준다. (편의를 위해) 배열1과 배열2를 비교하는데 배열2의 문자하나를 잡아서 배열1의 모든 문자와 비교해나간다. 문자를 비교해서 값이 같으면 왼쪽 위(현재 문자를 포함하지 않은 최댓값)에 +1..

[DP] 백준 11058 크리보드 python 📄 백준 11058 크리보드 📄 www.acmicpc.net/problem/11058 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 🤔 문제 풀이 🤔 버튼 1을 누르는 경우 dp[n] = dp[n - 1] + 1 버튼 2, 3을 누르는 경우는 크기가 증가하지 않으므로 최댓값이 될 수 없다. 버튼 4를 누르는 경우는 ctrl + A, ctrl + C인 2, 3번 버튼이 선행되어..

[BFS, 구현] 백준 16236 아기 상어 python 📄 백준 16236 아기 상어 python 📄 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 🤔 문제 풀이 🤔 첫번째 시도에서 정확히 구현하지 못했고 인터넷의 블로그를 참고하여 코드를 완성하였다. 내가 이 문제에서 놓친 포인트는 처음 아기상어의 위치를 저장한 후 맵에서 아기상어 위치를 0으로 바꿔주지 않았다. (크기가 9인 상어로 인식하게 됨) BFS가 사용하는 queue의 속성을 이용해 먹을 수 있는 상어를 찾은 횟수까지만 탐색을 수행하도록 한다...

[DP] 백준 1699 제곱수의 합 python 📄 백준 1699 제곱수의 합 📄 www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 🤔 문제 풀이 🤔 숫자가 주어질 때 제곱수의 합으로 나타낼 수 있는 최소 항의 갯수를 구하는 문제이다. 먼저 모든 숫자는 1의 제곱으로 만들 수 있으며 그 때 항의 갯수는 숫자 n일 때 n개 이다. 이제 1부터 n까지 숫자를 증가시켜가면서 각각의 숫자에 대해 최소항의 갯수를 구해보자. 1일 때는 1개이다. 2일 때는 1^2, 1^2 2개이..

[DP] 백준 2133 타일채우기 python 📄 백준 2133 타일채우기 📄 www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 🤔 문제 풀이 🤔 n = 2일 때, 2 x 1, 1 x 2타일로 3 x 2 타일을 만들 수 있는 갯수를 세어보면 3가지 경우의 수가 나온다. n = 3일 때, 홀수일때는 어떠한 타일도 만들 수 없다. n = 4일 때는 2가지의 새로운 경우의 수를 찾을 수 있다. n = 6일 때 또한 2가지의 새로운 경우의 수를 찾을 수 있다. 이렇게 짝수로 증가하는 n에서는 모두 2가지의 새로운 경우의 수를 찾을 수 있다. dp[0] = 1, 아무것도 없는 경우의 수 하나 dp[2] = 3, 3가지 경우의..

Velog 정리 모음 velog.io/@pyh8618/series pyh8618 (yunan) / 시리즈- velog 1개의 포스트·마지막 업데이트 2020년 9월 6일 velog.io

이전 1 다음

티스토리툴바