본문 바로가기

728x90

알고리즘 문제 풀이146

[백준] 포도주 시식 https://www.acmicpc.net/problem/2156 문제에 나온 예시 입출력을 가지고 20분정도 고민해보니 규칙을 찾을 수 있었다.길이가 n인 일차원 배열 wines에는 와인의 양을 저장한다.길이가 n인 일차원 배열 dp에는 마실 수 있는 포도주의 최댓값을 저장한다.포도주 잔이 k개 있는 경우(k>=3) 포도주를 마실 수 있는 경우의 수는 아래 중 최댓값이다.k번째 포도주, k-1번째 포도주를 마시는 경우이 경우 최대값은 k번째 포도주 양 + k-1번째 포도주 양 + k-3번째까지 마신 포도주 최댓값즉, dp[k] = wines[k] + wines[k-1] + dp[k-3]k번째 포도주, k-2번째 포도주를 마시는 경우이 경우 최대값은 k번째 포도주 양 + k-2번째까지 마신 포도주 최대.. 2024. 11. 25.

[백준] 2xn 타일링 1, 2 https://www.acmicpc.net/problem/11726 https://www.acmicpc.net/problem/11727 세트처럼 생긴 두 문제를 풀어보았다.쉬운 DP 문제라고 해서 덤볐는데 생각보다 빨리 못풀었다. 두문제 다 내가 몇년전에 다른 언어로 풀었던기 기록이 있던데그땐 어떻게 풀었나 모르겠다 ㅎㅎ 우선 두 문제 모두, 문제 풀이 방법은 못풀고 고민했던 시간이 아까울 정도로 아주 간단했다. n=1일 때부터 경우의 수를 모두 따져보고 점화식을 세우기만 하면 된다. 2xn 타일링의 경우,모든 경우의 수를 따져보면 이렇다.n=1 : 1가지n=2 : 2가지n=3 : 3가지 (= 1 + 2)n=4 : 5가지 (= 2 + 3)n=5 : 8가지 (= 3 + 5)...피보나치와 동일한 규칙이다... 2024. 11. 13.

회사 노트북에 java 개발환경 세팅하기 패키지 관리자 Homebrew 설치 터미널에 입력/bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)" iterm2 설치brew install --cask iterm2 Oh My Zsh 설치sh -c "$(curl -fsSL https://raw.githubusercontent.com/ohmyzsh/ohmyzsh/master/tools/install.sh)" 꾸미는 건 나중에Java 11버전을 사용할 것이기 때문에 JDK11 다운받기https://adoptium.net/temurin/releases/제대로 된 경로에 JDK가 설치되었는지 확인(JDK 폴더가 `/Library/Java/.. 2024. 7. 22.

[백준]2564번: 경비원 https://www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 너무너무 헷갈리는 문제였따... 1. 각 상점 정보를 입력받을 때마다, 각 상점의 원점 기준 시계방향 거리와 반시계방향 거리를 계산해서 저장해놓는다. 2. 동근이의 위치를 입력받고, 1에서 입력해둔 정보들을 가지고 경우의 수를 나누어서 상점별로 최단거리를 계산한다. import java.io.BufferedReader; import java.io.IOException; import java.io.Inp.. 2023. 10. 27.

[백준]1459번: 걷기 https://www.acmicpc.net/problem/1459 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 처음에는 dp로 풀려고 했는데, 주어진 정수 범위가 너무 커서 힙 메모리가 부족해서 배열을 만들 수 없었다. 그래서 오랫동안 고민하다가 다른 분 풀이를 참고해서 풀었다. 간단하게 생각하면 되는 거였는데 떠오르지가 않아서 오래걸렸따 🐥 조심할 점 - x와 y가 매우 큰 수로 주어지면 연산 결과가 Integer 범위를 초과하기 때문에, 변수 자료형을 모두 long타입으로 설정해주었다. 🐥 풀이 목표.. 2023. 10. 23.

[백준]10211번: Maximum Subarray https://www.acmicpc.net/problem/10211 10211번: Maximum Subarray 크기 N인 정수형 배열 X가 있을 때, X의 부분 배열(X의 연속한 일부분) 중 각 원소의 합이 가장 큰 부분 배열을 찾는 Maximum subarray problem(최대 부분배열 문제)은 컴퓨터 과학에서 매우 잘 알려져 있 www.acmicpc.net 🐥 브루트포스로 푸는 방법도 있지만, 문제를 보자마자 DP가 떠올라서 DP 풀어보았다. - 지금까지의 부분배열의 최대 합을 저장할 dp배열을 만든다. - dp[0] = arr[0]으로 초기화한다. - dp[1] ~ dp[n]까지 채운다 - 매 인덱스마다 다음 두 가지 선택지가 생긴다. 1) 현재까지의 최대 합(dp[i-1])에 현재값(arr[.. 2023. 10. 18.

이전 1 2 3 4 ··· 25 다음

728x90

티스토리툴바