목록알고리즘/백준 (56)
이숭간 공부기록
[백준] 파이썬 _ 연구소3
https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 문제유형: BFS,그래프탐색, 문제풀이 : 비활성 바이러스에 활성바이러스가 닿으면 비활성도 활성이 된다..... 는 것을 문제에서 놓침. 또 이때에는 시간이 증가하지 않음 그냥 변하기만함.. 활성바이러스가 빈칸으로 복제될때만 시간이 증가하는것이고 바이러스에 닿으면 그냥 변하게만 한다. 가능한 m개의 바이러스 조합에 대해 bfs를 돌려야되는데 이때 graph를 deepcopy하면 시간초과가난다. graph는..
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제유형 : 최소스패닝트리 (MST) 문제풀이 : 변형없는 전형적인 최소스패닝트리 문제이다. 프림과 크루스칼 알고리즘을 쓸 수 있는데 구현이 좀더 쉬운 크루스칼 알고리즘을 이용했다. 크루스칼 알고리즘에서는 서로소집합개념인 유니온파인드 개념을 알고있어야한다. 정답코드 : import sys input = sys.stdin.readline #크루스칼알고리즘 # 비용을 오름차순으로 정렬하고 # 사이클이 발생하면 추가하지않고, 사이클이 발생하지 않으면 추가한다. # 특정 원소가 속한 집합을 찾..
[백준] 14627번 파이썬 _ 파닭파닭
https://www.acmicpc.net/problem/14627 14627번: 파닭파닭 첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파 www.acmicpc.net 문제유형 : 이분탐색 문제풀이 : 이런 유형의 문제를 이미 알고있어서 보자마자 코드를 짰는데 웬걸 예외를 잡느라 8번은 더 제출했다... 날괴롭혔던 부분은 자를 파의길이가 0이되는,,, 즉 이분탐색에서 mid값이 0이되는 경우였다..ㅜ 이해를 돕기위해 예시를 들면, 파의모든 길이를 더한만큼 치킨의 개수가 있다면 파를 길이1로 잘라야 모든 치킨에게 같은양의 파를..
https://www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 문제유형 : 구현, 플로이드와샬 문제풀이 : 얼마전에 프로그래머스에서 푼 https://esoongan.tistory.com/178랑 아주 똑같은문제였다! 역시 한번이라도 푼 문제랑 비슷한 문제면 금방 푸는것같다. 양치기가 답인가? 문제 키포인트 내 자식노드의 부모노드에 내 부모노드를 추가한다. 내 부모노드의 자식노드에 내 자식노드를 추가한다. 약간 주의해야 할 점이 있는데 만약 내 부모의 부모들을..
https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제유형 : BFS 문제풀이 : BFS로 인접한 국가들을 방문하며 푸는 문제 문제에서 '다른국가를 거쳐가도(심지어 이미 방문한국가라도)된다. 라는 말이 나오는데 bfs로풀때 만약 2의 인접한 국가가 3,4라고 했을때 2->3, 2->4 으로 뻗어나가기때문에 2번이 2번 방문되어도 된다 이런의미로 해석하면 된다. 큐에 국가를 넣을때마다 비행기를 한번 탔다는것을 ..
https://www.acmicpc.net/problem/status/14499/28/1 문제유형 : 구현 문제풀이 : 이동시에 주사위를 바꿔주는것을 구현할 수 있어야한다. 동서남북에 따라 좌표이동을 생각해서 미리 구현해놓으면 된다. 다른분들의 풀이도 수동으로 동서남북에 좌표변환을 지정해두었다. 두번째 푸는 문젠데 첫번째때는 아마 못풀어서 답을 보고 풀었던 기억이 있는데 이번에는 바로 풀었다. 실력이 조금씩 늘긴 하나보다! 더 화이팅! 정답코드 : import sys input = sys.stdin.readline graph = [] n, m, x, y, k = map(int, input().split()) for i in range(n): graph.append(list(map(int, input()...