본문 바로가기

분류 전체보기321

백준 2133 c++ "타일 채우기" -PlusUltraCode- https://www.acmicpc.net/problem/2133 [필자 사고]동적프로그래밍의 대표저인 타일 채우기 문제이다.다만 이 문제만의 특별한 점은 세로의 크기가 3이라는 점이다.이러한 특성으로 인해 N의 값이 홀수이면 만들 수 있는 경우의 수가 없다.또한 도중 보이는 특이케이스 경우의 수도 있다.기존 방식에서 특이케이스 경우의 수도 더해줘야 해당 문제를 풀 수 있다.처음 문제를 풀 때는 특이케이스에 대해 생각도 못했었는데 사고를 확장시켜 준 문제이다.[코드 해설]2. 입력 처리 (Input 함수)사용자로부터 정수 N을 입력받고, 이를 저장할 벡터 dp를 동적으로 할당한다. 벡터의 크기는 N+1로 설정하여, 인덱스 N까지 접근할 수 있도록 한다.3. 동적 프로그래밍을 이용한 문제 해결 (Game_.. 2025. 3. 11.
백준 14002 c++ "가장 긴 증가하는 부분 수열 4" -PlusUltraCode- https://www.acmicpc.net/problem/14002 [필자 사고]기본적인 LIS 문제에 + 증가하는 숫자에 대한 기록까지 더해져 있는 문제이다.필자는 LIS문제는 익숙하게 풀었지만증가하는 숫자들의 기록에서 애를 먹었다.곰곰히 생각해보니 백트래킹 사고를 기반으로 문제를 풀면 풀 수 있었다. 총 LIS길이를 구하고 뒤에서 부터 dp값을 검사하여 같은 길이가 있다 하면 해당 값을 넣는 형식으로 말이다.발견한다면 현재 길이를 -1 로 해서 갱신해주고 위와 같은 과정을 반복해주면 증가하는 숫자들의 기록을 구할 수 있다. 아래는 자세한 코드 해설이다.[코드 해설]입력 처리 (Input 함수)Input() 함수는 수열의 길이 N을 입력받고, 이를 저장할 벡터 arr와 최장 증가 부분 수열(LIS, L.. 2025. 3. 10.
백준 11054 c++ "가장 긴 바이토닉 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11054 [필자 사고]동적 프로그래밍 문제이다.언뜻 봤을 때는 LIS문제 같아 보이지만LIS문제를 응용한 문제이다.dp배열을 2개 만들어 시작부분과 끝부분에서 각 시작하여 각 인덱스마다 2개의 배열을 더한 값-1 이 가장 큰값을 출력해야 된다. 필자는 해당 LIS를 구할 때 초기값을 1 로 설정을 안해서 출력값이 계속 1보다 작은 문제가 발생했었다.이 부분 주의해야 겠다. 개인적으로 해당 문제에서 LIS지식을 2개를 이용하여 처음 부분과 끝부분으로 알고리즘 적용한게 인상적이였다.[코드 해설]입력 처리 (Input 함수)Input() 함수는 배열의 크기 N을 입력받고, 이를 기반으로 배열 arr, dp, rDp를 초기화한다.arr 배열은 입력받은 .. 2025. 3. 10.
백준 14226 c++ "이모티콘" -PlusUltraCode- https://www.acmicpc.net/problem/14226[필자 사고]BFS탐색 문제입니다.특히 너비우선 탐색이라 최소값을 찾는 대표적인 문제라고 생각이 드네요이 문제에서 느낀 매력적이 포인트는 moniter 와 copyBoard를 이용하여 visted를 관리하는 방식이였습니다언뜻보면 visited를 1차원으로 해결할 거라 생각하지만 실제로 2차원배열을 설정하여 2가지 값에 해당하게 방문 배열을 설정해야 문제를 해결할 수 있습니다. 또한 범위 관련해서 주의를 해야 되는데 2000을 마지노선으로 정한 이유는 해당 S값이 1000으로 되어있어 1000의 2배는 2천이라 해당 숫자로 범위를 정했습니다. 아래는 자세한 소스코드 해설입니다.[코드 해설] 구조체 정의 및 변수 선언struct img는 현재.. 2025. 3. 9.

티스토리툴바