https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제를 처음 보면 딱 드는 생각이 에라토스테네스의 체이다. 소수는 구하는 문제로는 백준 1929번에서 에라토스테네스의 체를 활용하여 소수를 빠르게 구했었다. 이번 문제도 똑같이 완전탐색으로 for문을 돌리면서 가능한 모든 경우를 다 에라테스테네스의 체를 이용하여 걸러내려고 했지만 시간초과가 떴다. 조금만 생각해봐도 N = 8이면 숫자가 9천만개가 있는데 그걸다 계산하려하니 시간초과가 뜰..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 각 숫자가 어느곳으로 연결되었는지를 리스트에 저장하고 DFS(깊이 우선 탐색)를 돌려준다. 코드를 먼저 보고 설명하는 편이 더 나을거 같다. import sys sys.setrecursionlimit(10000) input = sys.stdin.readline def Sol(): N, M = map(int,input().split())..

https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제를 보고 그냥 바로 C++코드를 그대로 갖다쓰면 안되나? 했지만 당연하게도 숫자범위가 50만... 시간복잡도가 N * N인 버블 정렬을 사용하면 시간초과가 날게 뻔했다. 구현이 어려운 문제는 아니고 아이디어때문에 골드2인거 같다. C++ 코드를 해석하면 정렬이 완전히 되었을때 한줄 반복을 몇번수행했냐 라는 코드다. 따라서 정렬이 완성되고 나서의 i값에 +1을 하면 된다...

https://www.acmicpc.net/problem/20442 20442번: ㅋㅋ루ㅋㅋ 어떤 문자열에서 몇 개의 문자를 지워서 부분 수열을 만들 수 있다. 예를 들어, ABC의 부분 수열은 ABC, AB, BC, AC, A, B, C와 빈 문자열이다. www.acmicpc.net 재밌는 문제 이름을 찾다가 ㅋㅋ루ㅋㅋ를 발견하여 바로 풀기 시작했다. 왼쪽과 오른쪽 끝부터 가운데로 오면서 K의 개수를 세다가 R을 만나면 적은 K의 개수를 2배+1 하고 R의 개수를 더한다. 예를 들어 K R K K R K R R R K K K R K K 가 있다면 양쪽 끝부터 k의 개수를 센다.왼쪽에서 첫번째 R은 1번째 인덱스에 있고 오른쪽에서 첫번째 R은 -3번째 인덱스에 있다. K R K K R K R R R K ..

https://www.acmicpc.net/problem/13140 13140번: Hello World! N이 주어질 때 hello + world = N을 만족하는 서로 다른 한 자리 자연수(0 포함) d, e, h, l, o, r, w를 구해서 아래 그림과 같은 형태로 출력하는 프로그램을 작성하여라. 단, h와 w는 0이 될 수 없다. www.acmicpc.net 문제 이름이 Hello World! 다. 뭔가 반가워서 시도했는데 문제도 되게 재밌는 문제다. 문제를 고민하다가 어차피 반복에 들어가는 범위가 0~10까지 밖에 안되므로 여러번 충접해도 1억 이내에 계산할수 있다. (파이썬은 보통 1초에 1억번 계산) 그래서 완전탐색(브루트포스)으로 경우의 수를 다 훓으면서 풀었다. import sys inp..

https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1 ≤ M ≤ 9999, M은 홀수)이 주어지고, 그 다음 줄부터 이 수열의 원소가 차례대로 주 www.acmicpc.net 우선순위 큐를 2개 이용하는 문제로 왼쪽은 최대힙, 오른쪽은 최소힙으로 구현하여 중앙값을 구했다. 양쪽 힙의 len이 같을때는 왼쪽에 heappush를 하고 나머지는 오른쪽에 넣어준다. 이때 왼쪽의 최댓값이 오른쪽의 최솟값보다 크면 둘의 위치를 바꿔준다. 위의 과정을 반복하므로써 중앙값을 우선순위 큐를 이용하여 구할 수 있다. 손으로 예시를 들어서 직접 써보면 이해하기..