본문 바로가기
반응형

Algorithm296

[Python][이코테] 이진 탐색 이진 탐색 Binary Search 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 찾는 방법이다. 이진 탐색은 변수 3개를 사용한다. 시작점, 끝점 그리고 중간점 예를들어 0 2 4 6 8 10 12 14 16 18 의 배열에서 4를 찾는다고 가정하자 0 2 4 6 8 10 12 14 16 18 우선 시작점은 [0], 끝점은 [9] 중간점은 9/2 = 4.5 에서 소수점은 버려서 [4]로 지정한다. [0] = 0, [9] = 18, [4] = 8 [4]의 데이터와 찾으려는 값 4를 비교한다. [4]의 값이 더 크므로 중간점 이후의 값은 확인할 필요.. 2022. 10. 13.
[Python] 백준 2869번 - 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽이가 나무 막대를 모두 올라가는데 며칠이 걸리는지 출력한다. 처음에는 문제를 보자마자 스택으로 풀면되나? 스택이니 재귀를 사용해야겠지? 라고 생각했으나 문제의 조건에 길이가 최대 1,000,000,000 까지인걸 본 순간 재귀나 기타 반복문은 버리고 수학.. 2022. 10. 12.
[Python][이코테] 두 배열의 원소 교체 동빈이는 두 개의 배열 A와 B를 가지고 있다. 두 배열은 N개의 원소로 구성되어 있으며, 배열의 원소는 모두 자연수이다. 동빈이는 최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 것을 말한다. 동빈이의 최종 목표는 배열 A의 모든 원소의 합이 최대가 되도록 하는것이며, 여러분은 동빈이를 도와야 한다. 입력 조건 첫 번째 줄에 N, K가 공백으로 구분되어 입력된다. (1 ≤ N ≤ 100,000, 0 ≤ K ≤ N) 두 번째 줄에 배열 A의 원소들이 공백으로 구분되어 입력된다. 모든 원소는 10,000,000보다 작은 자연수이다. 세 번째 줄에 배열 B의 원소들이 공백으로 구분되어 입력된다. 모든 원.. 2022. 10. 9.
[Python][이코테] 성적이 낮은 순서로 학생 출력하기 입력 조건 첫 번째 줄에 학생의 수 N이 입력된다. (1 ≤ N ≤ 100000) 두 번째 줄부터 N + 1번째 줄에는 학생의 이름을 나타내는 문자열 A와 학생의 성적을 나타내는 정수 B가 공백으로 구분되어 입력된다. 문자열 A의 길이와 학생의 성적은 100 이하의 자연수이다. 출력 조건 모든 학생의 이름을 성적이 낮은 순서대로 출력한다. 성적이 동일한 학생들의 순서는 자유롭게 출력해도 괜찮다. 입력 예시 2 홍길동 95 이순신 77 출력 예시 이순신 홍길동 내 코드 n = int(input()) data = {} for _ in range(n): input_data = input().split() data[input_data[0]] = int(input_data[1]) sorted_data = sort.. 2022. 10. 8.
반응형

티스토리툴바