본문 바로가기

Algorithm

 (84)
알고리즘 공부하기 [1. 배열] 배열, 단순하게는 인덱스로 관리를 하고, 처음에 크기를 설정한다. 배열 관련 알고리즘문제는 너무도 많이 나오기 때문에, 자세한 설명은 생략 1.Arrays 관련 기능 - Arrays.toString(배열); -> 배열의 값을 String으로 출력해준다. - arr1[1].indexOf("hi") -> hi or hi 말고 알파벳 하나일 경우, 해당 문자가 포함된 인덱스를 return 해준다. ex. arr1[1] ="abcd" 1)arr1[1].indexOf("b") -> return 1 알파벳이 없다면, -1을 반환한다. 따라서, 해당 내 문자열 포함 여부는, if(arr1[1].indexOf("g") >= 0) 이런식으로 검사를 한다. - Arrays.sort, (Collections.reverseO..
[프로그래머스] 프린터 풀이 프린터 문제 설명 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. 예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다. 내가 인쇄를 요청한 문서가 몇 번째로 인쇄..
프로그래머스 [기능개발] 풀이 문제 설명 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 개의 기능이 배포되는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 작업의 개수(progresses, speeds배열의 길이)는 100개 이하입니다. 작업 진도는 100 미만의 자연수입니다. 작업 속도는 100 이하의 자..
5. 알고리즘 정리 [그리디] 그리디 알고리즘, 흔히 말해 탐욕기법이다. 우선 해당 알고리즘의 동작 형태 및 구현 방법에 대해서 익혀보자 그리디 탐욕기법은, 경우의 수가 존재할 경우, 매순간 최선의 경우를 선택하는 알고리즘이다. 현재 상황에서 가장 좋다고 생각되는 것을 선택해 나가는 것이기 떄문에, 항상 가장 좋은 결과를 만드는 것은 아니다. 그럼, 그냥 문제를 바로 풀어보자 * 동전 0 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) w..
4. 알고리즘 정리 [투 포인터] 투 포인터의 대표 적인 예제는 아래와 같다. 리스트 A가 있고, 타겟값 S가 있다. 이 리스트에서 두수의 합이 타겟값 S가 되는 걸 찾는다고 가정하면? 리스트 1개씩 비교해 가면서 체크를 할수있겠지만. 리스트의 크기에 따라, 시간 복잡도는 정비례하게된다. 그러면 이럴 경우에는 ? 리스트를 정렬하고 투포인터 알고리즘을 사용하면 된다. 사용 방법은 아래 순서와 같다. 1. 리스트를 오름차순으로 정렬한다. 2. 포인터 left는 리스트의 시작점을 포인터 right는 리스트의 끝점을 가리킨다. 3. left 와 right가 만날때까지 다음을 반복한다. 3-1. left + right 의 합이 타겟 값과 같으면 출력, 3-2. left + right 가 타겟 값보다 작으면 left 1증가 3-3 left + ri..
3. 알고리즘 정리 [최단 경로] 최단 경로에 대한 알고리즘을 정리해보자. 엇 최단 경로면 BFS 아닌가? 응 아니야~ 그러면 시작해보자 특정 시작노드에서부터 가중치를 더해가면서 계산하는 다익스트라 알고리즘이라는 것을 써야한다. 다익스트라 알고리즘이란? BFS랑 유사하지만 조금 다른 개념이다. BFS는 단순 가장가까운 노드부터 계산해서 큐에 넣고 빼서 체크를 했다면 다익스트라는 가까운 노드만 업데이트를 하는것이다. 그래서, 우선순위 큐는 minHeap방식을 활용해서 가장 짧은 거리를 가진 노드 정보만 꺼내고 업데이트한다. 좀더 자세히 알아보자 * 최단 경로 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,..
3. 알고리즘 정리 [이분탐색] 이진탐색에 대한 공부를 시작한다. 이진탐색을 왜쓸까? 일단 이것부터 파악을 해야한다. 사실 순차 탐색 = 이진탐색 값을 구하는 건 동일하다. 결국 둘다 탐색을 해서 답을 도출해내는 건 동일하게 성공적으로 실행된다. 근데, 탐색해야되는 량이 엄청 많다면? 그때는 이진탐색을 실행한다. 우선 이진탐색에 대한 기초적인 구현을 시작한다. 아주 간단하게, 5개의 숫자를 입력받고, 그중에 target인 15를 찾는것이다. mid를 시작과 끝점을 합한 /2 를 하고, 만약의 mid index가 타겟보다 크면, 최고를 mid -1 로 이동 반대라면 low를 mid +1로하게된다. 물론 이 것은 입력값이 순차적은 정렬 형태를 띈다는 가정이다. 이렇게 되면 순차 탐색 보다 훨씩 빠른 탐색을 할수있다. 탐색 대상이 많은 경우..
2. 알고리즘 정리 [DFS,BFS] DFS 깊이 우선 탐색이다. 어떤 노드나 행렬이 주어지면, 해당 노으나 행렬에 대한 값을 최대로 깊이 탐색하고, 그다음 노드로가는방법이다. 나는 그림으로 이해하는게 편해서 그림으로 남겨놓으려고한다. 그림이 좀 웃기지만 뭔가 이렇게 이해하는게 편하다 코드를 짤때 생각해야하는 구조로 다시 그려보자 우선 각 노드별로, ArrayList로 각 노드들이 가지는 인접한 것들을 구한다. 역시나 개떡같지만 ㅋ 이 걸 가지고 생각해보는 그림은 처음에 1부터 시작을 하면, 2로가고 2가 3으로가고 3에서 2로가려고하지만, 기존에 2에서 check를 해놨기 때문에 1로, 1도 체크해놨기 떄문에 4로 4는 모든걸 다 check가 되어있기 때문에 out이된다라고 생각하면 된다. 자 공부는 여기까지하고 예제 부터 풀어보자 htt..

티스토리툴바