본문 바로가기

알고리즘/백준

 (263)
[백준] 2156번 : 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 마실수 있는 포도주 양의 최대값을 구하여라. 1. 포도주잔을 선택하면 모든 포도주를 마셔야하고, 원래위치에 다시 놓는다. 2. 연속으로 3개 놓여있는 포도주는 마실 수 없다. 테스트 케이스 분석 6 6 10 13 9 8 1 dp[1] = 6 dp[2] = 12 dp[3] = max(juice[1]+juice[3], dp[2]) dp[4] = max(dp[1]+juice[3]+juice[4] ,dp[..
[백준] 1010번 : 다리 놓기 https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 다이나믹 프로그래밍으로 문제를 해결하였고 점화식은 dp[n][m] = dp[n-1][m-1] + dp[n-1][m] 으로 도출하였다. 테스트 케이스 서쪽노드2, 동쪽노드 4 dp[2][4] = d[1][3] + dp[1][4]는 서쪽노드의 첫번째노드가 동쪽의 첫번째 노드와 연결되어있는 경우와 연결되지 않는 경우의 수의 합이다. 1. 서쪽첫번째 노드가 동쪽 첫번째 노드와 연결되어 있는경우 - dp[..
[백준] 9251번 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 두 수열이 주어졌을때, 모두의 부분 수열이 되는 수열중 가장 긴 것을 찾아서 길이를 구하는게 문제의 목표이다. 해당 문제는 부르트포스 방법으로 문제를 해결 할 수 있으나 문자열의 길이가 N, M 일때 시간복잡도가 O(NM)이 걸린다. 하지만 다이나믹 프로그래밍을 적용하여 풀면 O(NM)으로 문제를 해결 할 수 있다. 1) 브루트포스 방식으로 문제 접근 ..
[백준] 12865번 : 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net 테스트 케이스 예제 입력 1 4 7 6 13 4 8 3 6 5 12 예제 출력 1 14 물품의 개수 4, 배낭에 넣을 수 있는 가치의 합7 아이템 1) 무게:6, 가치:13 아이템 2) 무게:4, 가치:8 아이템 3) 무게:3, 가치:6 아이템 4) 무게:5, 가치:12 결과 -> 아이템2, 아이템3으로 가치가 14 결과가 출력된다. ..
[백준] 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 : 나누기 3과 나누기2와 빼기의 세개의 연산을 적절히 사용하여 1을 만드는데 횟수의 최소값을 구해야한다. 테스트 케이스 입력 10이고 출력이 3일때 10->9->3->1 로 3번 만에 만들 수 있다. dp 테이블을 입력의 개수만큼 생성한다. dp[10] = 0 # 연산X dp[9] = 1 # -1 dp[8] = 2 # -1 -1 dp[7] = 3 # -1 -1 -1 dp[6] = 4 # -1 -1 -1 dp[5] = 1 # 나누기 2 dp[4] = 2 # 나누기2, -1 dp[3] = 2 # -1, 나누..
[백준] 14500번 : 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 해당 문제는 'ㅜ' 모양을 제외한 나머지 모양은 깊이우선 탐색을 하였을때 depth가 4인 모양들 입니다. 따라서 저는 'ㅜ' 모양을 제외한 나머지는 depth가 4까지인 깊이우선탐색을 진행하였습니다. shape라는 배열에 ㅗ ㅜ ㅓ ㅏ 모양을 방문하도록 지정하였습니다. # ㅗ 모양 shape = [[[0,0], [-1,0], [-1,1], [-2,0]], [[0,0], [-1,0], [-1,-1..
[백준] 14503번 : 로봇청소기 안녕하세요. 이번주는 구현 문제를 풀어보려고 합니다. https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 저는 해당 문제를 각각의 기능을 함수화 하였고, 조건문으로 문제를 해결하였습니다. cleaned라는 배열을 통하여 빈방들의 청소 여부를 확인 합니다. 재귀 함수를 통하여 1번 위치로 돌아가는 방식으로 구현하였습니다. N, M = map(int, input().split()) direction =..
[백준] 1261번 : 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 데이크스트라(최단경로)와 너비우선탐색을 통하여 문제를 해결 하였습니다. dp테이블을 만들어 최단 경로를 누적하여 벽을 더많이 부수고 오는 탐색경로의 탐색을 멈추게 합니다. dp테이블의 N-1,M-1 위치의 값이 벽을 최소로 부수고 들어오는 결과 입니다. from collections import deque INF = int(10e9) M, N = map(int, input()..

티스토리툴바