728x90 ALGORITHM142 [Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕(Greedy) 알고리즘 최적해를 구하는 데 사용되는 근시안적 방법 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택하여 최종 해답에 도달 ex) 거스름 돈의 지폐/동전 개수 최소화 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없음 탐욕 알고리즘 동작 과정 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가 실행 가능성 검사 : 새로운 부분해 집합이 실행 가능한지 확인, 문제의 제약 조건을 위반하지 않는지 검사 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지 확인 해 검사 : 아직 전체 문제의 해가 완성되.. 2021. 8. 22. [BOJ/Python] 1920. 수 찾기 📌 문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 📌 문제 접근 방법 이진 탐색 적용해보기! start랑 end범위 잡아주는 게 은근 헷갈린다..! 완전히 이해될 때까지 주말동안 문제 많이 풀어보기!!!! 📌 코드 import sys def isin(A, B): A.sort() result = [0]*M for i in range(M): start = 0 end = N-1 while sta.. 2021. 8. 21. [PG/Python] 모의고사 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 📌 문제 접근 방법 완전 탐색 적용해보기! answers리스트의 길이가 계속 바뀌어서 길이를 설정해주는 함수를 만들어서 길이를 늘려주었다. 다른 사람의 코드를 보니 answers의 해당 인덱스를 패턴 길이로 나누어서 바로 인덱싱을 해주었더라! 완전 깔끔✨ 어떻게 하면 그렇게 생각해서 코드를 구현할 수 있을까..!!! 📌 코드 def set_len(pat.. 2021. 8. 21. [Algorithm] 검색 - 완전 검색, 순차 검색, 이진 검색 검색/탐색 알고리즘 (Search Algorithm) 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업 탐색 키(Search Key) : 자료를 구별하여 인식할 수 있는 키 완전 검색(Exaustive Search) 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 수행 속도 느리지만 해답 찾아내지 못할 확률 작음 경우의 수가 상대적으로 작을 경우 유용 문제 풀 때 완전 검색으로 해답 도출 후, 성능 개선 위해 다른 알고리즘 사용하고 해답 확인하는 것이 바람직 완전 검색 종류 Brute-force : for문 사용하여 처음부터 끝까지 탐색 👉 Brute-force 적용해보기 비트 마스크 : 비트 연산 사용(&, |, ^, ~, ) 백트래킹 : 해를 찾아가는 도중 해가 될 가능성.. 2021. 8. 20. 이전 1 ··· 25 26 27 28 29 30 31 ··· 36 다음 728x90