BOJ 4153. 직각삼각형 https://www.acmicpc.net/problem/4153 소스코드 #include int main(){ while(1){ int x,y,z; scanf("%d %d %d", &x, &y, &z); if(x == 0) break; int max = 0; if(max < x) max = x; if(max < y) max = y; if(max < z) max = z; if(max == x) x = 0; if(max == y) y = 0; if(max == z) z = 0; if(max*max == x*x + y*y + z*z) printf("right\n"); else printf("wrong\n"); } }

BOJ 11279. 최대 힙 https://www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 풀이 heapq를 이용해서 풀었다. 주의할 점 세가지는, python3로 제출할 경우 시간초과, pypy3로 제출 input()으로 할 시 시간초과, sys.stdin.readline().rstrip()로 할 것 최대 힙으로 만들기 위해 (-n, n)로 튜플을 넘겨주어 -n기준 최소 힙 생성. heapq.heappop(heap)[1] 하여 n기준 최..

BOJ 1927. 최소 힙 https://www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 heapq를 이용해서 풀었다. 주의할 점 두가지는, python3로 제출할 경우 시간초과, pypy3로 제출 input()으로 할 시 시간초과, sys.stdin.readline().rstrip()로 할 것 python heapq 모듈 input()과 sys.stdin 소스코드 import heapq from sys import stdin N =..

BOJ 2606. 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 DFS를 통해 탐색한 노드의 수 - 1 (1번 컴퓨터는 제외) 를 구해주면 된다. 틀렸습니다 를 굉장히 많이 봤는데 이유는 그래프를 단방향으로 만들어 주어서 이다. 테스트 케이스에선 잘 나와서 생각하지 못했다. 앞으로 방향 을 언급하지 않으면 양방향으로 해 주어야 하는것을 잊으면 안되겠다. 재귀로도 풀 수 있다. dfs 파이썬 구현 소스코드 import sys from ..

BOJ 1003. 피보나치 함수 https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 테스트 케이스에 대해 0이 출력되는 횟수와 1이 출력되는 횟수를 구해보면, 테스트 케이스 0이 출력되는 횟수 1이 출력되는 횟수 0 1 0 1 0 1 2 1 1 3 1 2 4 2 3 5 3 5 6 5 8 7 8 13 이렇게 된다. 이는 테스트 케이스(N)에 대한 0과 1의 출력 = (N-1)의 0 출력 갯수 + (N-2)의 0 출력 갯수 (N-1)의 1 출력 갯수 + (N-2)의 1 출력 갯수 임을 알 수 있다. 피보나치의 정의는 이것이고 잘 보면 위의 표..

BOJ 1764. 듣보잡 1764번: 듣보잡 (acmicpc.net) 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 풀이 파이썬의 x in y를 이용해서 풀었더니 시간 초과가 났다. N과 M이 500,000 이하의 큰 수라 연산하는 것이 오래걸리나 싶어서 탐색을 이진탐색 으로 바꾸어 풀었다. 이진탐색(binary seart)는 O(NlogN) 파이썬 내장함수 sort()는 O(logN)이므로 이진탐색이 더 좋다. def binary_search(start, end, list, target, result):..