본문 바로가기

전체 글229

[백준] 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.
[백준] 14938번 서강그라운드(python) https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 문제 해결 방법 플로이드 워셜 알고리즘과 다익스트라 모두 사용할 수 있다. 플로이드의 시간복잡도가 더 크지만, n의 범위가 1부터 100까지라 문제 없을 것 같다고 판단해 플로이드로 풀었다. 1. 플로이드 알고리즘을 이용해 모든 정점에서 다른 정점으로 가는 최단 거리를 구한다. 2. 수색범위보다 작거나 같을 때, 다른 정점으로 이동하며 아이템의 개수를 더해준다. (이걸 .. 2023. 2. 26.
[백준] 2468번 안전 영역(python) https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. 난이도 실버1 (🥈) 2. 문제 해결 방법 rain의 경우 1보다 적게 내리면 아무 지역도 잠기지 않는다. 1. 따라서 0부터 1씩 증가하며 map의 value가 잠길 경우 visit, maps를 모두 -1로 바꿔주었다. for i in range(n): for j in range(n): if maps[i][j] 2023. 2. 26.
[백준] 1865번 웜홀(python) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. 난이도 골드3 (🥇) 2. 문제해결 과정 인터넷에 있는 많은 글들이 dist[v] != INF을 검사하지 않으면 정답 처리 된다고 했다. 그러나 벨만포드에 대한 이해도가 부족한 나는 그 말이 도무지 😭이해 되지않아 백준 질문게시판 + 이 문제와 관련된 모든 글들을 정독했다. 문제 해결에 가장 큰 힌트가 된 글을 jh05013님이 백준 질문게시판에 올려주신 "풀이 및 논란 완전히 .. 2023. 2. 26.

티스토리툴바