본문 바로가기

알고리즘107

[Python] 백준 6068 시간 관리하기 🧑‍💻 [Python] 백준 6068 시간 관리하기 Gold 5 - 정렬 하루는 0 시간부터 시작한다 농부가 주어진 일을 끝내기 위해, 얼마나 더 잘 수 있는지 시간을 구하는 것이다 하루를 시작하는 시간을 구하는 것이기 때문에, 시작하는 시간 기준으로 문제를 해결하면 된다 문제 풀이 입력을 받을 때, 일을 끝내기 위해 필요한 시간과, 일을 끝내야 하는 시간이 주어진다 여기서 일을 끝내야 하는 시간 기준으로 오름차순으로 정렬을 한다 hour 같은 경우, 하루를 시작하는 기준이 0 이니깐, 0부터 시작을 한다 while문을 통해, 일을 끝내야 하는 시간 안에 모든 일들을 할 수 있으면 1씩 더해준다 time에 일을 끝내기 위해 필요한 시간을 계속 더해준다 만약 여기서 time 이 일을 끝내야 하는 시간보다 .. 2023. 1. 9.
[Python] 백준 1946 신입 사원 🧑‍💻 [Python] 백준 1946 신입 사원 Silver 1 - 정렬 서류 성적과 면접 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않으면 선발을 한다 즉 서류 성적, 면접 성적 모두, 다른 지원자보다 낮으면 떨어지는 것이다 문제 풀이 먼저 서류 성적 기준으로 정렬을 한다 그리고 면접 성적들을 비교를 한다 제일 처음 기준을 서류 면접에서 1등 한 사람 기준으로 간다 서류 면접 1등 사람 기준(A)으로 면접 성적이 더 우수하다면, 그 사람도 (B) 신입 사원으로 뽑힐 수 있다 그 다음부터는 B의 면접 성적 기준으로 비교를 한다. (이렇게 계속 면접 성적 기준을 바꿔주면서 비교를 하며 뽑힐 수 있는 신입 사원의 수를 구한다) 정렬한 기준, 제일 앞에 있는 사람은 무조건 신입사원으로 뽑힌다. 서류가 1.. 2023. 1. 9.
[Python] 백준 1202 보석 도둑 🧑‍💻 백준 1202 보석 도둑 Gold 2 - 정렬, heapq 각 보석들의 무게와 가치가 주어지면서, 각 가방에 들어갈 수 있는 보석의 최대 무게가 주어진다 각 가방에는 보석 하나 밖에 못 들어간다 즉, 가방에 들어갈 수 있는 보석들 중, 최대의 보석 가치를 가방에 넣는 것이다 문제 풀이 가방에 들어갈 수 있는 보석들 중, 최대의 보석 가치를 가방에 넣는 것 즉 보석들을 각 보석들의 무게 위주로 오름차순으로 정렬을 한다 그리고 가방에 들어갈 수 있는 보석들을 구한다 그 가방에 들어갈 수 있는 보석들 중, 제일 가치가 높은 보석을 가방에 넣으면 된다 heapq 힙은 이진 트리를 사용하면서 우선순위 큐를 구해준다. O(logN) 코드 결과 코드 import heapq N, K = map(int, inpu.. 2023. 1. 6.
[Python] 백준 1253 - 좋다 🧑‍💻 백준 1253 - 좋다 Gold 4 - 정렬 리스트 안에 있는 어떤 수를, 리스트 안에 있는 두 수의 합으로 나타낼 수 있는 수의 개수를 구하는 것이다 여기서 놓치지 말아야 할 것은, 숫자의 값이 같아도 위치가 다르면 다른 숫자로 간주한다 예시) 원래 그냥 리스트를 정렬을 한 후, 투 포인터를 이용해서 더해서, 더한 숫자가 리스트에 있는지 확인만 하면 되는 줄 알았다 그렇게 되면, 다른 위치에 있어도, 같은 값의 숫자가 카운팅이 잘 안 될 수 있다 그래서 숫자 하나하나 씩 빼고, 그 외의 숫자들을 투 포인터를 사용해서 그 뺐던 숫자와 일치하는지 더해주면 된다 문제 풀이 위 각 변수들의 설명 i : for문을 통해서 정렬된 리스트에 있는 값들을 가지고 온다 (range를 가지고 오면 됨) temp .. 2023. 1. 5.
[Python] 백준 11497 - 통나무 건너뛰기 🧑‍💻 백준 11497 - 통나무 건너뛰기 Silver 1 - 정렬 인접한 통나무 높이의 차를 최소화 하는 문제다 여기서 제일 중요한 것은 통나무를 원형으로 세워 놓는 것이라서, 제일 앞과 제일 뒤에 있는 숫자도 높이의 차에 포함을 해야 한다 즉 단순히 정렬을 하게 된다면, 제일 앞에 있는 숫자와 제일 뒤에 있는 숫자의 차가 제일 커서, 답을 구할 수 없다 예시) 문제 풀이 먼저 정렬을 해야 하긴 한다 (오름차순으로 정렬을 했다) For문을 순회할 때 Index가 짝수 일 때 현재 index에서 빼기를 한다 index를 빼는 것은 0으로 시작해서, 뺄 때마다 -1 씩 누적을 시킨다 For문을 순회할 때 Index가 홀수 일 때 현재 index에서 같이 빼기를 한다 index를 빼는 것은 -2로 시작해서,.. 2023. 1. 4.
[Python] 백준 1744 - 수 묶기 🧑‍💻 백준 1744 - 수 묶기 GOLD 4 주어진 숫자들을 더해서 제일 큰 수를 만드는 것 숫자들을 2개씩 묶어서 곱할 수 있다 즉 큰 숫자들끼리 묶어서 곱하면, 합을 최대로 만들 수 있다 문제 풀이 주어진 숫자들을 리스트에 넣을 때에, 양수 리스트와 음수 리스트에 따로따로 넣는다 즉 리스트가 2개다. 여기서 0 은 음수 리스트에 넣는다 양수 리스트는 내림차순으로 / 음수 리스트는 오른차순으로 정렬을 한다 deque를 사용한다 이유는 제일 앞에 있는 숫자들을 pop을 해야하는데, pop은 리스트에 있는 제일 마지막 숫자를 꺼낸다 첫번째 숫자를 빠른 속도록 꺼내기 위해서 popleft를 사용해야하는데, deque를 적용해야 사용할 수 있음 while문을 통해 양수 리스트와 음수 리스트에 있는 숫자 꺼내.. 2023. 1. 1.
[Python] 백준 5052 - 전화번호 목록 🧑‍💻 백준 5052 - 전화번호 목록 GOLD 4 - 정렬 접두어가 있으면 NO를 출력하고 없으면 YES를 출력하는 문제 여기서 접두어(Prefix)란? 어떤 단어 또는 숫자 앞에 새로운 단어 또는 숫자가 되는 것 예시) 문제 풀이 숫자들을 integer로 입력을 받아오는 것이 아닌, 문자열로 불러온다 숫자의 원래 크기가 중요한 것이 아닌, 문자열에 있는 앞의 숫자들이 문자열을 비교할 때에 일치가 하는지가 중요하다! 숫자들을 정렬을 시킨다 문제의 예시를 정렬하게 된다면 '911', '97625999', '91125426' ▶️ ['911', '91125426', '97625999'] '113', '12340', '123440', '12345', '98346' ▶️ ['113', '12340', '123.. 2022. 12. 29.
Algorithm 📋Algorithm - 자료구조 ✔️ 알고리즘이란 Input → Algorithm → Output 문제란 특정한 input을 넣어, 원하는 output이 나오도록 하는 것 알고리즘은 어떤 문제를 해결하기 위해 정해진 절차나 행동이다 ✔️ 코딩 테스트란 기업에서 지원자 대상으로 코딩을 통한 알고리즘 기반 문제 해결 능력을 평가 문제 해결 능력과 구현력을 보려고 하는 것 문제 해결 능력 : 문제 의도를 정확히 파악하고, 적절한 해결 방법을 적용하는가? 구현력 : 해결 방법 프로그래밍을 통해 능숙하게 구현할 수 있는가? 코딩 테스트 : 문제파악 → 해결 방법 구상 → 정답 구현 현업 : 비즈니스 문제 → 해결 방법 구성 → 수정 및 구현 완벽히 똑같지는 않지만, 어느 수준까지는 대략적으로 판단할 수 있다 ✔️.. 2022. 12. 28.

티스토리툴바