본문 바로가기

전체 글229

[백준] 2670번 연속부분최대곱(python)(dp) https://www.acmicpc.net/problem/2670 2670번: 연속부분최대곱 첫째 줄은 나열된 양의 실수들의 개수 N이 주어지고, 그 다음 줄부터 N개의 수가 한 줄에 하나씩 들어 있다. N은 10,000 이하의 자연수이다. 실수는 소수점 첫째자리까지 주어지며, 0.0보다 크거나 www.acmicpc.net 1. 난이도 실버4 (🥈) 2. 문제 해결 방법 DP를 이용해서 문제를 해결했다. (현재의 값)과 (전까지의 최대곱 * 현재의 값) 중 더 큰 값을 dp에 넣으면 된다. round(num, 3) => 소수점 셋째자리까지 출력이지만 1.0 이었을 경우 1.0 으로 출력되어 오답처리된다. 따라서 ('%.3f' %max(dp))로 해야한다. 3. 내가 작성한 코드 n = int(input(.. 2023. 3. 1.
[백준] 2407번 조합(python)(dp) https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 1. 난이도 실버3 (🥈) 2. 내가 작성한 코드 dp 공부중이라 dp로 해결하고 싶었는데, 파스칼의 삼각형 공식을 제대로 몰라서 지저분하게 풀었다. 머쓱,, n,m = map(int, input().split()) dp = [0] * (n+1) dp[1] = 1 dp[n] = n for i in range(2,m+1): if n-i m인 경우 dp[i] = dp[n-i] #nCn-m값 넣어줌 else: #nCm 직접 계산해줌 r = n d = i for j in range(1,i): r.. 2023. 3. 1.
[백준] 11055번 가장 큰 증가 부분 수열(python)(dp) https://www.acmicpc.net/problem/11055 1. 난이도 실버2 (🥈) 2. 문제 해결 방법 가장 긴 증가하는 부분 수열과 비슷한 문제다. 증가하고 있을 경우 max(본인이 가지고 있는 누적합, 그 전 원소의 누적합 + 본인의 값)를 출력하면 되고, 감소하고 있을 경우 max(본인이 가지고 있는 누적합, 본인의 값)을 출력하면 된다. 감소하고 있을 경우를 고려하지 않고 제출해서 2트만에 맞았다. 3. 내가 작성한 코드 n = int(input()) num = list(map(int, input().split())) dp = [0] * n dp[0] = num[0] for i in range(n): for j in range(i): if num[i] > num[j]: dp[i] = .. 2023. 3. 1.
[백준] 1912번 연속합(python)(dp) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 n = int(input()) dp = [0] * n num = list(map(int, input().split())) dp[0] = num[0] for i in range(1,n): if dp[i-1] + num[i] > num[i]: dp[i] = dp[i-1] + num[i] else: dp[i] = num[i] print(max(dp)) dp에 누적.. 2023. 3. 1.
[백준] 11053번 가장 긴 증가하는 부분 수열(python)(dp) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 1. 내가 작성한 코드 n = int(input()) A = list(map(int,input().split())) dp = [1] * n #부분 수열의 최소 개수는 1이기 때문에 모두 1 for i in range(1,n): #1번부터 n번까지 확인 for j in range(i): #본인보다 앞에 있는 수 확인 if.. 2023. 3. 1.
❗문제 메모 - 삼성 문제 ❗ 백준 삼성 A형 기출 문제 17070번 파이프 옮기기1 (골드5) - X 메모) 복습필요, DP로 다시 풀어보기 파이프의 현재 상태가 가로/세로/대각선인 경우 이동했을 때, (n,n)에 도착할 수 있는 횟수를 출력하는 문제다. 당연히 BFS라고 생각하고 문제를 해결했는데 시간초과가 발생했고, 이후 DFS + 중복연산제거를 통해 해결할 수 있었다. 2023. 2. 28.
[백준] 17070번 파이프 옮기기 1(python) https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 1. 난이도 골드5 (🥇) 이제 삼성문제 풀 수 있지 않을까? 생각하고 시도한 오만방자한 과거의 나 눈감아 테스트케이스를 모두 맞아서 신나게 제출했지만 70% 에서 계속 시간초과가 떴다. 결국 구글로 도망갔고 다른 사람들의 코드와 비교해보니 시간초과가 뜰 만 했다는 생각,, 반성하게 되는 하루 (우울해져서 SWEA 가입하고 왔음) 2. 내가 작성한 코드 (70%에서 시간초.. 2023. 2. 28.
[백준] 2573번 빙산(python) https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 과정 주의해야 할 점 1. 전체 빙산의 녹는 양을 한 번에 빼줘야 한다. => 하나 빼주고, 다시 다른 거 빼주고,, 이런식으로 각각 반복하면 바다가 되어버렸을 경우 문제가 발생한다. 2. 처음부터 빙산이 없을 수도 있다. 코드 분석 1. 행과 열, 빙산의 정보를 입력받는다. from collections import deque n,m = map(i.. 2023. 2. 27.
[백준] 13549번 숨바꼭질3(python) https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 문제 해결 방법 다익스트라를 이용해서 순간이동과 걸어서 갈 때의 가중치를 다르게 두었다. 내가 놓쳤던 부분은 1. 수빈이가 동생보다 뒤에 있을 수 있다는 점 2. max 값이 100000 까지라는 점이다. => 최댓값을 동생의 위치 * 2로 했다가 틀렸다. 0-1 bfs 기 때문에 deque를 이용해서 풀 수 있다고 하는데 아직 그.. 2023. 2. 27.

티스토리툴바