Data Engineering
-
[백준 10819번] 완전 탐색 기법Data Engineering/알고리즘 - Python 2021. 6. 28. 15:29
[백준 10819번 - 차이를 최대로] https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net (첫번째 시도 - 오답) 생각했던 방법: |가장 큰 수 - 가장 작은 수| + |두번째 큰 수 - 두번째 작은 수| + ... 로 하면 될 것 같았다. n=int(input()) nums=list(map(int, input().split())) max=sorted(nums, reverse=True) min=sorted(nums) sum=0 for i in range(n//..
-
[백준 10974번] 완전 탐색 기법Data Engineering/알고리즘 - Python 2021. 6. 28. 14:36
📍완전 탐색 기법이란? : (컴퓨터의 계산을 이용하여) 가능한 모든 경우의 수를 확인해서 정답을 찾는 방법이다. 📍언제 사용하는가? : 시간이 많이 들기 때문에 탐색 범위가 적을 때 사용한다. 📍완전 탐색을 이용하기 위해서 사용되는 5가지 알고리즘 ◾ Brute-Force ◾ 비트마스크 ◾ 재귀 함수 ◾ 순열 ◾ BFS/ DFS 📍각 알고리즘에 대해 살펴보자. 1⃣ Brute-Force : 단순하게 for, if 문으로 모든 경우의 수를 찾는다. 2⃣ 비트마스크 : 2진수 표현 기법을 사용한다. (AND, OR, XOR, SHIFT, NOT) 3⃣ 재귀 함수 : 함수 내에서 자기 자신을 다시 호출한다. 4⃣ 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 나열한다. ex) [1,..
-
[백준 10610번] 그리디 알고리즘Data Engineering/알고리즘 - Python 2021. 6. 27. 18:31
[백준 알고리즘 - 10610번 30] https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net (오답) 문제: 시간초과 *그래도 문제는 잘 풀었다! 시간 초과는 차차 해결해 나가면 된다. import itertools n=list(str(int(input()))) nums=list(map(int, map(''.join, itertools.permutations(n)))) nums.sort(reverse=True) #가장 큰 수를 찾아야 하므로 내림차순 ..
-
[백준 2875번] 그리디 알고리즘Data Engineering/알고리즘 - Python 2021. 6. 27. 17:08
[ 백준 알고리즘 - 2875번 대회 or 인턴 ] https://www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net (오답) n,m,k=map(int, input().split()) ans=0 for i in range(max(n,m,k)): n-=2 m-=1 if n==0 or m==0: if (n+m)>k: ans+=1 break else: break else: ans+=1 print(ans) 문제: 문제의 예제가 아닌 경우 오답이 발생한다. (정답1) n,m,k=map(int, input().split()) ans=0 wh..
-
[백준 11047번] 그리디 알고리즘 / Greedy AlgorithmData Engineering/알고리즘 - Python 2021. 6. 27. 15:57
" The present is more important than the future. " 📍그리디 알고리즘(Greedy Algorithm) : 지금 이 순간의 최적인 답을 선택하는 알고리즘 설계 기법이다. 즉, 미래보다 현재의 이익을 추구한다고 생각하면 이해가 쉽다. 그런데 현재의 이익만 추구하는 것이므로 최적의 정답이 아닐 수 있다. 📍그럼 왜 그리디 알고리즘을 사용할까? : 이 순간의 최선의 선택을 하므로 성능이 빠르다! 그렇기 때문에 최적의 정답에 가까운 근사적인 답을 내릴 수 있다. [ 백준알고리즘 11047번 - 동전0 ] https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,00..