본문 바로가기

개발 일기/알고리즘

(5)
[알고리즘] 조합 ex) 5개 중 3개 뽑는 방법 오늘 모 기업 코딩테스트를 봤는데 조합 문제가 나와서 올려본다. 예: 5개의 숫자 중 3가지를 뽑는 방법... 중복 없이! public class Main { static void combination(int[] arr, boolean[] visited, int start, int n, int r) { if (r == 0) { for (int i = 0; i < arr.length; i++) { if (visited[i]) System.out.print(arr[i] + " "); } System.out.println(""); return; } for (int i = start; i < n; i++) { visited[i] = true; combination(arr, visited, i + 1, n, r ..
[알고리즘] JAVA 정렬 정렬 효율을 위해 필요하다!! 선택 정렬 가장 작은 데이터를 선택해 맨 앞으로 보내고 이를 반복. 가장 작은 데이터를 앞으로 보내는 과정을 n-1번 반복. O(n^2)으로 데이터 10,000개 이상은 느려짐. 삽입 정렬 첫 번째 자리는 정렬되어 있다고 판단하고 두 번째 자리부터 시작. 두 번째 데이터가 어떤 위치로 들어갈지 판단하고 첫 번째 보다 작은지 큰지 비교해 왼쪽 혹은 오른쪽에 삽입. 자신의 위치에서 한칸씩 아래로 내려가며 크기를 비교 후 삽입. O(n^2)으로 리스트가 정렬되어 있는 상태에서 선택 정렬보다 빠르게 동작하여 최선의 경우 O(n)까지 가능. 퀵 정렬 가장 많이 사용되는 알고리즘. 기준(Pivot) 데이터를 설정하고 기준보다 큰 데이터와 작은 데이터의 위치를 바꿈. 호어 분할 방식: ..
[알고리즘] BFS 너비 우선 탐색 BFS란? 가까운 노드부터 탐색. 즉 옆에 있는 것부터 탐색. 큐를 이용하여 구현. BFS 방법 탐색 시작 노드를 큐에 삽입하고 방문 처리. 큐에서 노드를 꺼내 인접 노드 중 방문하지 않은 노드 모두 큐에 삽입하고 방문처리. 2번을 처리할 수 없을 때 까지 실행. public class BFS { public static void Solution(int[][] graph) { Queue queue = new LinkedList(); boolean[] visited = new boolean[graph.length]; queue.add(1); // START visited[1] = true; while (!queue.isEmpty()) { int num = queue.poll(); System.out.pri..
[프로그래머스] 완전탐색 Lv.1 모의고사 모의고사 문제 설명 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution ..
[프로그래머스] 정렬 Lv.1 K번째 수 -문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 array의 길이는 1 이상 100 이하입니다. ..