본문 바로가기

알고리즘 부셔버렷/ProblemSolving45

leetcode 1024 Stone Game II (DP, Java) 문제 링크문제 요약n([2,7,9,4,4]A, B 가 있으면 게임을 합니다.게임의 내용은 턴제 게임으로 자신의 턴일 때 마다 돌무더기를 가져갑니다.각 턴에 가져올 수 있는 돌무더기의 수는 (1 다음 턴이 될 때 m 은 max(m, x) 로 최신화됩니다.A, B 는 각자 자신의 턴에 최선의 수를 판단합니다.문제 풀이이 문제는 DP 문제이다. 어떻게 판단할 수 있을까요.. 처음 문제를 읽었을 땐 이게 어떤 유형의 문제인지 감이 안잡힐 것입니다. 이럴땐 먼저 brute force 로 접근하는 것입니다.private int rec(int i, int m, int n, int[] suffixSum) { if (i + 2 * m >= n) return suffixSum[i]; int result = 0;.. 2024. 9. 30.
[Algospot] SOLONG 안녕히, 물고기는 고마웠어요! (Python, Trie) [문제 링크](https://www.algospot.com/judge/problem/read/SOLONG)이 문제는 타이핑 시 **빈도가 잦은 문자를 추천**하는 기능을 구현하는 문제입니다.### 제약조건**입력**사전에 포함된 단어의 수 N (1 입력할 단어의 수 M (1 그 후 N 줄에는 한 줄에 하나의 문자열과 정수로 사전에 포함된 단어와 해당 단어의 출현 빈도가 **사전 순서와 무관**하게 주어집니다. **같은 단어가 두번 이상 주어지는 일은 없으며**, 출현 빈도는 1 과 10만 사이의 정수입니다. 그 다음 줄에 M개의 단어로 입력할 문자열이 주어집니다. **모든 단어는 알파벳 대문자이며, 길이는 최대 10입니다.**### 핵심내용단어의 접두사부터 시작해 접미사를 찾아내는데는 `Trie` 가 적.. 2024. 9. 25.
[BOJ] 10037 Decorating the Pastures (문제풀이, PYTHON) 문제 링크 10037번: Decorating the Pastures Farmer John has N (1 2024. 3. 4.
Python3, PyPy3 Python3은 인터프리터(실행전 바이트코드로 컴파일되지만), PyPy3에선 JIT이 도입되었다합니다. PyPy3가 메모리를 더 소모할 수 있지만, Python3에서 시간초과가 나던 문제가 PyPy3에선 해결될 수 있다. 메모리 초과의 우려도 있으니 문제 조건을 잘 살펴보면서 고르면 좋을 것 같다. 2023. 9. 12.
[BOJ 6574] 백준 새로운 과일 파이썬 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 6574번 문제 새로운 과일이다. https://www.acmicpc.net/problem/6574 LCS를 잘 모른다면 감조차 잡기 힘들 수 있는 문제이다. LCS에 대해선 이 분의 글이 참 좋았다. (글 잘 적는 사람 부러워요) https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subseq.. 2023. 7. 19.
[BOJ] 4811 알약 C++ 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 4811번 알약 문제입니다. 약통에는 n개의 알약이 있으며 완전한 알약 하나를 반으로 쪼개서 먹어야합니다. 완전한 약을 골랐을 경우 반쪽으로 쪼개서 반쪽을 먹고 남은 반쪽은 다시 약통에 넣습니다. 이 때 약통에 있는 약을 매일 반쪽 씩 복용할 때 고른 알약의 경우의 수 입니다. 해결 과정 약통에 완전한 알약만 있을 경우 약통[n(완전한 알약 수) - 1][(반쪽 알약 수) 0 + 1] .반쪽 알약 수의 0은 완전한 알약만 있기에 0이고 뒤의 +1은 온전한 알약을 선택한 뒤 반쪽은 먹고 반쪽은 약통에 넣었기 때문 약통에 반쪽 알약만 있을 경우 1 약통에 완전한 알약, 반쪽 알약 둘 다 있을 경우 완전한 알약을 고른 경우 약통[n(완전한 알약 수).. 2023. 4. 8.
[BOJ] 6568번 귀도 반 로썸은 크리스마스날 심심하다고 파이썬을 만들었다. 문제풀이 c++ 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 6568번 문제 입니다. https://www.acmicpc.net/problem/6568 구현문제 파일을 다 읽을 때까지(EOF) 입력을 받습니다. 32Byte의 메모리와 8bit 가산기, 5bit의 프로그램 카운터가 존재합니다. 명령어의 크기는 1Byte입니다. 해결 과정 명령어는 1Byte이고 메모리는 32Byte이므로 최대 32개의 명령어를 가질 수 있습니다. 구현 문제인 만큼 고려할 부분이 조금 있습니다. 입력이 이진수배열의 문자열인 만큼 이를 파싱해야합니다. 그리고 명령어의 상위 3bit와 그외 하위 5bit를 나눠야합니다. 이는 상위 3bit를 먼저 구하기 위해 5bit 2^5을 나눈 몫이 상위 3bit이고 나눈 뒤 나머지는 하위 .. 2023. 4. 8.
[BOJ] 백준 2565 전깃줄 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2565번 전깃줄 문제입니다. https://www.acmicpc.net/problem/2565 해결 과정 예제 ) 왼쪽 전봇대 기준 오름차순으로 정렬 LIS 문제 익숙하다면 가장 긴 증가하는 부분순열을 구하면 이게 바로 전깃줄에 의해 방해받지 않는 전깃줄들의 집합이기에 전체 전깃줄에서 빼주면 전깃줄들을 가로질러 방해하는 전깃줄들의 수를 구할 수 있습니다. 코드 전문 #include #include #include using namespace std; using pii = pair; int n; vector line_arr; int dp[502]; bool comp(pii a, pii b) { return a.first < b.first; } .. 2023. 1. 5.

티스토리툴바