본문 바로가기

알고리즘146

그리디 알고리즘, 원인과 결과 찾기 🧑‍💻 그리디 알고리즘, 원인과 결과 찾기 멀티잇 코딩테스트 러닝클래스'Python 5월반 거스름돈 1, 5, 10, 20, 40 원이라는 동전이 있다 N원을 거슬러 주기 위한 최소의 동전의 개수를 구하는 것 기본적으로 40부터 시작해서, 남은 나머지를 계산해주면 된다 N = int(input()) coin = [40, 20, 10, 5, 1] count = 0 for c in coin: if c temp_end: count += 1 temp_end = end print(count) 2023. 5. 23.
기초 자료구조의 구현과 응용 🧑‍💻 기초 자료구조의 구현과 응용 멀티잇 코딩테스트 러닝클래스'Python 5월반 Stack 말 그대로 stack을 구현하면 된다 stack은 Last In First Out 규칙을 가지고 있다 stack에 들어갈 수 있는 용량이 정해졌다 stack이 이미 꽉 찼을 때에, 값을 넣어야 하면, "Overflow"를 출력 stack에 아무것도 없는데, 값을 빼야 하는 명령어가 실행되면, "Underflow"를 출력한다 N, K = map(int, input().split()) stack = [] for _ in range(N): command = list(input().split()) if command[0] == "push": if len(stack) < K: stack.append(int(command.. 2023. 5. 22.
완전 탐색 🧑‍💻 완전 탐색 멀티잇 코딩테스트 러닝클래스'Python 5월반 제곱 암호 암호를 풀어내는 문제 알파벳, 숫자 순서로 짝을 이뤄서 입력이 주어진다 숫자를 제곱하고, 앞에 알파벳을 제곱번째의 알파벳을 출력하는 것이다 ord와 chr를 사용했다 알파벳을 숫자로 반환하기 위해서 ord를 사용 소문자 같은 경우 a = 97 ~ z = 122 122를 넘어갈 경우를 대비해서 (int(code[i]) ** 2) % 26 를 해주었다 그리고 한번 더 122를 넘어가면 26을 뺐다 마지막으로 숫자를 문자로 반환하기 위해 chr를 사용 N = int(input()) code = list(input()) answer = '' for i in range(N): if i % 2 == 0: temp = code[i] else.. 2023. 5. 11.
시뮬레이션과 창의적 해결 🧑‍💻 시뮬레이션과 창의적 해결 멀티잇 코딩테스트 러닝클래스'Python 5월반 0 커플 숫자로 된 리스트가 주어진다 리스트 안에 숫자의 개수는 짝수이다 음수와 양수가 들어가 있고, 둘의 합이 0이면 커플이다 그 중 합하면 0이 아닌 숫자를 구해야 한다 딕셔너리로 먼저 해결을 했다 key 로는 숫자의 절대값을 넣었고, value에다가 원래 값을 넣었다 만약 절대값이 같으면 value에 값끼리 더했다 (같은 절대값이 나오면, value는 0이 된다) 그리고 마지막에 모든 value 들을 더했다 짝이 없으면, value는 0이 아니라, 다른 숫자일 것 N = int(input()) score = list(map(int, input().split())) temp_dict = {} for s in score: .. 2023. 5. 9.
기초 수학과 구현 🧑‍💻 기초 수학과 구현 멀티잇 코딩테스트 러닝클래스&#39;Python 5월반 최장 맨해튼 거리 |x1 - x2| + |y1 - y2| 의 값이 최장 맨해튼 거리다 (x1, y1) , (x2, y2) 4개의 숫자가 주어지는데, 그 숫자로 만들 수 있는 제일 긴 맨해튼 거리를 만드는 것이다 permutations을 사용하여 주어진 4개의 숫자로 만들 수 있는 수열을 모두 구한다 그리고 맨해튼 거리 공식을 이용하여, 최장 맨해튼 거리를 구하면 된다 from itertools import permutations numbers = list(map(int, input().split())) answer = 0 for i in permutations(numbers, len(numbers)): answer = max.. 2023. 5. 5.
기초 문자열 구현 🧑‍💻 기초 문자열 구현 멀티잇 코딩테스트 러닝클래스'Python 5월반 대소문자 바꾸기 단어가 주어지면, 대문자는 소문자로, 소문자는 대문자로 바꿔서 출력하는 것이다 예) input : JeJoon output : jEjOON N = int(input()) word = input() answer = '' for letter in word: if letter.isupper(): answer += letter.lower() else: answer += letter.upper() print(answer) 간단한 풀이 법 N = int(input()) word = input() print(word.swapcase()) .swapcase() 는 대문자를 소문자로, 소문자를 대문자로 바꿔주는 메서드다 단어 필터 .. 2023. 5. 4.
[Python] 백준 14888 연산자 끼워넣기 🧑‍💻 [Python] 백준 14888 연산자 끼워넣기 Silver 1 - DFS DFS로 풀이를 했다 코드 min_num = 1e9 max_num = -1e9 N = int(input()) numbers = list(map(int, input().split())) operators = list(map(int, input().split())) def dfs(num_depth, total, plus, minus, multiply, divide): global min_num, max_num if num_depth == N: min_num, max_num = min(total, min_num), max(total, max_num) return if plus > 0: dfs(num_depth + 1, total.. 2023. 4. 7.
[Python] 백준 9663 N-Queen 🧑‍💻 [Python] 백준 9663 N-Queen Gold 4 - Backtracking Queen은 위, 아래, 오른쪽, 왼쪽, 대각선, 8 방면 모두 공격을 할 수 있다 N이 주어지고, 체스판 사이즈는 N x N 이고, N 개의 Queen을 넣었을 때 서로 공격할 수 없는 때의 경우의 수를 찾는 것 1차적으로 자세히 보면, 각 행과 열마다, Queen은 하나씩 배치할 수 있다 이 뜻은 굳이 체스판 자체를 안 만들어도 된다 board = [0, 3, 1, 4, 2] 아래 사진을 표현한 리스트 (board의 인덱스가 열/row, board의 값이 행/column) board 안에 있는 값들은 모두 달라야 한다 row (board의 인덱스) column (board의 값) 0 0 1 3 2 1 3 4 4.. 2023. 4. 5.
[Python] 백준 15650 N과 M 2 🧑‍💻 [Python] 백준 15650 N과 M 2 Silver 3 - Backtracking 쉽게 itertools의 combinations를 사용해서 풀 수 있는 문제다 하지만 Backtracking을 공부하고 싶어서 풀었던 문제다 기본적으로 if len(nums) == M: 을 통해서 재귀 함수의 base case를 만든다 안 만들면 무한 루프 리스트 안에 for문을 돌며, 나오는 숫자가 없을 때, 리스트 안에 해당 숫자를 넣고 backtracking(start)를 다시 돈다 여기서 중요한 것은, 수열이 오름차순이어야 한다는 것이다 그래서 재귀함수를 돌릴때마다 backtracking(start + 1)를 해야 한다 그렇게 하면, for문에서 전에서 backtracking() 했던 것보다, 큰 수부터.. 2023. 4. 2.

티스토리툴바