본문 바로가기

🔅코딩테스트 공부🔅/❗백준138

[백준] 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.
[백준] 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.
[백준] 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.
[백준] 1976번 여행 가자(python) https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 단계별로 풀어보기 중 union find로 분류되어 있어서 바로 풀었다. 무방향 그래프에서 cycle을 찾기 위해서는 union find를 이용하면 쉽다는 것을 잊지말자 3. 내가 작성한 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n = int(input().rstri.. 2023. 2. 27.
[백준] 1717번 집합의 표현(python) https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 1. 난이도 골드5 (🥇) 2. 문제 해결 방법 union find 알고리즘을 이용해서 문제를 해결하면 된다. n과 m의 값이 크기 때문에 경로압축을 통해 시간복잡도를 감소시켰다. 잘 푼 것 같은데 자꾸 런타임 에러가 발생해서 왜일까 한참 고민했는데 setrecursionlimt를 설정해주지 않았었고, 이를 수정했더니 잘 출력되었다. 10만으로 설정하면 잘 통.. 2023. 2. 27.
[백준] 1929번 소수 구하기(python) https://www.acmicpc.net/problem/1929 1. 난이도 실버3 (🥈) 2. 문제 해결 방법 1. 에라토스테네스의 체를 이용해 소수/합성수를 구분한다. 2. num의 value가 True인 수 중 m이상, n이하일 때만 출력하면 된다. 혹시 에라토스테네스를 잘 썼는데 자꾸만 틀렸다고 뜬다면, m이 1인 경우를 생각했는지 고려하면 좋을 것 같다. (이거 놓쳐서 m부터 n+1 까지 반복문 돌렸다가 틀렸었음,,😭) 3. 내가 작성한 코드 m,n = map(int, input().split()) #m이상 n이하 total = [True] * (n+1) for i in range(2, n+1): if total[i] == True: for j in range(2*i, n+1, i): tota.. 2023. 2. 26.
[백준] 2960번 에라토스테네스의 체(python) https://www.acmicpc.net/problem/2960 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 1. 난이도 실버4 (🥈) 2. 문제 해결 방법 에라토스테네스 체 복습할 겸 풀어봤다. 이 문제에선 소수도 지우는 수로 count 한다는 점을 주의해서 해결하면 된다. n,k = map(int, input().split()) num = [True] * (n+1) x = 0 for i in range(2,n+1): if num[i] == True: x += 1 if x == k: print(i) break for j in range(2*i, n+1, i): if num[j] != Fal.. 2023. 2. 26.
[백준] 14938번 서강그라운드(python) https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 플로이드 워셜 알고리즘과 다익스트라 모두 사용할 수 있다. 플로이드의 시간복잡도가 더 크지만, n의 범위가 1부터 100까지라 문제 없을 것 같다고 판단해 플로이드로 풀었다. 1. 플로이드 알고리즘을 이용해 모든 정점에서 다른 정점으로 가는 최단 거리를 구한다. 2. 수색범위보다 작거나 같을 때, 다른 정점으로 이동하며 아이템의 개수를 더해준다. (이걸 .. 2023. 2. 26.

티스토리툴바