본문 바로가기

알고리즘146

Programmers 2 레벨 테스트 1 Programmers 2 레벨 테스트 1 문제 숫자가 담겨있는 배열이 주어진다. 그 배열 안에 있는 숫자들을 나열하여, 제일 큰 숫자를 만드는 것이다. [6, 20, 4] 가 있다면 6420을 출력하는 것 각 숫자는 1부터 1000까지의 숫자다. 즉 999가 제일 큰 숫자. 문제 풀이 배열 안에 있는 숫자들을 문자열로 만든다 그렇게 하면 숫자의 제일 앞 자리 숫자를 기준으로 순차적으로 배열을 해준다 각 문자열을 4번을 반복시키고, 그 중 4자리를 가지고 온다. 4자리는 1부터 10000까지의 숫자가 주어져서 최대 4자리가 되는 것 4번 반복하는 이유는 (람다를 사용한다) [6, 21, 2, 8] 이 주어졌을 때 먼저 정렬을 하면 [8, 6, 21, 2] 가 된다 제일 크게 만드려면 86221이어야 한다 .. 2023. 2. 7.
[Python] 백준 1260 DFS와 BFS 🧑‍💻 [Python] 백준 1260 DFS와 BFS Silver 2 - DFS / BFS DFS는 깊이 우선이다. 먼저 한 쪽을 선택해서, 탐색을 하는 것이다 BFS는 넓이 우선 탐색이다. 즉 부모 노드에 여러 자식 노드가 있으면, 바로 연결되어 있는 자식 노드들 부터 탐색을 한다 문제풀이 함수를 사용했다 리스트를 만들고, 리스트 안에 있는 요소들을 오름차순으로 정렬했다 (만약 길이 2개 이상이면, 숫자가 작은 곳부터 탐색을 한다) DFS 같은 경우, 재귀를 이용한다 즉 DFS는 만약 방문을 안 한 노드가 있으면, 그 노드를 다시 DFS(V)를 한다 방문을 했으면 for문은 끝까지 돌아갈 것이다. 즉 for문이 끝났다는 것은, 이미 모든 노드를 한번씩 탐색을 했다는 것이다 BFS 같은 경우 queue를.. 2023. 2. 6.
[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.
[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.

티스토리툴바