[백준] 14621 나만 안되는 연애 | MST (Kruscal) | Gol3 Pythonhttps://www.acmicpc.net/problem/14621 접근유형 : MST - kruscal [문제해석] 모든 대학교를 연결하는 최단경로 = MST 남초대학교M 와 여초대학교W 사이의 간선만 경로에 포함할 수 있음 모든 학교를 연결하는 경로가 존재하지 않을 경우 -1 출력 1 1 크루스칼~로 해보자 간선수 노드수에 비해 그렇게 많은 것같진 않고 프림보다 빠른 편이니까특이사항은 간선 선택할 때, 연결된 노드의 학교종류가 같으면 선택하지 않도록 짜면 될 듯 구상 간선 (가중치, 노드1, 노드2) 형식으로 한 리스트에 입력받음 이 때 노드1과 노드2의 학교타입이 같으면 리스트에 넣지 않음 (그래프에 사용할..
백준
[백준] 1922 네트워크 연결 | MST (Prim, Kruscal) | Gol4 Pythonhttps://www.acmicpc.net/problem/1922 접근유형 1 : MST - prim (396ms)유형 2 : MST - kruscal (240ms)간선 수가 노드수보다 100배 많은데 prim보다 kruscal 이 더 빠르네 [문제 해석]최소의 비용으로 모든 컴퓨터를 연결하는 경로 구하기= MST 최소 스패닝 트리 구하기1 1 1 간선이 주어질 때 두 노드번호가 같을 수도 있다 MST 프림으로 풀어보자~ 노드선택 구상 - Prim간선 입력받아서 연결된 첫번째 노드별로 (가중치, 노드2) 형태로 리스트에 저장최소힙 사용(정렬유지하며 잦은 삽입 필요)현재 그래프에 포함되어있는 노드 표시하는 배열..
[백준] 1197 최소 스패닝 트리 | MST (Kruscal, Union Find) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 크루스칼 알고리즘크루스칼 알고리즘은 간선 추가 시마다 사이클이 생기는 지 확인하기 위해 주로 Union Find를 사용한다. 그래서 그 내용도 나옴! [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제1 1 음수 가중치 간선 존재, 양방향가중치 절댓값 시간 제한 1초메모리 제한 128MB [개념]MST 구하는 법크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것 직전 글에 프림으로 풀어보았고, 이번에는 크루스칼로 풀..
[백준] 1197 최소 스패닝 트리 | MST(Prim) | Gol4 Pythonhttps://www.acmicpc.net/problem/1197 접근유형 : MST - 프림 알고리즘프림이 노드를 추가하는 방식이지만 결국은 간선의 가중치를 확인해야 하는데논리를 너무 노드에만 집중해서 생각했다. 생각을 열어두자~ [문제 해석]주어진 그래프의 최소 스패닝 트리MST를 구하는 문제 1 1 음수 가중치 간선 존재, 양방향 가중치 절댓값 시간 제한 1초 메모리 제한 128MB [개념]MST 구하는 법 크루스칼 : 간선을 greedy로 선택, 사이클없이(union find)프림 : 노드를 선택. 노드 중 간선 가중치가 가장 적은 것정점보다 간선 개수 범위가 더 커서 프림으로 짜보자 구상 1 간선 입력받아 리스트..
[백준] 4195 친구 네트워크 | Union Find, 경로압축 | Gol2 Pythonhttps://www.acmicpc.net/problem/4195 접근유형 : union find (합집합)union find 인데 노드 이름이 문자열인union find 짤 때 모든 연산은 루트노드 기준으로 할 것 기억하기..~! [문제 해석]sns 친구추가(합집합 연산) 시마다 그 새로운 친구 네트워크에 포함된 전체 친구 수 구하기친구 네트워크란 친구 관계만으로 이동할 수 있는 사이를 말함친구 = 노드, 친구관계 = 간선시간제한 3초친구관계 수 앗.. 사이클이 생길수도 있겠네..? 같은 네트워크면 친구추가 무시해야겠다노드가 친구이름으로 주어지니까 딕셔너리를 쓰자 구상 : 노드이름 문자열에 해당하는 번호를 따로 ..
[백준] 1717 집합의 표현 | Union Find, 경로압축 | Gol5 Pythonhttps://www.acmicpc.net/problem/1717 구상유형 : union find +경로압축둘 다 새롭게 구현해본 개념이라 공부가 많이 됐다!union find만으로는 시간초과가 나서 경로압축 등 find함수를 최적화하여 해결했다.새로운 재미가 있던 문제~ [문제 해셕]0~n 각 하나씩만 원소로 갖는 집합 n+1개가 주어지고, 이들 간의 집합 연산 결과 출력하기0 a b : a와 b가 포함되어있는 집합의 합집합 연산1 a b : a와 b가 같은 집합의 원소인지 확인하는 연산a = b 일 수도 있음1 1 시간제한 : 2초 트러블 슈팅TS 1 : 합집합 연산 시 x,y가 포함된 집합 전체를 연결시켜야하므로..
[백준] 16946 벽 부수고 이동하기 4 | BFS | Gol2 Pythonhttps://www.acmicpc.net/problem/16946 채점 되게 천천히 됨 쫄깃하네여..ㅎ골드 쯤 되니까 시간제한이 문제가 되기 시작한다 ㅎ허허 구상유형 : bfs [문제 해석]벽이 존재하는 맵이 주어짐. 각 벽마다 벽이 없어졌을 때, 해당 벽 위치에 인접한 공간 크기를 구하는 문제빈 공간은 0, 벽은 1벽 위치에 해당하는 공간 크기를 10으로 나눈 나머지를 출력시간제한 : 2초구상 1 (timeout)전체를 돈다벽(1)이 나오면 해당 벽에 인접한 공간을 bfs 돌며 공간 크기를 계산한다벽 위치에 공간 크기를 10으로 나눈 나머지를 기록한다 구상 2 (성공)전체를 돈다방문 전인 빈 공간(0)이 나오면 bfs 인접한..
[백준] 2146 다리만들기 | BFS | Gol3 Pythonhttps://www.acmicpc.net/problem/2146 pypy로만 성공한 풀이입니다.(python은 시간초과)구상유형 : bfs비슷한 문제들을 푸는 중이라 접근은 어렵지 않게 했으나조건문 하나 잘못적어서 시간 진짜 많이 썼다 도륵시간초과만 나서 시간을 줄이는 방법만 고민했는데 코드에 잘못된 부분이 있었다코드에 논리적인 오류가 있어도 오답이 아닌 시간초과만 날 수도 있다는 것을 깨달은 시간,,,pypy로만 통과했지만 핵심적인 문제는 찾았고 더 이상 시간복잡도 개선에 시간을 쓰는 건 무리라고 판단. 넘어가자! [문제 해석]땅과 땅을 연결하는 가장 짧은 다리 길이 찾기다리와 인접해있으면 연결된 것임시간제한 2초 구상전체를 2번 돌아야 ..
[백준] 13549 숨바꼭질 3 | BFS | Gol5 Pythonhttps://www.acmicpc.net/problem/13549 구상유형 : bfs직전에 푼 1697과 유사그래서 좀더 깔끔하게 풀 수 있었다! [문제 해석]1697 숨바꼭질 문제와 동일하나, 2배 이동을 하는 경우 드는 시간이 0이라는 점만 다르다.N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지+1-12배 0 ≤ N, K ≤ 100,000시간제한 2초메모리제한 512 MB 구상매번 세가지 경우 모두 bfs 돈다단, 아래 조건을 만족하지 않으면 큐에 넣지 않는다.이미 방문했던 숫자의 경우 이전의 해당 숫자까지 갔던 최소이동횟수보다 클 때숫자가 이동 가능 범위를 벗어날 때 (0 ≤ N ≤ 100,000)..
[백준] 1697 숨바꼭질 | BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/1697 구상유형 : bfs메모리 초과는 처음봐서 고생했다. 문제 조건을 잘못이해했음..~ 그래도 배운 게 있으니까TIP : dict, set보다 처음부터 초기화해서 쓰더라도 list가 더 메모리 적게 쓰고 빠를 수 있다.Q : 아니 다들 visited체크를 해서 한번 방문한 노드는 다시 방문하지 않게 짜는데, 그게 왜 되지?? 더 최적으로 방문한 경로가 답이면 답이 걸러지지 않나 [문제 해석]N에서 K로 가는 가장 빠른 횟수 찾기한 횟수에 할 수 있는 이동의 종류는 3가지 1. +1 2. -1 3. 2배0 ≤ N, K ≤ 100,000 -> 이게 처음 주어지는 위치..
[백준] 2667 단지번호붙이기 | DFS,BFS | Sil1 Pythonhttps://www.acmicpc.net/problem/2667 구상유형 : dfs (bfs도 가능할듯) [문제 해석]연결된 그룹의 수와 크기를 세는 문제가로세로로 인접되어있으면 같은 그룹임그룹의 총 개수 셈각 그룹마다 몇개가 포함되어있는지 개수 셈시간제한 1초5 구상칸 전체를 돈다visited면 넘어간다방문 전이면서 1인 칸을 만나면 dfs시작그 주변에 있는 1인 칸만 스택에 넣으며 dfs돈다 두두두돌면서 1 대신 해당되는 그룹 번호로 바꿔준다 (0,1은 이미 입력데이터에서 사용중이므로 그룹 번호는 2부터 사용)dfs끝나면 칸 전체 돌기를 이어서 진행 트러블 슈팅문제 구상에서 실수해서 한번 헤맸다 dfs bfs도 아직 멀었구나..
[백준] 14698 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) | Gol4 | 힙 Pythonhttps://www.acmicpc.net/problem/14698 구상유형 : 힙최소값이 어떤 경우일지 고민을 했는데 찾아보니까 그냥 매번 현재 존재하는 슬라임 중 가장 작은 것들을 쓰면 최소라고 함. 왜지?[문제 해석]슬라임을 2마리씩 합성하는데, 합성 시마다 두 슬라임의 에너지의 곱만큼 전기가 든다.합성 결과로 두 슬라임의 에너지의 곱만큼의 에너지를 가진 한마리의 새로운 슬라임이 됨 슬라임을 모두 합성해 한마리로 만드는 데에 드는 모든 전기의 곱의 최소값 답 : 테스트케이스마다 모든 전기의 곱의 최솟값을 1, 000, 000, 007 로 나눈 나머지 출력 구상최소값을 어케 구할까..-> 그냥 작은..
[백준] 13094 과제 | Gol3 | 힙 Pythonhttps://www.acmicpc.net/problem/13904 구상풀이 1 : 별다른 자료구조 사용않고 그냥 구현함 (112ms) 로직 특성상 힙을 활용한 방식보다 느리다.풀이 2 : 힙 (56ms)이 방식이 속도가 훨씬 빠르다!접근 방식을 아예 다르게 해야 힙을 쓸 수 있었다. 로직을 새로 짬. 더 효율적인 로직임! [문제 해석]얻을 수 있는 점수 최댓값 구하기과제는 하루에 1개만, 완료 시 점수과제 별로 점수 다름. 마감일 지나면 점수x과제 개수N 마감일까지 남은 일수d 시간 제한 : 1초 구상 - 힙 쓰는 ver과제를 점수 큰 순으로 마감일에 가장 가까우면서 배치가능한 자리에 배치구현과제 점수 기준으로 최대힙을 만든다.점수가 가장 큰 과..
[백준] 19638 센티와 마법의 뿅망치 | Sil1 | 힙 Pythonhttps://www.acmicpc.net/problem/19638 구상풀이 1 : 힙최대힙 음수로 써줘야 하는거 꽤나 귀찮네.. 메서드 만들어서 쓸 걸 그랬나풀이 2 (시간초과) : heapq 안쓰고도 풀 수 있나 싶어서 그냥 리스트랑 sort써서도 해봤다.-> heappush 대신 값을 넣을 때마다 다시 정렬해준다.-> 예제는 통과했으나 시간초과!heapq는 값을 정렬된 상태로 유지하며 계속 넣었다뺐다 해야할 때 유용할 것임을 느꼈다. [문제 해석]마법 뿅망치 : 키/2 가 됨. 키가 1일경우 영향x문제에 안적혀있었는데, 키가 홀수일 경우 2로 나눈 몫으로 하면됨항상 가장 키가 큰 사람 중 한명을 때림때리는 횟수T 제한있음답 : ..
[백준] 11279 최대 힙 | Sil2 | 힙 Pythonhttps://www.acmicpc.net/problem/11279 구상유형 : 힙(최대힙)파이썬은 그냥 heapq쓰면 되는 문제 구상최대힙이므로 heapq쓸 때 값을 음수로 저장입력된 자연수를 힙에 push입력이 0이면 가장 큰 값을 pop (출력하고 그 값을 배열에서 제거) 트러블 슈팅x 코드# v1 : 힙(최대힙)#파이썬은 그냥 heapq쓰면 되는 문제'''- 최대힙이므로 heapq쓸 때 값을 음수로 저장- 입력된 자연수를 힙에 push- 입력이 0이면 가장 큰 값을 pop (출력하고 그 값을 배열에서 제거)'''import heapqimport sysinput = sys.stdin.readlineN = int(input())heap = ..
