![]()
구현 개념 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것 동일한 알고리즘이면 더 간결하고 효율적인 코드가 잘 작성된 코드 아이디어 떠올리는 것과 별개로 구현 능력은 실무에서도 매우 중요 유형 완전 탐색 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법 모든 경우의 수를 다 계산 반복문 혹은 재귀 함수를 적절히 사용하여 예외 케이스 모두 확인 일반적으로 DFS/BFS 알고리즘 이용 시뮬레이션 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형 완전 탐색과 해결 방법 비슷, 복잡한 구현 요구사항을 그대로 코드로 작성 원소를 나열하는 모든 경우의 수를 고려해야 하는 상황에서 보통 순열이나 조합 라이브러리 사용 → 파이썬 표준 라이브러리 itertools로 쉽게 구현 문제 ..
![]()
구현 개념 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것 동일한 알고리즘이면 더 간결하고 효율적인 코드가 잘 작성된 코드 아이디어 떠올리는 것과 별개로 구현 능력은 실무에서도 매우 중요 유형 완전 탐색 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법 모든 경우의 수를 다 계산 반복문 혹은 재귀 함수를 적절히 사용하여 예외 케이스 모두 확인 일반적으로 DFS/BFS 알고리즘 이용 시뮬레이션 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형 완전 탐색과 해결 방법 비슷, 복잡한 구현 요구사항을 그대로 코드로 작성 원소를 나열하는 모든 경우의 수를 고려해야 하는 상황에서 보통 순열이나 조합 라이브러리 사용 → 파이썬 표준 라이브러리 itertools로 쉽게 구현 문제 ..
![]()
구현 개념 머릿속에 있는 알고리즘을 정확하고 빠르게 프로그램으로 작성하는 것 동일한 알고리즘이면 더 간결하고 효율적인 코드가 잘 작성된 코드 아이디어 떠올리는 것과 별개로 구현 능력은 실무에서도 매우 중요 유형 완전 탐색 모든 경우의 수를 빠짐없이 다 계산하는 해결 방법 모든 경우의 수를 다 계산 반복문 혹은 재귀 함수를 적절히 사용하여 예외 케이스 모두 확인 일반적으로 DFS/BFS 알고리즘 이용 시뮬레이션 문제에서 제시하는 논리나 동작 과정을 그대로 코드로 옮겨야 하는 유형 완전 탐색과 해결 방법 비슷, 복잡한 구현 요구사항을 그대로 코드로 작성 원소를 나열하는 모든 경우의 수를 고려해야 하는 상황에서 보통 순열이나 조합 라이브러리 사용 → 파이썬 표준 라이브러리 itertools로 쉽게 구현 문제 ..
![]()
그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 시간이 적게 걸리는 음식부터 확인하는 탐욕적 접근 방식으로 해결 시간 기준으로 정렬한 후, 시간이 적게 걸리는 음식부터 제거 ex) 3개의 음식, K를 15초라고 ..
![]()
그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 정렬을 이용한 그리디 알고리즘 아이디어 화폐 단위 오름차순 정렬 1부터 차례대로 특정 금액 target 만들 수 있는지 확인 target을 만들 수 있으면, 값 업..
![]()
그리디 개념 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 '최적의 해'를 찾는 문제로 출제 ➝ 그리디 알고리즘의 정당성을 고민해보기 다양한 알고리즘에 두루 사용 # ex) 다익스트라 최단 경로 알고리즘, 크루스칼 알고리즘 빈출유형 거스름돈 문제 거슬러 줘야 할 동전의 최소 개수 찾는 문제 가장 큰 단위의 화폐 ~ 작은 단위의 화폐를 차례대로 확인하고 거슬러 주는 작업 1이 될 때까지 N이 1이 될 때까지 '1을 빼기' 혹은 'K로 나누기' 연산을 최소 몇 번 수행해야 하는지 계산 최대한 많이 나누기가 문제 해결 아이디어 문제 해설 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중에서 더 적은 횟수를 가지는 겨우 계산 모두 0으로 만드는 경우 모두 1로 만드는 경우 풀이 data = inp..
