[Python] 백준 알고리즘 2805번 : 나무 자르기
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 👩💻문제 이해 항상 그렇듯 이분탐색 알고리즘에서는 무엇을 변수로 둘지와 조건을 어떻게 줄지가 가장 중요하다. (조건) 위 문제에서는 가지고 가려 하는 나무의 길이가 M으로 정해져 있기 때문에 이걸 조건으로 두면 된다. 즉, 주어진 배열 각각의 원소들을 구하고자 하는 값(target)으로 뺀 값의 합이 M이 되는 것이 조건이다. 그리고 이 때 절단기 높이의 ..
[Python] 백준 알고리즘 2776번 : 암기왕
https://www.acmicpc.net/problem/2776 2776번: 암기왕 연종이는 엄청난 기억력을 가지고 있다. 그래서 하루 동안 본 정수들을 모두 기억 할 수 있다. 하지만 이를 믿을 수 없는 동규는 그의 기억력을 시험해 보기로 한다. 동규는 연종을 따라 다니며, www.acmicpc.net 👩💻문제 이해 이해하기에 어려운 문제는 아니다. N개의 정수가 주어진 '수첩1'의 배열을 정렬한 후 '수첩2'에 들어있는 각각의 정수들을 이분탐색 알고리즘으로 '수첩1'에도 있는지 없는지를 판단하면 된다. 👩💻반복문을 사용해 이분탐색 알고리즘 구현 (함수 별도 구현) : 성공🌈 def binary(arr, target): start = 0 end = len(arr) - 1 while start
[Python] 백준 알고리즘 1654번 : 랜선 자르기
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 👩💻문제 이해 만들 수 있는 랜선의 길이 (target) 이 [1,2,3, ..., 주어진 랜선의 최대값] 배열을 이분탐색을 이용해 (주어진 랜선 길이 // 배열의 중간값)의 합이 K와 같아질 때 까지 반복하면 된다. 정렬된 배열에서 각각의 (주어진 랜선 길이 // start와 end의 중간값(mid)) 의 합(= cnt)이 k와 같아질 때까지 이분탐색 알고리즘을 반..
[Algorithm] 이분 탐색 / 이진 탐색 (Binary Search) 알고리즘
🌵이분 탐색(Binary Search) 이란? - 정렬되어 있는 리스트(배열)에서 탐색 범위를 절반씩 좁혀가며 원하는 값(target)을 탐색하는 방법 - 이 때 리스트(배열)는 항상 정렬되어 있어야 한다 시간 복잡도 : O(log n) 🌵문제 해결 방법 이분 탐색 알고리즘은 변수 3개 (start, mid, end)를 사용해 값을 탐색 간단하게 말하면 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이분 탐색의 과정 변수 이름에서도 알 수 있듯, start의 초기 값은 리스트(배열) 시작 위치 (0) mid 는 start와 end의 중간 지점 ((start + end) // 2) end 는 리스트(배열) 마지막 위치 (len(list) - 1) 1. 리스트(..
[Algorithm] 해시를 사용한 집합(set)과 맵(map)
🌵 Hash Function (해시 함수) 또는 Hash Algorithm (해시 알고리즘) 임의의 길이의 데이터(key)를 고정된 길이의 데이터(hash)로 매핑하는 함수 이 과정을 hashing이라 한다. 즉, 해시 함수 : key (Input) -> Hash (Output) 이때의 Hash는 저장 위치가 된다. 🌵 Hash Table (해시 테이블) 또는 Hash Map (해시 맵) 해시값을 주소 또는 색인 삼아 데이터(value)를 key와 함께 저장하는 자료구조이다. 파이썬의 딕셔너리(dictionary) 자료형은 해시 테이블로 구현되어 있다. 장점 해시 테이블은 key-value가 1:1로 매핑되어 있기 때문에 삽입, 삭제, 검색의 과정에서 모두 평균적으로 O(1)의 시간 복잡도를 가지고 있다..
[Python] ⭐️백준 알고리즘 1018번 : 체스판 다시 칠하기
https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 👩💻문제 이해 브루트포스 알고리즘을 이용해 주어진 배열을 모두 돌며 다시 칠해야하는 부분을 카운트하고 최소값을 찾는다. 맨 위 왼쪽 체스판이 흰색인 경우, 검은색인 경우로 나누어 다시 칠해야 하는 수를 확인 해야한다. 👩💻반복문을 사용해 모든 경우 체크 : 성공🌈 n, m=map(int,input().split()) # n행, m열 arr = [] cnt=[] for i in range..