Doby's Lab

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net Level: Silver III Solved By: BFS BFS를 통해서 1번 노드로부터 연결된 모든 노드를 찾는 문제였습니다. from collections import deque N = int(input()) M = int(input()) adj = [[] for i in range(0, N + 1)] visited = [False for _ in range(0, N + 1)] def bfs(no..

https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net Level: Silver III Solved By: Sort, ASCII 1. char to int 파이썬에는 char에 대한 ASCII를 반환해 주는 ord() 함수가 있습니다. ord는 Ordinal Position의 약자로 문자의 원래 위치를 의미한다고 합니다. 이 함수를 이용하여 ord('9') (9의 ASCII 값)를 넘지 않는, 즉 숫자인 문자에 대해서 ord('0') (0의 AS..

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net Level: Gold V Solved By: String (split) 1. 문자열 split 입력이 까다로운 문제입니다. 파이썬에서는 이러한 문자열에 대해 핸들링을 할 수 있는 split()라는 함수가 있으며, delimiter를 ', '로 할당하여 분리를 해준 뒤에 맨 앞 원소와 맨 마지막 원소에 담겨있는 '[', ']'를 없애줍니다. 2. 모든 reverse를 처리하면 시간 초과다. 제가 알기로는 reverse 함수는 O(N)으로 알고 있습니다. ..

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net Level: Bronze II Solved By: Sieve of Eratosthenes 파이썬으로 에라토스테네스의 체를 구현해보았습니다. from sys import stdin N = stdin.readline() def getPrime(n): prime = [] visited = [False for _ in range(0, n + 1)] visited[1] = True for i in range(2, n + 1): if visited[i] == True: con..

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net Level: Silver IV Solved By: Queue 파이썬에서는 Queue를 사용하기 위해서 deque을 사용합니다. queue를 사용하지 않는 이유는 파이썬에서 제공하는 queue는 멀티스레드를 위해 동기화 과정을 거치기 때문에 문제풀이용으로는 좋지 않습니다. 그래서 deque을 사용하여 문제를 풀 수 있으며, 아래와 같이 가져올 수 있습니다. from collections import deque 그리고, deque에서는 아래와 같이 원소를 push, pop 하며 양 옆으로 가..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net Level: Silver II Solved By: Backtracking Backtracking을 통해서 풀 수 있는 문제였습니다. 부분 집합을 구하는 과정은 Recursive call을 통해 지금 현재 index에 해당하는 수를 부분집합에 포함시킬 것이냐 배제시킬 것이냐를 나누어서 코드를 쓸 수 있다면, 구현이 가능합니다. 즉, 하나의 수에 대해 2가지 경우를..

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net Level: Silver IV Solved By: Binary Search 기존 이분 탐색에 대한 감을 잃지 않기 위해 풀어본 문제였습니다. 이분 탐색을 위해서는 탐색을 진행하는 배열에 대해 정렬이 되어 있어야 하며, 현재 mid index에 해당하는 value가 찾고 있는 find value보다 작거나 큰 경우에 어떻게 처리를 하는가가 이분 탐색의..

https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net Level: Silver V Solved By: Sort 파이썬에서 다중 조건에 대해 정렬하는 방법은 A라는 상위 조건과 B라는 하위 조건이 있으면, B로 먼저 정렬을 한 후에 A로 정렬을 합니다. (Ref. https://velog.io/@1204jh/1181) 또한, 중복 값들을 없애주어야 하기 때문에 입력받은 리스트를 set으로 한 번 전환하여 중복 값들을 버린 후에 리스트로 다시..