알고리즘 부셔버렷/ProblemSolving43 [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. [BOJ] 백준 2225 합분해 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2225번 합분해 문제입니다. https://www.acmicpc.net/problem/2225 0부터 N까지의 정수 중 K개를 뽑아 더하고 그 결과가 N이 되는 경우의 수를 찾아야합니다. 덧셈의 순서가 다른 경우엔 다른 경우로 셉니다. 한 개의 수를 중복적으로 사용가능합니다. 해결 과정 0에서 3 까지 수에서 2개를 뽑아 합이 3인 경우의 수는 3을 하나 뽑았다는 가정하에 0에서 0 까지의 수 중 1개를 뽑아 합이 0이 되는 경우를 포함합니다. - 0 3 2를 하나 뽑았다는 가정하에는 0에서 1 까지의 수 중 1개를 뽑아 합이 1이 되는 경우를 포함합니다. - 1 2 1을 하나 뽑았다는 가정하에는 0에서 2 까지의 수 중 1개를 뽑아 합이 2.. 2023. 1. 5. [BOJ] 백준 2482 색상환 (문제 설명, 코드, C++) 문제 설명 해결 과정 코드 전문 문제 설명 본 문제는 백준의 2482번 색상환 문제입니다. 순환구조의 배열에서 각 원소들이 서로 이웃하지 않게끔, 총 n개의 원소 중에 k를 고를 수 있는 경우의 수를 찾는 문제입니다. https://www.acmicpc.net/problem/2482 해결 과정 핵심 아이디어는 첫 원소와 마지막 원소를 둘 다 고려해야할 때를 제외하면 순환적인 구조에서 벗어날 수 있다는 것 입니다. 그렇기에 시작 원소부터 끝 원소 전까지 반복을 통해 경우를 찾을 수 있습니다. i 번째 원소를 보고 j개 원소를 뽑아야한다면 i 번째 원소를 뽑을 경우 ) dp[i - 2][j - 1] (i를 뽑았으니 자신을 빼야하고, 자신 이전의 원소는 뽑을 수 없기에 i에 2를 뺍니다) i 번째 원소를 뽑지.. 2023. 1. 4. 이전 1 2 3 4 ··· 6 다음
