https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 예제를 손으로 풀어봤지만,, 아직도 왜 70이 나오는 지 모르겠다,,,ㅋㅋㅋ 코드로 짜서 풀면 70이 나오긴 하는데 말이지,, 휴게소가 없는 구간의 최댓값을 low = 1 , high = L 로 두고 이분탐색을 통해 값을 찾아갔다. 두 지점 사이의 간격이 mid보다 크면 그 사이에 휴게소를 mid보다 작게 될 만큼 세워주고 m에 개수를 더해준다. 그리고 m이 M보다 같거..
알고리즘💻/이분탐색&정렬&분할정복
https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net 1. 입력을 받으면서 손질을 해준다. 이때 K보다 같거나 작은 길이는 그냥 버린다. 2. P의 길이를 low = 1, high = 10**9 로 하여 이분탐색한다. import sys input = sys.stdin.readline N, K, M = map(int, input().split()) length = [] for _ in range(N): L ..
https://www.acmicpc.net/problem/1074 1074번: Z 한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. 만약, N > 1이 라서 www.acmicpc.net 전체 사각형을 네 개의 작은 사각형으로 계속 나누어나가면서 답을 더해가는 방법으로 풀었다. 각각의 작은 네 개의 작은 사각형을 Z 방향으로 0, 1, 2, 3 이라고 생각하고 위치에 따라 그 사각형 안의 개수에 곱해서 정답에 계속 더해준다. 이전에 한 번 풀었던 문제인데, 이전에 푼 방법이 시간이 조금 더 절약되더라. import sys input = sys.stdin.readline N,..
https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 처음엔 문제에 나와있는 코드를 그대로 구현해봤는데, 시간초과가 났다. 버블정렬은 O(n^2)의 시간복잡도를 가지기 때문이다. import sys N = int(sys.stdin.readline()) A = [-1] for _ in range(N): A.append(int(sys.stdin.readline())) for i in range(1, N+2): change = Fa..
https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 정렬의 중간 과정을 구하는 문제이다. 주어진 숫자의 수가 N, 현재 정렬을 하고 있는 사람이 k라고 했을 때 정렬되는 단위는 N//k이다. 따라서 N//k만큼의 길이로 배열을 나누어서 정렬한 후 출력해주었다. import sys N = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split()..
https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net 삼각형의 세 변의 길이를 a, b, c라고 하고 그 중에 제일 긴 변의 길이가 c 라고 할 때 a+b > c 라는 조건을 만족해야 삼각형이 성립할 수 있다. 입력받은 빨대의 길이를 오름차순으로 정렬하고 제일 긴 빨대(arr[-1])부터 c라고 했을 때 가능한 모든 경우를 탐색해봤는데.. 당연히 시간초과가 났다. 중간에 break문을 넣어도 시간초과가 났다. 다시 한 번 생각..
https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 조건에 맞게 정렬을 하면 된다. 파이썬에서 조건 여러개를 이용하여 정렬을 할 때는 sort메소드와 lambda를 이용하면 된다. 내림차순으로 정렬할 때는 조건에 - 를 붙여주면 된다. import sys N = int(sys.stdin.readline()) arr = [] for _ in range(N): name, k, e, m = sys.stdin.readline().sp..
www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 문제풀이: set을 이용하여 중복된 수를 제거한 후, 오름차순으로 정렬하였다. 그리고 처음에 주어진 배열의 원소를 새로 정렬한 배열에서 찾고 그 인덱스를 정답 배열에 추가하였다. pypy로 통과하였다. import sys N = int(sys.stdin.readline()) X = list(map(int, sys.stdin.readline().split())) ..
www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 아이디어: 이분탐색 이분탐색을 이용하여 푸면 된다. 하지만, 구현 과정에서 그냥 mid 값을 출력하니 틀렸다. 조금만 생각해보면 당연한 것이다. 조건에 맞을 경우에만 답을 업데이트해주고 그 답을 출력해야 한다. 그런데 또 파이썬으로 제출하면 시간초과가 떠서 pypy로 제출했는데, 질문을 보니 시간을 단축할 수 있는 방법을 생각해보라고 해서 이왕 정렬하는 거 배열의 끝에서 ..
www.acmicpc.net/problem/3758 3758번: KCPC 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 www.acmicpc.net 아이디어: #정렬 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 따라서 정렬 조건은 1. 최종점수 2. 풀이를 제출한 횟수 3. 마지막 제출 시간 이다. 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 한 문제에 대한 풀이를 여러번 제출할 수 있으며 그 중 최고 점수가 그 문제의 최종 점수이다. 입력..
