본문 바로가기

파이썬47

[알고리즘/Python] 이진 탐색(Binary Search) 너무 편향된 알고리즘 문제만 푼 나를 반성하며 이진 탐색에 대하여 정리해보려고 한다. 1. 이진 탐색이란? 검색 범위를 줄여나가며 특정 데이터를 검색하는 알고리즘 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다. 2. 동작 방식 배열의 중간 값을 가져온다. 중간 값과 검색 값을 비교한다. 중간 값이 검색 값과 같으면 종료 (mid = key) 중간 값이 검색 값보다 크다면 중간 값 기준 오른쪽 구간을 대상으로 탐색 (mid < key) 중간 값이 검색 값보다 작으면 중간 값 기준 왼쪽 구.. 2023. 1. 28.
[프로그래머스/파이썬] 디펜스 게임 https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 : 준호는 디펜스 게임을 진행한다. 병사는 n명 가지고 있고, 적을 마주할 때 마다 적의 수만큼 아군의 수도 줄어든다. 단, '무적권'이라는 스킬을 사용할 시 병사의 소모없이 한 라운드의 공격을 막을 수 있다. 무적권을 적절히 사용하여 준호가 몇 라운드까지 버틸 수 있는지 출력하라. level 2문제길래 가볍게 접근했다가 애를 먹었다. 이진 탐색 + 파라메트릭 서치 + 힙 문제는 사실.. 2023. 1. 27.
[프로그래머스/파이썬] 기사단원의 무기 https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 요약 : 기사단의 각 기사는 번호를 가진다. 그 번호의 약수 개수만큼의 공격력을 가진 무기를 구매할 수있다. 그러나 이웃나라와 협약으로 인하여 공격력이 제한 수치 이상이 되게 되면 협약기관에서 정한 공격력을 가지는 무기를 구매해야한다. 무기를 만들 때 무기의 공격력 1당 1kg의 철을 사용한다. 무기를 모두 만들기 위해 필요한 철의 무게를 구하라 풀이 ) 처음에 그냥 무작정 약수를 구하게 .. 2023. 1. 16.
[백준/파이썬] 2091 : 동전 https://www.acmicpc.net/problem/2091 2091번: 동전 첫째 줄에 답을 출력한다. cent의 수, nickel의 수, dime의 수, quarter의 수를 출력한다. 불가능한 경우에는 0을 네 개 출력한다. www.acmicpc.net 문제 요약 : 1,5,10,25 동전이 있다. 각 동전의 개수는 정해져 있고, 동전 개수 내로 X원을 만드는 가장 큰 경우의 수를 출력하라. 동전 시리즈 풀겠다고 했다가 동전한테 털림 18번의 시도 끝에 성공한거라 어떻게 성공한건지 기록해놓으려고 한다,, 어디가 틀렸는지 반례라도 알고 싶어서 검색을 많이 했는데, 파이썬으로 2091번을 푼 경우가 거의 없었고 질문도 답해주신 분들이 없었다. 그나마 검색에서 나오는 경우는 DFS였는데, 나는 DF.. 2022. 10. 25.
[백준/파이썬] 2294 : 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 문제 요약 : n가지 동전으로 k원을 만든다. 사용한 동전의 최소의 개수를 출력하고 불가능할 경우 -1을 출력한다. 어쩌다보니 동전문제 도장깨기 중이다..ㅋㅋ 이렇게 된김에 계속 동전 시리즈를 풀어보겠음 시도 1 ) 앞서 동전문제를 많이 풀어서 그런지 금방 규칙이 눈에 보였다. 그냥 동전 1문제와 큰 틀은 같다. 동전 1 풀이는 아래와 같음 https://eunsun.. 2022. 10. 18.

티스토리툴바