Algorithm
-
[백준 1157번] - 기본 / PythonData Engineering/알고리즘 - Python 2021. 6. 30. 21:29
[백준 1157번] - 기본 https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net (오답) x=input() arr=[x[i].upper() for i in range(len(x))] mySet=list(set(arr)) dict={} for i in range(len(mySet)): a=arr.count(mySet[i]) dict[mySet[i]]=a key,value = dict.items() if len(max(dict.values()))==1: print(key) else: ..
-
[백준 1260번] BFS, DFSData Engineering/알고리즘 - Python 2021. 6. 29. 15:46
[백준 1260번] DFS와 BFS] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net (정답) 처음 해보는 문제라서 많이 어려워서 다른 답들을 참고했다. n,m,v=map(int,input().split()) mat=[[0]*(n+1) for _ in range(n+1)] visit=[0]*(n+1) for i in range(m): x,y=map(int, input().split()) mat[x][y]=m..
-
[백준 6603번] 완전 탐색 기법Data Engineering/알고리즘 - Python 2021. 6. 28. 17:13
[백준 6603번 - 로또] https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net (오답) 문제점: "독일 로또는 수 6개를 고른다"는 조건을 고려주지 않았다. 고칠점: 문제의 조건을 꼭 확인하고 시작하자. import sys from itertools import permutations arr=[] while True: a=list(map(int, sys.stdin.readline().split())) arr.append(a) if a[..
-
[백준 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,..