본문 바로가기

Algorithm/Binary Search9

[프로그래머스] 순위 검색 (Python 파이썬) programmers.co.kr/learn/courses/30/lessons/72412 5: queryl[j].remove("and") for i in range(len(infol)): for j in range(len(queryl)): flag = 0 for k in range(4): if infol[i][k] != queryl[j][k]: if queryl[j][k] != '-': flag = 1 break if flag == 0: if int(infol[i][4]) >= int(queryl[j][4]): answer[j] += 1 return answer 효율성을 통과하기 위해 사용한 방법은, 딕셔너리(자바의 hash와 비슷한 파이썬의 자료구조), 이분탐색(BinarySearch)를 이용했습니다. .. 2021. 4. 24.
[백준] 12015번 가장 긴 증가하는 부분 수열 2 (Python 파이썬) www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제이다. 예를 들어, A = {10, 20, 10, 30, 20, 50} 인 경우 가장 긴 증가하는 부분 수열은 {10, 20, 30, 50} 이다. 풀이 과정 먼저, 풀이과정 두가지를 이용할 수 있는데, 하나는 이진탐색을 직접 구현하여 수열이 들어갈 자리를 찾는 방법이고 다른 하나는 내장 모듈인 bisect를 이용한 방법이다. 먼저 풀.. 2021. 4. 4.
[백준] 1300번 K번째 수 (Python 파이썬) www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 문제 설명 이 문제에서 A라는 배열의 각 칸에는 다음과 같이 자기 인덱스의 곱을 담고있다. ( 즉 N[2][3] = 2*3 ) 1 2 3 2 4 6 3 6 9 이러한 배열을 B라는 1차원 배열에 오름차순으로 나타내었을 때, k번째 인덱스에는 어떤 수가 있는지를 출력하는 문제이다. 풀이 과정 처음에는 N*N크기의 1차원 배열을 만들어 for문을 이용해 1*1부터 N*N까지의 수를 모.. 2021. 4. 4.
[백준] 10816번 숫자 카드 2 (Python 파이썬) www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 지난번에 풀었던 10815번 숫자카드 1 문제의 상위 호환 문제이다. 숫자카드1 문제의 경우 이진탐색을 하여 찾고자 하는 숫자가 있으면 단순히 1을 출력하는 문제였다면, 이 문제는 찾고자 하는 숫자의 개수까지 구해야 한다. 처음에는 숫자카드 1처럼 이진탐색을 한 후에 찾은 숫자는 리스트에서 제외를 해주고 다시 이진탐색을 추가하는 식으로 해서 개수를 구했는데, 이진탐색임에도 불구.. 2021. 4. 2.
[백준] 1654번 랜선 자르기 (Python 파이썬) https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 문제는 내가 현재 가지고 있는 서로 다른 길이의 랜선들을 잘라서 동일한 길이의 새로운 랜선을 여러개 만드는 것이다. 내가 가지고 있는 랜선의 개수 K와 새로 만들 랜선의 개수 N을 입력받는다. 예를 들어 K=4, N=11 이라면 4개의 긴 랜선을 잘라 11개의 짧은 랜선을 만드는 것이다. 이 때, 11개를 만들 수 있는 랜선의 최대 길이를 구하면 된다. 즉, 11개를 .. 2021. 1. 27.
[백준] 3020번 개똥벌레 (Python 파이썬) https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 문제에 대한 자세한 설명은 위 링크에 기술 되어있다. 쉽게 풀어쓰자면 동굴의 길이(N)와 높이(H)를 입력받는다. 동굴은 석순과 종유석으로 구성되어 있는데, 석순은 아래에서 자라는 고드름 종유석은 천장에서 나는 고드름이라고 생각하면 된다. 문제에서 동굴의 길이만큼 석순과 종유석의 길이를 입력받는데, 번갈아 가면서 입력받는다. ( 석순과 종유석은 각각 동굴의 길이 1만큼 차지한다) 예를 들어, 1 3 .. 2021. 1. 25.

티스토리툴바