Greedy

Greedy Algorithm현재 상황에서 지금 당장 좋은 것만 고르는 방법매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음.사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 함기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 "가장 큰 순서대로", "가장 작은 순서대로" 와 같은 기준을 알게 모르게 제시 거스름돈음식점의 계산을 도와주는 점원이 있다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수..

• format_list_bulleted Algorithm
• · 2025. 3. 18.
• textsms

Baekjoon - 약수, 소수와 배수

13241. 최소공배수 Solution유클리드 호제법 (Euclidean Algorithm)2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나..1)def gcd(m, n): if m 2)def gcd(m, n): while n != 0: t = m % n (m, n) = (n, t) return abs(m) 3)def gcd(m, n): while n != 0: if m  이를 이용해 최소공배수를 구할 수 있음,, a와 b의 최소공배수는 a와 b의 곱을 a와 b의 최대공약수를 나눈 값과 같다.def lcm(a, b): return (a * b) // gcd(a, b) 주의해야 할 점 : Python 에서는 위에서 아래로 Intepreter 가 한 줄씩 읽으므..

• format_list_bulleted Algorithm
• · 2024. 10. 20.
• textsms

Baekjoon - 집합과 맵

10815. 숫자 카드 Solutionn개의 정수들은 순서가 필요 없음 : Setm개의 정수들은 순서 필요 : list => 안에 존재하는지를 판단한다. (for문)import sysinput = sys.stdin.readlineN = int(input())N_set = set(map(int, input().split()))M = int(input())M_list = list(map(int, input().split()))for i in M_list: if i in N_set: print("1", end=" ") else: print("0", end=" ") 14425. "문자열 집합" String (N개) => 집합 S,,S에 포함되어 있는 문자열이다.M : 검사해야..

• format_list_bulleted Algorithm
• · 2024. 10. 3.
• textsms

Baekjoon - 정렬

2752. 수 정렬 N개의 수가 주어졌을 때, 오름차순으로 정렬하는 문제이다. (단, 수는 중복 X)  Solution중복되지 않은 수들만 존재하므로 Set 자료구조를 이용하는 것부터 생각을 출발하였다. 그러나 중복은 기본 옵션이므로 List로 진행하였다.  그래서, Sorted() function 을 사용하여 진행하였다.Sorted(정렬할 데이터 : iterable, key parameter (어떤 것을 기준으로 : Default : key), reverse parameter (오름차순 : Defalut -> False, 내림차순 : True))Sort() : 본체 리스트를 정렬 후 반환.Sorted() : 본체 리스트에서 정렬한 새로운 리스트 반환. N = int(input())N_set = set(..

• format_list_bulleted Algorithm
• · 2024. 10. 1.
• textsms

Baekjoon - Brute-Force

Brute-Force Algorithm문제를 해결하기 위하여, 모든 경우를 탐색하고 답을 도출하는 Algorithm.=> 결과를 찾는다는 것에 중점을 둔다. 이것과 비슷한 것은 완전 탐색 알고리즘이 있다. (같지만 다른 점이 존재) 완전 탐색 알고리즘모든 경우의 수를 전부 탐색하는 방식의 알고리즘으로, 결과보다는 탐색에 중점을 둔다. 이 Algorithm의 사용 조건은 다음과 같다.문제에서 달성하고자 하는 Solution이 잘 정의되어야 한다.문제를 해결할 수 있는 풀이의 수가 제한되어 있어야 한다.Algorithm Example1. 반복문을 사용하는 경우-> 대부분 반복문과 조건문을 활용해서 모든 경우를 탐색한다.2. 재귀를 사용하는 경우-> 피보나치 수열 (DP (Dynamic Programming)..

• format_list_bulleted Algorithm
• · 2024. 9. 18.
• textsms

Baekjoon Time-complexity

24262번 문제 이 문제는 시간복잡도를 확인하는 문제이다. n을 입력하면 절반으로 계속 줄이고 그 수를 배열의 인덱스로 넣어서 반환해주고 있다. 따라서, 이걸 다항식으로 표현하였을 때 미지수로 표현한다면 x라고 표현할 수 있다. 이 x의 시간 복잡도를 표현한다면 O(n) 이다. 단지 최고차항의 차수를 출력하고 그게 아니면 0을 출력하는 의미이므로, 출력문 두 개만 존재해도 문제는 풀린다.public class Main { public static void main(String[] args) { System.out.println("1"); System.out.println("0"); }}  24263 문제  이 문제는 n을 받아서 1 ~ n까지 입력 받고 있다. 예제 입력..

• format_list_bulleted Algorithm
• · 2024. 9. 18.
• textsms