방구석 개발자의 실험실

https://www.acmicpc.net/problem/2193      문제0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 N자리 이친수의 개수를 ..

[백준] 11722 가장 긴 감소하는 부분 수열 자바 풀이 DP  본 문제에선 숫자가 감소하지만 반대로 생각하면 증가이기 때문에 LIS문제입니다최장 증가 부분수열 (LIS, Longest Increasing Subsequence).  저번에 풀었던 LCS도 참고하시면 좋을 것 같습니다2024.08.22 - [알고리즘 단련장/백준] - [백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DP [백준] 9251 LCS 최장 공통 부분수열 자바 풀이 DPhttps://www.acmicpc.net/problem/9251  왜 그때 당시에는 생각이 나지 않았을까. 싶은DP의 기본중의 기본 문제.안해보면 낯설지만, 한번 만나면 익숙한 녀석. 시작해보자.  스펙은 이렇다.       문snapcode.tistor..

https://www.acmicpc.net/problem/2579     계단 오르기 성공 문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 ..

[소프티어] 통근버스 출발 순서 검증하기 자바 풀이 dp DP (HSAT 4회 정기 코딩 인증평가 기출)  https://softeer.ai/practice/6257 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai  언어별 시간/메모리언어시간메모리JavaScript2초1024MBC1초1024MBC++1초1024MBJava2초1024MBPython2초1024MB현대자동차그룹 연구소에서는 임직원들의 편의를 위해 출퇴근 통근 버스를 제공하고 있다.퇴근 시간이 되면 연구소 주차장에는 수 많은 버스들이 일렬로 주차되어 있다. 퇴근 버스는 번호순서 대로 출발해야 하는데, 주차장은 폭이 좁아 앞의 버스가 모두 나가야 뒤의 버스가 나갈 수 있는 구조로 되어 있다. 버스를 순서에 맞게 출발시키기 위..

DP란?- 동적 프로그래밍(DP)은 알고리즘 문제 해결에 매우 중요한 기법 중 하나     추천 DP 문제들 1003번: 피보나치 함수문제 설명: 피보나치 함수의 호출 횟수를 계산하는 문제로, 기본적인 DP를 이해하고 연습하기 좋음 1463번: 1로 만들기문제 설명: 주어진 정수를 1로 만드는 최소 연산 횟수를 찾는 문제로, DP를 통해 최적의 방법을 찾는 연습을 할 수 있음 2098번: 외판원 순회문제 설명: 외판원 문제로, 모든 도시를 방문하여 처음 도시에 돌아오는 최단 경로를 찾는 문제임. 비트마스크 DP를 활용하는 문제로 도전해볼 만함.11053번: 가장 긴 증가하는 부분 수열문제 설명: 주어진 수열에서 가장 긴 증가하는 부분 수열의 길이를 찾는 문제임. DP를 활용하여 최적의 부분 수열을 찾는 ..