티스토리

For Programmer

검색하기

블로그 홈

For Programmer

ji-gwang.tistory.com/m

비전공자가 전공자가 되는날까지...

구독자: 6

방명록 방문하기

주요 글 목록

백준 14502번 파이썬 문제풀이(연구소) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 간단히 0의 위치를 저장후 3개를 뽑는다 그 3개를 1로 바꾸고 바꾼상태에서 bfs를돌려 바이러스를 잠식하게 한다. 그 후 0의 개수를 세어 가장큰값을 찾으면 된다. from collections import deque N, M = map(int, input().split()) map_ = [list(map(int, input().split())) for _ in range(N)] brr = [] zero =.. 공감수 0 댓글수 0 2022. 5. 27.
백준 17298번 파이썬 문제풀이(오큰수) https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net N = int(input()) arr = list(map(int, input().split())) ans = [-1] * N # 초기 정답을 -1로 설정 stack = [0] # 첫 인덱스 0을 넣어준다. for i in range(1, N): # 만약 스택의 마지막 인덱스의 arr값이 해당 비교하고자 하는 값보다 작다면 # 그 값보다 클때까지 해당 값을 오른쪽의 큰 수로 설정해준다. while stack .. 공감수 0 댓글수 0 2022. 5. 15.
백준 1799번 파이썬 문제풀이(비숍) https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 상당히 어려운 문제이다.. 아무리 풀어도 시간초과가 나길래 풀이힌트를 보았다. 해결방법은 다음과 같다. 어차피 대각선끼리만 영향을 주니 dfs를 돌 때 반씩 나눠서 돌자는 것이다. 즉, 최대 O(2^100) 인 시간복잡도를 O(2^25) * 2 로 줄일 수 있다는 것이다.(6700만 정도) 단, 한부분만 신경을 잘써야하는데 바로 N이 짝수일때와 홀수일때 열과 행의 계산이 달라진다는 점이다. 자세한 코드는 .. 공감수 0 댓글수 0 2022. 5. 13.
백준 16724번 파이썬 문제풀이(피리 부는 사나이) https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 해당 문제 처음에 연결요소 개수 찾는 문제인지 알고 풀었으나 당연히 아니였다... 그래서 생각을 조금 더 해보니 다음과 같은 구조를 발견할 수 있었다. 1. 이미 방문처리된 그룹과 연결된다면(이미 설치했으므로) 굳이 safe-zone을 설치할 필요가 없다. 2. 아직 방문처리 되지않은 그룹과 연결되었는데 더이상 갈곳이 없다면 그때 개수를 1개 증가시켜준다. 3... 공감수 0 댓글수 0 2022. 5. 12.
백준 16946번 파이썬 문제풀이(벽 부수고 이동하기4) https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 해당 문제 굉장히 어려웠다... (알고나면 쉬운데 모르면 어려운 문제) 문제 해결은 단순하다. 1. 붙어 있는 0끼리 딕셔너리로 그룹을 매긴다. 그리고 각 그룹마다 0의 개수를 저장해놓는다. 2. 그 후 1의 위치만 찾아서 위 아래 좌 우 4방향으로 한번만 이동하면서 각각의 그룹에 저장되어있는 0의 개수만 더해주면 된다. from collections import deque .. 공감수 0 댓글수 0 2022. 5. 12.
백준 2473번 파이썬 문제풀이(세 용액) https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net O(n^2) 에 해결할 수 있기 때문에 잘생각해보면 리스트 전체의 각 지점을 반복문을 돌면서 한점을 기준으로 잡고 바로 오른쪽을 시작점 마지막 인덱스를 끝지점으로 투포인터를 돌리면 되는 간단한 문제이다. 세개의 점을 찾아야하기 때문에 투포인터의 응용버전이라 조금 생소할 수도 있지만 이기회에 잘 익히자. (참고로 N^2 임에도 불구하고 아주큰수의 + 연산때문에 파이썬3에서는 시.. 공감수 0 댓글수 0 2022. 5. 11.
백준 17404번 파이썬 문제풀이(RGB거리 2) - 탑다운(top-down) dp https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 아무리 구글링을 해도 바텀업으로만 풀었지 탑다운으로 푼 글이 없어서 탑다운으로 한번 풀어보았다. 3차원 메모제이션을 활용해서 풀었으며 마지막전에서 시작 번호와 같은지만 잘 비교해서 같다면 continue해버리는 느낌으로만 하면 쉽게 해결할 수 있다. import sys sys.setrecursionlimit(5000) N = int(input()) house = [li.. 공감수 0 댓글수 0 2022. 5. 10.
백준 1090번 파이썬 문제풀이(체커) https://www.acmicpc.net/problem/1090 1090번: 체커 N개의 체커가 엄청 큰 보드 위에 있다. i번 체커는 (xi, yi)에 있다. 같은 칸에 여러 체커가 있을 수도 있다. 체커를 한 번 움직이는 것은 그 체커를 위, 왼쪽, 오른쪽, 아래 중의 한 방향으로 한 칸 www.acmicpc.net 백준 14400번 파이썬 (편의점 2) 과 비슷한 문제이나 난이도가 꽤있는 문제이다. 결국 문제에서 요하는 것은 완전탐색이다. N이 50이라 O(N^4)까지 돌 수 있어서 완전탐색으로 접근하면 생각보다 쉽게 해결할 수 있다. 문제해결방식은 다음과같다. 1. 우선 모든 좌표의 조합을 돈다. (O(n^2)) 2. 각각의 좌표마다 모든 좌표와의 거리를 구한다. 3. 오름차순 정렬 후 1개부터.. 공감수 0 댓글수 0 2022. 5. 9.
백준 14400번 파이썬 문제풀이(편의점 2) https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 간단한 정렬 문제이다. x축 기준 정렬하여 x축 중간값 찾고 y축 기준정렬해서 y축 중간값을 찾는다. 그 후 반복문을 돌면서 거리를 계산해주면 된다. import sys input = sys.stdin.readline N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] arr.sort(key=lambda x: x[0].. 공감수 0 댓글수 0 2022. 5. 9.
백준 19590번 파이썬 문제풀이(비드맨) https://www.acmicpc.net/problem/19590 19590번: 비드맨 구슬을 엄청 좋아하는 비드맨이 있다. 구슬만 보면 갖고 싶어 하는 비드맨은 오늘도 갖고 싶은 구슬을 발견했다. 그러나 비드맨은 현재 구슬을 너무 많이 갖고 있기 때문에 더 이상 구슬을 가질 www.acmicpc.net 딱 코드포스 같은곳에서 좋아할 문제이다.. N이 아주 크고 그리디.... 아이디어 생각하기 정말쉽지 않은 문제이다. 단 생각하고나면 간단하다. 가장 큰 값과 총 합을 찾는다. 만약 (총합 - 가장 많은 구슬의 개수) - 가장 많은 구슬의 개수 가 음수라면 즉, 가장 많은 구슬의 개수를 제외한 나머지 구슬들의 합이 더 적다면 그냥 가장 많은 구슬의 개수 - 나머지 구슬 개수의 합이 답이다. 그러나 반대로.. 공감수 0 댓글수 0 2022. 5. 9.
백준 3190번 파이썬 문제풀이(뱀) https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net import sys input = sys.stdin.readline from collections import deque # 사과를 먹으면 뱀길이 늘어남 # 벽이나 자기지신의 몸과 부딪히면 게임 끝 # 뱀은 0,0 시작 길이는 1 처음엔 오른쪽 # 1.다음칸에 몸길이 늘려서 이동 # 2-1.사과가 있으면 사과 사라지고 꼬리는 그전칸 그대로 # 2-2.사과 없으면 꼬리를 끌고와서 몸길이 그전 그대로 유지 .. 공감수 0 댓글수 0 2022. 5. 8.
백준 2437번 파이썬 문제풀이(저울) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 아이디어 구상하는것이 처음에 되게 까다로웠다. 몇번의 케이스를 직접 쓰다보니 다음과 같은 정보를 얻을 수 있었다. 만약 해당 i번째의 값보다 그 앞 i - 1번째까지의 합 + 1 것보다 작거나같다면 무조건 i번째까지 합한 값은 무조건 측정이 가능하다는 것이다. 즉, 1 2 3 8 가있을때, 첫번째 1 보다 2번째 2가 1+ 1와 같기 때문에 총 합인 3까지는 무조건 측정이 가능하다는것이다. 그럼 3번째 3을.. 공감수 0 댓글수 0 2022. 5. 8.
백준 1946번 파이썬 문제풀이(신입 사원) https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 정렬 후 도저히 O(N)으로 처리할 방법이 생각이 나지 않아 풀이를 봤다. (후... 이걸 도대체 어떻게 처음부터 생각하는지 ㅠ) 풀이 방식은 다음과 같다. 1. 서류점수를 기준으로 오름차순 한다. 2. 서류점수를 기준으로 오름차순 했기 때문에 서류순위는 보장이 되고 면접순위만 비교하면된다. 3. 비교방식은 첫 기준점을 서류점수 1등의 면접순위로 잡아준다. 4. 반복문을 1번.. 공감수 0 댓글수 0 2022. 5. 7.
백준 1931번 파이썬 문제풀이(회의실 배정) https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 유명한 웰노운 그리디 문제이다. 풀이방법은 굉장히 간단하다. 끝나는 시간을 오름차순으로 정렬해서 빨리끝나는 것들만 계속 선택하면 된다. 단! 시작시간도 고려해야 하기 때문에 끝나는시간을 오름차순으로 정렬하되, 끝나는 시간이 같을 경우 시작시간을 기준으로도 오름차순을 해주어 빨리 시작하는 것을 선택해주게끔 해야한다. * 그이유는... (시작하자 말자 끝나는 회의가 존재하기 때문.. 공감수 0 댓글수 0 2022. 5. 7.
백준 2138번 파이썬 문제풀이(전구와 스위치) https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 웰노운 그리디 문제이다. 사실 처음에 생각하기가 참 쉽지 않았다... 해당 풀이방법은 다음과 같다. 1. 첫번째 스위치를 킬때와 끌때를 기준으로 나눈다. 2. 두번째 스위치부터 마지막까지 돌면서 각 자리 스위치를 킬지 말지를 결정해야하는데 방식은 다음과 같다. 현재 스위치자리 한칸 앞의 스위치와 정답 스위치의 해당 자리와 전구 상태가 같은지 비교해서 다르다면 해당 스위.. 공감수 0 댓글수 0 2022. 5. 5.
백준 14247번 파이썬 문제풀이(나무 자르기) https://www.acmicpc.net/problem/14247 14247번: 나무 자르기 영선이는 나무꾼으로 나무를 구하러 오전에 산에 오른다. 산에는 n개의 나무가 있는데, 영선이는 하루에 한 나무씩 n일 산에 오르며 나무를 잘라갈 것이다. 하지만 이 산은 영험한 기운이 있어 www.acmicpc.net 그리디 문제이나 그리디 문제들 특징이 처음보면 생각해내기가 쉽지않다는 것이다. 해당문제도 "참고로, 자른 이후에도 나무는 0부터 다시 자라기 때문에 같은 나무를 여러 번 자를 수는 있다." 이 지문때문에 난이도가 상승하는데 사실 이지문이 있어도 모든 나무를 한번씩 자르는 것이 최대 이득이다. 왜냐하면 어차피 나무들은 냅두면 계속 자라기 때문에 가장 적게 자라는 나무부터 오름차순으로 계속 베어가면 .. 공감수 0 댓글수 0 2022. 5. 5.
백준 2847번 파이썬 문제풀이(게임을 만든 동준이) https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 처음에 전체를 N번 동안 돌고 각 반복문마다 앞에서 앞,뒤(i,i+1) 값을 보면서 앞의 값이 뒤의값보다 크다면 앞의 값을 (앞의값 - 뒤의 값 + 1)으로 바꿔주는 방식으로 생각했다. 다행이 N = 100이라 O(N^2)이 통과되었지만 N 이 10000이상일때도 해당 문제를 풀려면 O(N)방식을 생각해야한다. 따라서 그 방식이 뒤에서부터 값을 비교하며 만약 앞에값이 뒤값보다 더 크다면 해당 값.. 공감수 0 댓글수 0 2022. 5. 5.
백준 2217번 파이썬 문제풀이(로프) https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 위 문제는 그리디적으로 접근해야하는데 실버4 치고는 처음에 사실 생각하기 꽤 어려웠다. 풀이법은 우선 오름차순 정렬한뒤 젤 작은값 * 총개수 , 그다음작은값 * (총개수 - 1) , ... 와같은식으로 계산한다음 가장 큰 값을 출력하는 식으로 접근하면 된다. 해당 문제의 증명은 각자 다들 잘 생각해보기 바란ㄷㅏ........ import sys input = sys.stdin.readli.. 공감수 0 댓글수 0 2022. 5. 5.
백준 1789번 파이썬 문제풀이(수들의 합) https://www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net 간단한 그리디 문제이다. 1부터 1씩증가시켜가면서 계속 더해가며 횟수를 센다. 만약 S와 같다면 그 횟수를 출력하면 되고 S보다 크다면 마지막 더한 횟수를 -1 해준 값을 출력하면 된다. S = int(input()) cur = 0 # 현재 값 i = 1 # 더할 값(1씩 증가) cnt = 0 # 더한 횟수 while True: cur += i # i만큼 계속 더한다 cnt += 1 # 횟수를 1씩 증가 if cur > S: # 만약 S보다 크다면 한개 줄이면 되므로 cnt -= 1 # 횟수를 1개 줄이고 brea.. 공감수 0 댓글수 0 2022. 5. 5.
백준 24956번 파이썬 문제풀이(나는 정말 휘파람을 못 불어) https://www.acmicpc.net/problem/24956 24956번: 나는 정말 휘파람을 못 불어 '유사 휘파람 문자열'인 부분 수열의 개수를 $1\,000\,000\,007(= 10^9+7)$로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제 사실 골드 4 치고는 굉장히 어려운 문제이다. 접근 방법은 다음과 같다. 1. 누적합으로 W와 E의 개수를 미리 구해야 놓아야 한다. (단 E는 반대방향으로 누적합) 2. H를 만날때 마다 해당 H지점에서 왼쪽으로 W의 개수 * 2 ^ 오른쪽으로 E의 개수 - E의개수 - 1 로 구해야한다. 3. pow 내장 메서드와 3번 째인자 Mod 사용하면 더욱더 빠른 시간복잡도로 2 ** N 계산이 가능하다. 여기서 의문인 2 ^ 오른쪽으로 E의.. 공감수 0 댓글수 0 2022. 5. 2.
백준 16472번 파이썬 문제풀이(고냥이) https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 간단한 투포인터 문제이다. 하지만 주의할 점은 문자의 종류가 N개 보다 작아도 최댓값을 갱신해주어야 한다. (문제에서 이부분에 대한 설명이 약간 부족했다. 이 부분을 테스트 케이스로 보여주면 좋았겠다.. ㅠ) alpha = [0] * 26 N = int(input()) word = input() + 'z' # 문자열의 범위를 벗어나지 않게 하기 위해 아무 문자로 패딩 s = 0 # 시작인덱스 e = 0 #.. 공감수 0 댓글수 0 2022. 5. 2.
백준 1644번 파이썬 문제풀이(소수의 연속합) https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 1. 빠른 소수 구하기(에라토스테네스의 체 최적화) 2. 투포인터 (연속된 구간의 합) 위의 2가지를 이용하면 쉽게 문제를 해결할 수 있다. N = int(input()) # 빠른 소수 구하기 (에라토스 테네스의 체 최적화) sosu = [True for i in range(N + 1)] sosu[0], sosu[1] = False, False temp_sosu = [] for i in range(2, len(sosu)): if not sosu[i]: continue temp_sosu.append(i) index =.. 공감수 0 댓글수 0 2022. 5. 2.
백준 2887번 파이썬 문제풀이(행성 터널) - (크루스칼) https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 모르면 한없이 어렵고 알고나면 한없이 쉬운 문제이다. 그냥 간단하다 1. 리스트안에 x,y,z 좌표와 현재의 점 번호를 함께 튜플로 저장한다. 2. 각각의 점을 기준으로 정렬한 후 3. 바로 붙어있는 점이 가장 짧은 거리이므로 그 거리를 계산해서 4. 다시 리스트 하나에 해당 두점과 거리를 모두 넣어준다. 5. 그 후 거리를 기준으로 오름차순 정렬 후 크루스칼 해주.. 공감수 0 댓글수 0 2022. 4. 28.
백준 1647번 파이썬 문제풀이(도시 분할 계획) - (크루스칼) https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 간단히 크루스칼 코드만 알고 있다면 쉽게 해결할 수 있다. 조건 2가지 ( 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. , 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다.) 가 있는데 그 중 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 의 조건을 생각하기가 까다로울 수 있다. 문제를 잘보.. 공감수 0 댓글수 0 2022. 4. 27.
백준 20955번 파이썬 문제풀이(민서의 응급 수술) - (유니온 파인드) https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 간단한 유니온 파인드 문제이다. 풀이 방식은 유니온 파인드 돌린 후 1. 만약 두 노드가 이미 연결되어 있다면 연산횟수 + 1 2. 모든 연산이 끝난 후 연결되지 않은 연결요소 집합이 몇개 존재하는지 set함수를 통해 체킹 import sys input = sys.stdin.readline def find(x): if x != parent[x]: parent[x] = find(parent[x]).. 공감수 0 댓글수 0 2022. 4. 26.
백준 20040번 파이썬 문제풀이(사이클 게임) - (유니온 파인드) https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 보통의 유니온파인드 문제와 비슷하게 크게 어려운 문제는 아니다. 하지만 파이썬 사용자라면 1. 경로 압축 2. 유니온 바이 랭크 두가지 모두 최적화 해주어야 통과할 수 있다. import sys input = sys.stdin.readline # 1. 경로 압축 def find(x): if x != parent[x]: parent[x] = find(parent[x]) # 재귀를 돌며 해당 부.. 공감수 0 댓글수 0 2022. 4. 26.
백준 1939번 파이썬 문제풀이(중량 제한) - (1. 최대힙 다익스트라, 2. 유니온 파인드) 해당 문제는 풀이가 많이 존재할 수 있으나 크게 생각나는 2가지 방법으로 구현했다. 1. 최대힙을 이용한 다익스트라 2. 중량을 내림차순 정렬 후 유니온 파인드 1. 최대힙을 이용한 다익스트라 import heapq import sys input = sys.stdin.readline def dijkstra(v1, v2): global ans q = [] heapq.heappush(q, (-(1 공감수 0 댓글수 0 2022. 4. 25.
백준 18352번 파이썬 문제풀이(특정 거리의 도시 찾기) 해당 문제는 BFS로 풀 수도 있고 모든 거리를 1로 두고 다익스트라를 돌려도 된다. 1. BFS 풀이 import sys from collections import deque input = sys.stdin.readline N, M, K, X = map(int, input().split()) # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호 graph = [[] for _ in range(N + 1)] for _ in range(M): a, b = map(int, input().split()) graph[a].append(b) ans = [] visited = [False] * (N + 1) def bfs(start): queue = deque([[start, 0]]) visited[star.. 공감수 0 댓글수 0 2022. 4. 21.
백준 4485번 파이썬 문제풀이(녹색 옷 입은 애가 젤다지?) 무지성 다익 돌리면 된다. 단, 다익을 구하기 위해 아주 큰값으로 초기화를 해줄텐데 다익스트라를 시작하기 전 0,0의 거리 비용을 초기에 입력받은 배열의 0,0에 있는 좌표의 값으로 시작하는 것이 아주 중요하다. import heapq import sys input = sys.stdin.readline def dijkstra(): q = [] heapq.heappush(q, (arr[0][0], 0, 0)) distance[0][0] = arr[0][0] while q: cost, r, c = heapq.heappop(q) if r == N - 1 and c == N - 1: return cost if cost > distance[r][c]: continue for i in range(4): nr = r.. 공감수 0 댓글수 0 2022. 4. 21.
백준 13910번 파이썬 문제풀이(개업) 간단한 DP문제이다. 약간 웰노운이라 쉽게 풀 수 있었다. 최대 2개만 고를 수 있기 때문에 실버이지 않나 생각해본다. 이 중반복문을 돌면서 한개 뽑았을때 2개뽑았을 때 나눠서 생각하면 쉽게 풀 수 있다. import sys sys.setrecursionlimit(10000) input = sys.stdin.readline N, M = map(int, input().split()) w_size = list(map(int, input().split())) dp = [1 공감수 0 댓글수 0 2022. 4. 21.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.