자주 쓰이는 코딩테스트 메소드, 문법 출처: https://earthteacher.tistory.com/169#gsc.tab=0
특정 범위의 숫자 나열되어 있을 때 각 숫자의 개수를 세어보기 문제 정의 M 이상 N 이하의 수가 나열되어 순서에 상관없이 나열되어 있다고 할 때 각 수가 몇 개인지 세어보는 방법을 구현해봅시다. 가령 20세부터 100세 이하의 사람들이 어느 한 장소에 머물고 있다고 할때 연령대에 따라 혹은 각 나이에 따른 인원을 체크해볼 수 있습니다. 문제 해결 이런 문제의 경우 해결하려는 범위 내에서 counting에 필요한 변수의 개수를 생각해 볼 수 있습니다. 연령대에 따른 경우라면 20대, 30대... 100세 까지 셀 수 있는 변수를 선언해서 증가할 수 있습니다. 그렇지 않고 각 나이마다 counting을 하기 위해서는 그 개수만큼의 변수보다는 배열을 선언하여 개수를 세는 것이 합리적인 방법입니다. 수행에 걸리는 시간은 데이터의 개수가 n개라고 할 때, O(n)입니다. ..
경우의 수 문제 (Brute-Force Search) 경우의 수 모든 경우에 대하여 탐색하여 결과를 찾는 문제 문제의 범위가 간단한 경우 완전 탐색으로 모든 해를 찾아보는 방식 수학에서 수열이나 조합과 같은 문제를 해결하는데 사용 문제 정의 심각한 인플레이션을 겪고 있는 어느나라에서 1만원, 2만원, 5만원, 10만원 20만원 50만원 여섯가지 지폐를 사용하고 있다. 배고파씨는 100만원 어치 빵을 사려고 마트에 가서 돈을 내려다 여섯 가지 지폐를 이용하여 100만원 어치 빵을 사는 방법이 모두 몇 가지인지궁금해 졌다. 지불하는 방법은 모두 몇 가지가 있을까? 예를 들어 1만원 10장, 10만원 4장, 50만원 1장 으로 100만원을 지불 할 수 있다. 모두 몇가지인지 구하세요 문제 해결 100 만원이 되는 모든 경우에 대해 탐색하여 지불 가능한 경우의 수..
여러 종류의 동전으로 가격 지불하는 문제(Greedy 알고리즘) 그리디(Greedy) 알고리즘 다른 용어로 탐욕 알고리즘이라고도 함 지금 상황에서 가장 좋은 해결책을 찾는 알고리즘으로 실제 여러 알고리즘 테스트에서도 흔히 볼 수 있는 문제중 하나임 여러 조합에 따른 그 해를 찾는 경우가 많고 이때 제시되는 대부분의 조건은 "가장 금액이 큰 순서부터" 라던가 "가장 면적이 큰 타일을 우선적으로"등의 방식에 제시 이 알고리즘은 조건이 명확할 때 정확한 답을 찾을 수 있고, 기존의 다른 알고리즘의 지식이 없어도 상식적인 범위에서 코딩이 가능하다. 문제 정의 가게에 간 철수는 8370원 어치 물건을 구매하였습니다. 철수에게는 500원짜리 20개 100원짜리 20개 50원짜리 20개 10원짜리 20개의 동전이 있습니다. 철수는 금액을 지불 할 때 단위가 큰 동전부터 지불하려고..
썸네일 피보나치 수열 문제 여러 방식으로 해결하기 재귀 함수로 풀이하기 public int fibonacciRecur(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacciRecur(n - 1) + fibonacciRecur(n - 2); } 반복문으로 풀이하기 public int fibonacciIter(int n) { int ppre = 0; int pre = 1; int current = 0; if (n == 0) return 0; if (n == 1) return 1; for (int i = 2; i
썸네일 미로 찾기 문제 입구에서 출구로 통하는 길을 찾는 미로 찾기 문제 스택을 활용하여 문제를 해결할 수 있음 출구 탐색을 위해 BFS나 DFS로 해결할 수 있음 아래 그림에서 Enter 에서 Exit을 찾아가는 path의 좌표를 출력하세요 움직 일 수 있는 방향의 예: ( 2,2 ) 위치에서 볼 수 있는 도달 가능 위치는 N(2,1), E(3,2), S(2,3), W(1,2) 하나의 위치를 방문할때마다 stack에 위치를 저장한다. (push) 저장된 위치에서 더 이상 갈 곳이 없는 경우 되돌아 간다. ( pop ) stack에서 꺼낸 위치에서 가지 않은 곳을 찾아 간다. 미로 정의 public class Maze { public int[][] myMaze ={ {0, 1, 1, 1, 0, 1, 1, 1}, {0, 0, 0..
다익스트라(Dijlstra) 알고리즘 https://m.blog.naver.com/ndb796/221234424646# 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 참조: 안경잡이개발자님의 블로그 패컴에서 공부한 최적경로 찾기 알고리즘 강의에서 다익스트라 알고리즘을 들어 서치 중 찾은 좋은 페이지라 따로 정리할 겸 참조합니다.
썸네일 최단거리 구하기 문제 문제 풀이 모든 노드 중 연결된 최단거리를 가진 노드를 찾아서 노드 v에 인접한 노드 w 에 대해 다음 조건이 성립하면 w 에 대한 최단 거리를 업데이트 한다 (즉 원래 w로 가던 거리보다 v를 거쳐 가는 거리가 더 가까우면 w로 가는 거리는 v를 거쳐가는 것으로 최단 거리를 수정) Yw = Yv + Cvw if Yv + Cvw < Yw class MyGraph{ private int count; //노드 수 private int[][] vertexMatrix; // matrix로 그래프 표시 private int[] distance; // 특정 노드에 대한 각 노드의 최단 거리 private boolean[] visited; // alread visited??? private static int UNL..
썸네일 DFS(Depth - First Search)와 BFS(Breadth - First Search)그래프 탐색 그래프 탐색 그래프를 matrix로 표현하기 public class UndirectedGraph{ private int count; private int[][] vertexMatrix; public UndirectedGraph(int count){ this.count = count; vertexMatrix = new int[count][count]; } public void addEdges(int from, int to, int weight){ vertexMatrix[from][to] = weight; vertexMatrix[to][from] = weight; } public int[][] getMatrix(){ return vertexMatrix; } } 깊이 우선 탐색(DFS) 인접한 노드를 우선 탐..
썸네일 정렬 알고리즘 평균 수행 시간이 O(n^2)인 알고리즘 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상씩 비교를 하여 정렬 됨 Insertion Sort 구현해보기 Insertion Sort의 기본 개념은 이미 정렬된 상태의 요소에 새로운 요소를 추가할 때 정렬하여 추가하는 개념이다.(손안의 카드) 두 번째 요소 부터 이전 요소들과 비교하면서 insert 될 위치를 찾아가며 정렬하는 알고리즘 public class InsertionSort { public static void insertionSort(int[] arr, int count) { int i = 0, j = 0; int temp = 0; for(i =..
정렬된 수에서 하나의 수의 위치 찾기 문제 정의 여러 개의 수가 정렬된 순서로 있을 때 특정한 수를 찾는 방법 단순 반복문을 이용하면 수의 개수에 따라 비교 횟수가 증가하는 O(n)의 수행이 이루어짐 수가 정렬된 상태에서는 이진 탐색(binary search)을 활용하면 매번 비교되는 요소의 수가 절반으로 감소될 수 있으므로 O(logN)의 수행으로 원하는 수를 찾을 수 있음 수의 예 : [12, 25, 31, 48, 54, 66, 70, 83, 95, 108] 83의 위치를 찾아보세요 88의 위치를 찾아보세요 해결 방법 수가 정렬된 상태이므로 중간의 값을 하나 선택한다. 찾으려는 값이 그보다 크면 범위를 오른쪽으로 그보다 작으면 범위를 왼쪽으로 좁힐수 있다. 한번 비교 할때 마다 1/2씩 범위가 좁혀진다. 프로그래밍 public class..
나열된 수에서 최솟값과 최댓값 구하기 문제 정의 여러 개의 수가 배열에 있을 때 그 중 가장 큰 값과 가장 작은 값을 찾는다. 배열의 몇 번째에 있는지 순서를 찾는다. 반복문을 한번만 사용하여 문제를 해결한다. 수의 예 : [10, 55, 23, 2, 79, 101, 16, 82, 30, 45] 해결하기 배열에 있는 수 중 맨 처음에 있는 값을 max와 min으로 가정하고, 배열의 마지막 숫자까지 비교하면서 더 큰 수나 더 작은 수가 나올때 max와 min의 값을 바꾸도록 한다. 그때의 위치를 변수에 저장한다. 프로그래밍 public class MinMaxProblem { public static void main(String[] args) { int[] numbers = {10, 55, 23, 2, 79, 101, 16, 82, 30, 4..
라이브러리 브랜드 그룹 | 코드는 기억보단 기록

티스토리툴바