Problem Solving
-
[프로그래머스] 최소직사각형 - Python3Problem Solving/브루트포스 2023. 1. 11. 23:45
문제 설명 여러 명함 사이즈가 주어질 때, 명함을 모두 넣을 수 있는 지갑의 최소 크기를 구하는 문제 알고리즘 분류 - Brute Force 난이도 - Level 1 접근 방법 - Brute Force 명함을 돌릴 수 있기에 가로와 세로 중 큰 값이 중요하다. 따라서 가로와 세로 중 큰 값이 뒤로 올 수 있도록 각 배열을 정렬하고, 배열의 왼쪽 값과 오른쪽 값의 각 최댓값을 구해 곱하였다. 답안 코드 - Brute Force 정확성: 100, 합계: 100.0 / 100.0 def solution(sizes): answer = 0 max_i = 0 max_j = 0 for size in sizes: size = sorted(size) if max_i < size[0]: max_i = size[0] if ..
-
[백준] 1038. 감소하는 수 - Python3Problem Solving 2023. 1. 10. 19:00
문제 설명 9876543210과 같이, 자릿수가 점점 감소하는 N번째 수를 구하는 문제 알고리즘 분류 - 브루트포스, (백트래킹?) 난이도 - 골드5 접근 방법 1. Brute Force 브루트포스로 접근하는 방법이 두 가지 생각났다. 1) 0부터 시작해 실제 정수를 문자열화해서 자릿수를 일일이 비교하는 방법 => 시간 초과 시간복잡도는 구하기가 애매한데... 9876543210까지의 수마다 문자열화 하고(logN) 각 자리수를 비교했으니 당연히 시간 초과가 났다. 2) 가장 큰 자리수의 수보다 작은 수를 뒤에 붙여가는 방법 예 - 0, 1, 10, 2, 20, 21, 210, ... 0~9까지 맨 앞자리를 설정하고, 맨 앞자리수보다 작은 수들의 모든 부분집합을 구해 각 부분집합을 문자열화 -> 역순 정..
-
[백준] 14225. 부분수열의 합 - Python3Problem Solving 2023. 1. 10. 01:36
문제 설명 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 문제 알고리즘 분류 - Brute Force, ... 난이도 - 실버1 접근 방법 1. Brute Force 1) 부분 배열의 원소의 개수가 1~n개일 때의 모든 조합을 구하고, 그에 대한 부분합을 저장한다. 2) 부분합을 저장한 배열에 대해 중복 원소를 제거 및 정렬하고, 부분합 배열과 1~(부분합의 최댓값)의 자연수 수열을 비교하다보면 최초로 다른 값이 답이 된다. (다른 분들 해답 보니까 DP로 실행시간 32ms였나 엄청 효율적으로 푸신 분도 있고, DFS로 200ms대로 푸신 분도 있어서 다른 방법도 시도해볼 예정) 답안 코드 1. Brute Force 메모리: 96212 KB , 시간: 4..
-
[백준] 19071. 외판원 순회2 - C++Problem Solving 2023. 1. 10. 00:47
문제 설명 1번부터 N번까지의 도시가 있을 때, 한 도시에서 출발하여 각 도시를 한 번만 방문하고 출발한 도시로 돌아오는 경로의 최소비용을 구하는 문제 알고리즘 분류 - 브루트포스, (백트래킹, DP?) 난이도 - 실버2 관련 개념 C++에서 순열 사용하기 - std::next_permutation https://cplusplus.com/reference/algorithm/next_permutation/ https://cplusplus.com/reference/algorithm/next_permutation/ function template std::next_permutation default (1)template bool next_permutation (BidirectionalIterator first..
-
[leetcode - python] Excel SheetProblem Solving 2022. 7. 20. 00:15
문제 설명 https://leetcode.com/problems/excel-sheet-column-number/submissions/ Excel Sheet Column Number - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 - Easy A~Z가 1~26열을 나타내고, 27 이상은 AA와 같이 알파벳의 조합으로 표현될 때, 주어진 알파벳 조합이 몇열인지 구하는 문제 관련 개념 문자열, 아스키코드 접근 방법 26^(자릿수) + 알파벳에 해당하는 열 을..
-
[leetcode - Python] Roman to IntegerProblem Solving 2022. 7. 19. 14:29
문제 설명 https://leetcode.com/problems/roman-to-integer/submissions/ Roman to Integer - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 - Medium 문자열로 주어지는 로마 숫자를 아라비아 숫자로 바꾸는 문제 접근 방법 기본적으로 알파벳을 만나면 해당 숫자를 더해주는데, 만난 알파벳보다 그 다음 알파벳이 더 크면 빼준다. 이때 주의해야할 점은, 문제 예시엔 I, X, C에 대한 총 6가지 예..
-
[leetcode - python] Majority ElementProblem Solving 2022. 7. 18. 17:11
문제 설명 https://leetcode.com/problems/majority-element/ Majority Element - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 배열 중 과반수 이상 등장하는 수를 찾는 문제 난이도 - Easy 관련 개념 Boyer-Moore Voting Algorithm (보이어-무어 과반수 투표 알고리즘) : 인접한 두 수가 서로 다르다면 둘 다 버리는 개념의 알고리즘. 2개를 버리면 과반수가 1 줄어드므로 Majority E..
-
[leetcode - C] Maximum SubarrayProblem Solving 2022. 7. 16. 13:47
문제 설명 https://leetcode.com/problems/maximum-subarray/ Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 난이도 - Medium 배열에서 연속된 수들 중 합이 가장 큰 조합을 찾는 문제 관련 개념 배열 접근 방법 패턴을 찾으면 구현은 어렵지 않은 문제. 배열의 요소를 앞에서부터 탐색하면서 현재 탐색하는 수를 Maximum Subarray에 포함할지 말지가 관건 이므로, (직전까지의 누적합+현..