반응형 알고리즘6 [Algorithm] 구현 문제란? 학습 목표 · 구현 문제란? · 구현 시 고려해야 할 메모리 제약 사항 · 채점 환경 · 구현 문제에 접근하는 방법 구현 문제란? 코딩 테스트에서 구현 · 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현 문제 · 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 - 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제된다. - ex) 완전 탐색, 시뮬레이션 유형 ▶ 완전 탐색: 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 ▶ 시뮬레이션: 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 문제 구현하기 어려운 문제란? 1. 알고리즘은 간단한데 코드가 치나칠 만큼 길어지는 문제 2. 특정 소수점 자리까지 출력해야 하는 문제 3. 문자열이 입력으로 주어졌을 때 한 문자 .. 2021. 11. 6. [Algorithm] 이것이 코딩테스트다 - 이진탐색 문제풀이(with 자바) 부품찾기 public class 부품찾기 { public static void main(String [] args){ Scanner scanner = new Scanner(System.in); int N = scanner.nextInt(); int[] parts = new int[N]; for(int i=0; i target){ start = mid+1; } else { end = mid-1; } } } } 2021. 9. 13. [Algorithm] 순차 탐색과 이진 탐색 순차 탐색 (Sequential Search) · N개의 데이터가 있을 때, 해당 데이터를 차례대로 하나씩 확인하여 처리하는 방법 · 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인 · 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요 -> 최악의 경우 시간 복잡도: O(N) ▶ 예시 - 순차 탐색으로 특정 문자열의 위치 찾기 public class SequentialSerach { public static void main(String[] args){ String[] strings = {"a","b","c","d","e"}; String target = "d"; for(int i=0; i< strings.length; i++) if(strings[i].equals(target)) Sy.. 2021. 9. 6. [Algorithm] DFS와 BFS란? 작동 방식과 구현 방법(with 자바) DFS와 BFS란? 작동 방식과 구현 방법(with 자바) 이 글은 DFS와 BFS 개념에 대해 설명하고, 작동 방식을 그림으로 보여주며, 이러한 작동 방식을 자바 소스 코드로 구현합니다. 학습 목표 ㆍDFS ㆍBFS ㆍ정리 DFS · DFS(Depth-First Search)는 깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 알고리즘 동작 방식 · 스택 자료구조를 이용한다. 1. 탐색 시작 노드를 스택에 삽입하고, 방문 처리한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 위의 1번과 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.. 2021. 1. 26. [Algorithm] 알고리즘 구현 유형 문제 풀이 - 시각 문제 '이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 알고리즘 구현 유형 문제 중 ' 시각' 문제와 풀이를 설명합니다. 문제 🎁입력 조건 정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하라. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다 00시 00분 03초 00시 13분 30초 반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다 00시 02분 55초 01시 27분 45초 🎁입력 조건 첫째 줄에 정수 N이 입력된다. (0 2021. 1. 16. [알고리즘] 백트래킹 문제 - Sum of Subsets 백트래킹 문제 - Sum of Subsets 백트래킹(Backtracking) 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻한다. 즉, 탐색하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다고 해서 백트래킹이라는 이름이 붙었다. Sum of Subsets 백트래킹을 사용하여 해결할 수 있는 문제 중 Sum of Subsets이 있다. Sum of Subsets은 집합 w의 부분집합 중 그 합이 숫자 K와 같은 부분 집합들을 찾는 문제다. 이때, 집합에 음의 값과 중복 값은 없다고 가정한다. 예제를 통해 문제를 이해해보자. 집합 w는 w₁ = 2, w₂ = 10, w₃ = 13, w₄ = 17, w₅ = 22, w₆ = 42 이다. K = 52일때, K와 값이 같은 집합 w의 부분 .. 2021. 1. 1. 이전 1 다음 반응형
