본문 바로가기

코딩테스트 문제풀이

[python3]2146번:다리만들기 다리 만들기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 192 MB 34525 12576 7824 33.328% 문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다. 위의 그림에서 색이 있는 부분이.. 더보기
집합의 표현 1717번 python Union-Find를 이용한 풀이: import sys sys.setrecursionlimit(10**5) def union(x,y): x=union_find(x) y=union_find(y) if x 더보기
Union-Find 1976번 여행가자 union-Find 의 동작과정 다음과 같이 노드가 1,2,3번끼리 연결이 되어있다고 가정을 해봅시다. 다음 사진은 2번과 3번이 연결되었다고 가정을 해보았습니다. 그럼 재귀적으로 순차적으로 탐색을 진행해서 3번 노드는 2번으로 교체를 해주고 다시 2번 노드를 찾아서 1번과 연결이 되어있다면 더 작은값으로 변환을 해주어야합니다. 따라서 재귀적으로 호출을 진행하여 1,2,3번 노드는 1번으로 초기화를 진행해주면 1번과 2번과 3번이 연결되어있다고 가정할수있습니다. 여행가자 문제풀이 ## # 두 원소가 속한 집합을 합치기 ## 부모는 속한집합중에 제일 작은값을 가져야함 def union(x,y): x=find_union(x) y=find_union(y) if x 더보기
투 포인터 알고리즘 1. 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가르키도록 한다. 2. 현재 부분 합이 M과 같다면, 카운트를 한다. 3. 현재 부분 합이 M보다 작다면 end를 1 증가시킨다 4. 현재 부분 합이 M보다 크거나 같다면 start를 1증가시킨다. 5. 모든경우를 확인할때까지 2부터 4번까지의 과정을 반복한다. [초기 단계] : 시작점과 끝점이 첫번째 원소의 인덱스를 가리키도록 합니다. 현재의 부분 합은 1. 현재 카운트 : 0 [Step 1] : 이전 단계에서의 부분합이 1 -> end를 증가시킵니다. 현재의 부분 합 : 3 현재 카운트 : 0 [Step 2] : 부분합이 3 -> end를 증가시킵니다. 현재의 부분 합 : 6 현재 카운트 : 0 [Step 3] : 부분합 6 -.. 더보기
라이브러리를 이용한 순열(수열추측하기) 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. 3 1 2 4 4 3 6 7 9 16 N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. ▣ 입력설명 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다. ▣ 출력설명 첫째 줄에 삼각형에서 가장 위에 들어갈.. 더보기
LIS(Longest Increasing Subsequence) 알고리즘 가장 긴 증가하는 부분 수열 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 122803 48389 31863 37.364% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 출력 첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. 예제 입력 1 복사 6 10 20 10 30 20 50 .. 더보기
[python3] 1316번 그룹단어체커 (구현) 그룹 단어 체커 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 113508 58707 48654 52.090% 문제 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N이 들어온다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 단어가 들어온다. 단어는 알파벳 소문자로만 되어있고 중복되지 않으며,.. 더보기
Heapq란 무엇인가 최대힙과 최소힙. heapq는 이진트리형태로 구성이 되어있다. heapq.heappush를하게되면 파이썬은 자동으로 최소힙이 구성되게된다. 즉 heapq에 넣었다 빼기만해도 오름차순 정렬이 된다는말이다. heapq를 활용한 문제풀이 N번째 큰 수 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 12 MB (하단 참고) 18632 7530 5351 39.552% 문제 N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자. 12 7 9 15 5 13 8 11 19 6 21 10 26 31 16 48 14 28 35 25 52 20 32 41 49 이러한 표가 주어졌을 때, N번째 큰 수를 .. 더보기

티스토리툴바