본문 바로가기

🔅코딩테스트 공부🔅213

[백준] 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.
[알고리즘] UNION FIND(서로소 집합 알고리즘) union find(=서로소 집합 알고리즘) union 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합침 find 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려줌 서로소 집합은 트리 구조를 이용해 표현하며, 부모 테이블을 항상 가지고 있어야 함 무방향 그래프에서 사이클 판별 가능 => 두 노드의 루트 노드가 같으면 cycle union find 코드 def find_parent(parent, x): #루트노드가 바로 부모노드가 됨 => 경로압축 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) return parent[x] def find_parent1(parent, x): #부모노드가 제대로 출력 => 경로압축 x if pa.. 2023. 2. 27.
[구간 합] 접두사 합 구간 합의 시간복잡도는 O(NM)이다. N,M의 데이터가 커지면 시간복잡도가 증가하게 되어 문제가 발생한다. 이럴 경우 구간 합 혹은 누적 합 계산을 빠르게 하기 위해 접두사 합을 이용하면 된다. 접두사 합은 리스트의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은 것이다. 아래를 코드를 실행시키면 sum value = [0, 10, 30, 60, 100, 150] 이 되며 sum_value[right] - sum_value[left-1] 을 해주면 빠르게 구할 수 있다. n = int(input()) data = [10,20,30,40,50] sum_value = 0 prefix_sum = [0] for i in data: sum_value += i prefix_sum.append(sum_value) l.. 2023. 2. 26.
[백준] 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.

티스토리툴바