본문 바로가기

알고리즘107

[Python] 백준 1083 소트 🧑‍💻 [Python] 백준 1083 소트 Gold 5 - 그리디 문제풀이 최대한 제일 큰 숫자가 앞으로 와야 한다 숫자의 움직임에 제한이 있다 일단 swap만큼의 숫자들을 슬라이스를 통해 슬라이스 안에 제일 큰 숫자를 가지고 온다 그리고 i까지, 뒤로 그 큰 숫자를 앞으로 가지고 온다 이것을 swap이 0이 될때까지 반복을 한다 코드 N = int(input()) array = list(map(int, input().split())) swap = int(input()) for i in range(N): max_num = max(array[i : i + swap + 1]) max_num_index = array.index(max_num) for j in range(max_num_index, i, -1):.. 2023. 2. 1.
[Python] 백준 12931 두 배 더하기 🧑‍💻 [Python] 백준 12931 두 배 더하기 Gold 5 - 그리디 제일 중요하게 생각해야 하는 것은 B에서 배열 A를 만드는 것이다 즉 B에 있는 원소들을 다 0으로 만들어야 하는 것 즉 B에서 값 하나씩 1을 빼는 것 그리고 B에서 모든 값을 2로 나눠서 0을 만드는 것으로 반대로 생각하면 된다 문제풀이 최소를 구하는 것이니깐 모든 값을 2로 나누는 것을 먼저 생각한다 for문을 통해, 모든 숫자가 숫자 % 2 == 0 로 떨어지면, count에 1을 더한다 그리고 for문을 순회할 때에, 각 숫자들을 2로 나눈 것을 temp 리스트에 넣는다 그리고 만약에 for문을 아무 문제 없이 순회를 했다면, temp리스트를 B로 업데이트 한다 반대로 위에서 for문을 통해 순회를 했는데, 홀수를 구한.. 2023. 2. 1.
[Python] 백준 2212 센서 feat. Shark_상어 https://wlgustlra.tistory.com/ 🧑‍💻 [Python] 백준 2212 센서 Gold 5 - 그리디 문제풀이 센서들을 내림차순으로 정렬을 한다 그리고 센서들 사이의 거리를 계산해서 새로운 리스트에 넣는다 그 리스트를 오름차순으로 정렬을 하고, 세울 수 있는 집중국에서 1을 뺀만큼, 리스트에서 거리를 빼준다 거리를 빼면, 해당 센서는, 자기 자신만의 집중국을 가지는 것이 코드 censor_num = int(input()) center_num = int(input()) censors = list(map(int, input().split())) censors.sort(reverse=True) # 설치할 수 있는 집중국이 센서보다 많거나, 같으면, # 각 센서에게 집중국을 설치하면 된다 i.. 2023. 1. 29.
[Python] 백준 1783 병든 나이트 🧑‍💻 [Python] 백준 1783 병든 나이트 Silver 3 - 그리디 나이트는 무조건 오른쪽으로 움직이는 것을 핵심적으로 생각하면 된다 즉 if문에는 1번부터 4번까지 한번씩 사용을 못 하는 경우들을 넣는다 문제풀이 위의 내용을 if문을 통해 해결을 하면 된다 코드 import math N, M = map(int, input().split()) if N == 1: print(1) elif N == 2: print(min(4, int(math.ceil(M/2)))) elif M 2023. 1. 29.
[Python] 백준 1026 보물 🧑‍💻 [Python] 백준 1026 보물 Silver 4 - 그리디 A는 재배열이 가능하고, B는 재배열을 하면 안 된다고 하지만, 둘 다 정렬을 해야 한다 A는 오름차 순으로, B는 내림차 순으로 정렬을 해야 한다 문제풀이 A는 오름차순으로 B는 내림차순으로 정렬을 한다 즉 나중에 같은 인덱스끼리 곱할 때, A의 작은 수는 B의 큰 수와 곱한다 그리고 그것을 나중에 다 더하면 최소 값이 된다 코드 N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort() B.sort(key=lambda x: -x) answer = 0 for i in range(N): answer += A[i] * B[.. 2023. 1. 27.
Udemy - Javascript - Merge Sort Udemy - Javascript - Merge Sort 정렬이란? 데이터가 있으면, 데이터를 숫자 또는 단어별로 오름차순 또는 내림차순으로 나열하는 것이다 정렬을 하는 방법은 다양하다. 정렬하는 방법마다, 정렬을 하는 시간은 다르다 버블, 선택, 삽입 정렬들은 숫자가 계속 늘어날 수록, 속도가 느려진다 반대로 합병 정렬, 퀵 정렬, 지수 정렬은 위의 3개보다 더 빠르다 합병 정렬 두 배열 합병하기 function mergeSort(array1, array2) { let i = 0 let j = 0 let newArray = [] while (i < array1.length && j < array2.length) { if (array1[i] < array2[j]) { newArray.push(array1.. 2023. 1. 27.
[Python] 백준 1339 단어 수학 🧑‍💻 [Python] 백준 1339 단어 수학 Gold 4 - 그리디 문자열들이 주어진다 문자열들의 알파벳에 숫자를 배정해서, 더해서 최대 수를 만드는 것이다 A에 9를 배정했으면, 모든 문자열에 A가 들어가 있으면, 그 A들은 9이다 문제풀이 문자열을 어떻게 딕셔너리에 넣어서, 어떻게 숫자를 배정할지 많이 고민을 했다 알파벳들이 십의 몇번째 자리인지 찾고, 그 자리에 따라서 내림차순으로 9부터 배정하는 것이다 각 단어들의 알파벳들을 딕셔너리에 넣는다 여기서 10 ** (times - 1)을 하여서, 해당 알파벳이 몇 번째 자리인지 value로 넣는다 그리고 다 구했으면 딕셔너리의 값들을 리스트로 변환해서, 내림차순으로 정렬을 한다 정렬한 리스트를 순회하면서 9부터 내려가면서 곱해주고, result에 .. 2023. 1. 26.
[Python] 백준 1439 뒤집기 🧑‍💻 [Python] 백준 1439 뒤집기 Gold 5 - 그리디 문자열은 0과 1 밖에 없다 연속된 숫자들을 뒤집는 것이고, 최소한으로 뒤집는 것이 목표 즉 0000011111000001100 은 01010 과 똑같다 문제풀이 (처음 풀이, 틀림) one , zero라는 변수를 만들어 0으로 초기화 시켰다 문자열을 순회하며, 문자열이 바뀔 때 마다, 1이면 one에 1을 더하고, 0이면 zero에 1을 더했다 경우의 수 one이 0이고, zero가 0일 때에, 숫자를 뒤집지 않아도 되서 0을 출력 one만 0이면 zero 값인 1을 출력 zero만 0이면, one 값인 1을 출력 zero와 one이 0이 아니면, 둘 중에 작은 것을 출력 문제풀이 (두번째) 000001110000110110 은 010.. 2023. 1. 25.
[Python] 백준 1138 한 줄로 서기 🧑‍💻 [Python] 백준 1138 한 줄로 서기 Gold 4 - 그리디 입력값은 서있는 사람의 기준으로 왼쪽에, 자신보다 키가 큰 사람의 숫자를 의미한다 예) 키가 1인 사람 왼쪽에는 자신보다 큰 사람이 6명이 있다 문제풀이 result의 0의 개수를 세면서, index + 1 즉 키를 넣어주면 된다 코드 N = int(input()) result = [0] * N for index, num in enumerate(list(map(int, input().split()))): cnt = 0 i = 0 while True: if result[i] == 0 and cnt == num: result[i] = index + 1 break elif result[i] == 0: cnt += 1 i += 1 pri.. 2023. 1. 25.

티스토리툴바