Algorithm
-
[정렬] 개념정리1 - 삽입 정렬, 선택 정렬, 퀵 정렬, 계수 정렬Algorithm/개념정리 2021. 8. 18. 10:01
개념 → 정렬 : 데이터를 특정한 기준에 따라 오름차순 or 내림차순으로 나열하는 것 → 자료 탐색에 있어서 필수적임! → 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬은 이진 탐색의 전처리 과정이기도 함) 추가) 오름차순으로 정렬된 데이터들을 내림차순 정렬할 경우 : 리스트 뒤집는 연산은 O(N)의 복잡도로 간단히 수행 가능함 분류 *정렬 알고리즘 선택 기준 → 모든 경우에 최적인 정렬 알고리즘은 없음 → 각 응용분야에 적합한 정렬 방법을 사용해야 함 ex) 레코드 수의 많고 적음, 레코드 크기의 크고 작음, key의 특성(문자, 정수, 실수 등), 메모리 내부/외부 정렬 *정렬 알고리즘의 평가 기준 → 비교 횟수의 많고 적음, 이동 횟수의 많고 적음 *정렬 알고리즘 분류 [1] 단순하..
-
[Greedy] 문제 이름 : University Career Fair - 사용자 정의 클래스 객체 정렬Algorithm/HackerRank 2021. 7. 30. 11:07
문제 설명 A team organizing a university career fair has a list of companies along with their respective arrival times and their duration of stay. Only one company can present at any time. Given each company's arrival time and the duration they will stay, determine the maximum number of presentations that can be hosted during the career fair. 사용 개념 그리디, 객체 정렬 문제 해결 아이디어 주어진 시간동안 최대한 많은 발표를 해야하므로 그리디..
-
[BFS] 문제 이름 : Reach the End in TimeAlgorithm/HackerRank 2021. 7. 20. 11:27
문제 설명 2-D grid가 주어졌을 때 상단의 가장 왼쪽 코너에서부터 하단의 가장 오른쪽 코너까지 K초 안에 도착 가능하다면 "Yes"를, 불가능하다면 "No"를 반환해라. 막힌 곳은 '#'으로, 안막힌 곳은 '.'으로 표시된다. 시작 지점과 도착 지점은 unblocked cell이다. 상하좌우로 이동이 가능하고, 인접 cell로 이동하는데 1초가 소요된다. 사용 개념 그래프 탐색, BFS 문제 해결 아이디어 2021.07.08 - [Algorithm/유형별 문제 풀기] - [DFS/BFS] 문제 이름 : 미로 탈출 (위의 문제와 동일한 개념의 문제이다! 문제 내용만 다를 뿐 사실상 동일하다.) 주어진 문제는 시작 지점으로 부터 특정 위치(도착 지점)까지 걸리는 시간을 구하는 것이므로 탐색을 사용해야 ..
-
[문자열] 문제 이름 : String ReductionAlgorithm/HackerRank 2021. 7. 19. 11:39
문제 설명 알파벳 소문자로 이루어진 문자열이 주어질 때 해당 문자열의 부분 문자열이 모두 서로 다르도록 문자열을 줄일 때 최소 삭제 횟수를 구해라(문자열의 아무 index 삭제 가능) 사용 개념 문자열, 반복문 문제 해결 아이디어 부분문자열의 경우 문자 1개도 부분 문자열에 해당한다. 즉 부분 문자열이 서로 다르도록 하려면, 문자열에서 각 알파벳이 1개만 존재해야 한다. 따라서 최소 삭제의 경우는 2개 이상 존재하는 알파벳들을 1개 빼고 모두 삭제하면 된다. 코드 구현 방식) ㄱ. 알파벳 등장 횟수 저장을 위한 int 배열 선언(index 0 = a, index 1 = b . . .) ㄴ. String 클래스의 charAt()을 사용해 각 문자 접근 ㄷ. 각 알파벳에 해당하는 ㄱ에서 생성한 배열의 ind..