알고리즘/백준
-
[백준 / Python] 2606번 바이러스 | 초코더알고리즘/백준 2020. 1. 17. 23:02
https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다. www.acmicpc.net 접근법 저는 BFS를 이용해 풀었습니다! 이 링크를 참고하시면 돼요~ https://sinsomi.tistory.com/entry/%EB%B0%B1%EC%A4%80-Python-1260%EB%B2%88-DFS%EC%99%80-BFS-%EC%B4%88%EC%BD%94%EB%8D%94 다 같은데 다른..
-
[백준 / Python] 1260번 DFS와 BFS | 초코더알고리즘/백준 2020. 1. 17. 00:26
https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. www.acmicpc.net 접근법 DFS와 BFS는 개인적으로 복잡하다고 느낀 코드이기 때문에 코드를 나누어서 세세히 설명해보겠습니다. 입력은 예제 입력1인 4 5 1 을 예로 들겠습니다. 1 2 1 3 1 4 2 4 3 4 1. N,M,V를 받아오고 '0'으로 이루어진 인접행렬 (N+1)*(N+1) 짜리 생성 ..
-
[백준 / Python] 1205번 등수 구하기 | 초코더알고리즘/백준 2020. 1. 16. 19:36
https://www.acmicpc.net/problem/1205 1205번: 등수 구하기 첫째 줄에 N, 송유진의 새로운 점수, 그리고 P가 주어진다. P는 10보다 크거나 같고, 50보다 작거나 같은 정수, N은 0보다 크거나 같고, P보다 작거나 같은 정수이다. 그리고 모든 점수는 2,000,000,000보다 작거나 같은 자연수 또는 0이다. 둘째 줄에는 현재 랭킹 리스트에 있는 점수가 비오름차순으로 주어진다. 둘째 줄은 N이 0보다 큰 경우에만 주어진다. www.acmicpc.net 접근법 새로 들어온 점수를 append()함수로 추가하고 정렬해줍니다. 그리고 새로 들어온 점수의 등수를 index()함수를 이용해 구해줍니다. 그런데 두번째 입출력 예와 같이 새로들어온 점수가 마지막 점수와 같으면서..
-
[백준 / Python] 2399번 거리의 합 | 초코더알고리즘/백준 2020. 1. 15. 17:16
https://www.acmicpc.net/problem/2399 2399번: 거리의 합 첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다. www.acmicpc.net 접근법 n정수들을 입력받아온 후 이중for문을 이용해 각각의 차의 절대값을 더해주었습니다. abs()함수를 쓰면 쉽게 음수를 양수로 바꿀 수 있었습니다. 실행은 되는데 시간초과가 나서 어떻게 고쳐야 할지 고민해봐야겠어요 ㅜ 나의코드 import sys temp=0 n=int(input()) nums=list(map(int,sys.stdin.readline().split())) #한줄만 입력받을땐 그냥 sp..
-
[백준 / Python] 2959번 거북이 | 초코더알고리즘/백준 2020. 1. 14. 00:40
https://www.acmicpc.net/problem/2959 2959번: 거북이 문제 거북이는 이제 어떤 것에도 흥미를 느끼지 않는다. 그 이유는 거북이가 300년동안 살았고, 그 동안 모든 것들을 다 해보았기 때문이다. 거북이는 시간을 떼우는 무엇인가를 하려고 한다. 이번 주말에 거북이는 거북이 세계에서 매우 유명한 게임인 "가장 큰 직사각형 만들기"를 해보려고 한다. 이 게임을 시작하기 전에 거북이는 양의 정수 네 개를 머릿 속에 생각해야 한다. 한 방향으로 움직이기 시작하고 90도 회전한 뒤에 새로운 방향으로 움직인다. 이런 식 www.acmicpc.net 접근법 nums에 정수들을 입력받고, nums를 큰순서대로 나열합니다. 넓이가 가장 클경우의 직사각형은 (두번째큰수)*(가장작은수) 의 식..
-
[백준 / Python] 5052번 전화번호 목록 | 초코더알고리즘/백준 2020. 1. 14. 00:14
https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다. 예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자 긴급전화: 911 상근: 97 625 999 선영: 91 12 54 26 이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 www.acmicpc.net 접근법 numbers배열에 전화번호 목록을 입력받아옵니다. 그리고 정렬시킵니다. 문자열을 정렬시키면 ['911', '97625999'..
-
[백준 / Python] 3047번 ABC | 초코더알고리즘/백준 2020. 1. 13. 18:04
https://www.acmicpc.net/problem/3047 3047번: ABC 문제 세 수 A, B, C가 주어진다. A는 B보다 작고, B는 C보다 작다. 세 수 A, B, C가 주어졌을 때, 입력에서 주어진 순서대로 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 세 수 A, B, C가 주어진다. 하지만, 순서는 A, B, C가 아닐 수도 있다. 세 수는 100보다 작거나 같은 자연수이다. 둘째 줄에는 A, B, C로 이루어진 세 글자가 주어지며, 이 순서대로 출력하면 된다. 출력 주어진 세 수를 주어진 출력 순서대로 출력하면 www.acmicpc.net 접근법 입력받은 숫자는 nums라는 리스트로 저장하고, 입력받은 문자열은 strs라는 변수에 저장합니다. nums를 정렬합니다. 그리고 st..
-
[백준 / Python] 10825번 국영수 | 초코더알고리즘/백준 2020. 1. 13. 17:51
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 100보다 작거나 같은 자연수이다. 이름은 알파벳 대소문자로 이루어진 문자열이고, 길이는 10자리를 넘지 않는다. www.acmicpc.net 접근법 sort()와 lambda를 이용해서 정렬시킨다는 것이 포인트였습니다. 그런데 국어점수와 수학점수는 높은순대로 정렬시켜야해서 reverse=True를 사용해주어야 하는가 했는데, 정렬조건이 여러개일때는 사용이 불가하였습니다. 어차피 모두 정수이므로 '-'만 붙..