알고리즘
-
[정렬] 개념정리1 - 삽입 정렬, 선택 정렬, 퀵 정렬, 계수 정렬Algorithm/개념정리 2021. 8. 18. 10:01
개념 → 정렬 : 데이터를 특정한 기준에 따라 오름차순 or 내림차순으로 나열하는 것 → 자료 탐색에 있어서 필수적임! → 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색이 가능해짐(정렬은 이진 탐색의 전처리 과정이기도 함) 추가) 오름차순으로 정렬된 데이터들을 내림차순 정렬할 경우 : 리스트 뒤집는 연산은 O(N)의 복잡도로 간단히 수행 가능함 분류 *정렬 알고리즘 선택 기준 → 모든 경우에 최적인 정렬 알고리즘은 없음 → 각 응용분야에 적합한 정렬 방법을 사용해야 함 ex) 레코드 수의 많고 적음, 레코드 크기의 크고 작음, key의 특성(문자, 정수, 실수 등), 메모리 내부/외부 정렬 *정렬 알고리즘의 평가 기준 → 비교 횟수의 많고 적음, 이동 횟수의 많고 적음 *정렬 알고리즘 분류 [1] 단순하..
-
[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] 문제 이름 : 미로 탈출 (위의 문제와 동일한 개념의 문제이다! 문제 내용만 다를 뿐 사실상 동일하다.) 주어진 문제는 시작 지점으로 부터 특정 위치(도착 지점)까지 걸리는 시간을 구하는 것이므로 탐색을 사용해야 ..
-
[추가] 복잡도Algorithm/개념정리 2021. 7. 9. 10:58
복잡도?! 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도 시간복잡도 + 공간복잡도 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 → 알고리즘을 위해 필요한 연산 횟수 측정 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 → 알고리즘을 위해 필요한 메모리의 양 측정 → 둘은 일종의 거래 관계가 성립함 → 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하는 등 → 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법을 '메모이제이션' 기법이라고 함 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 알고리즘 문제 풀 때 단순히 '복잡도'는 시간 복잡도를 의미함 시간복잡도 표현 시 '빅오(Big-O) 표기법'을 사용함 →..
-
[구현] 문제이름 : 게임 개발Algorithm/유형별 문제 풀기 2021. 6. 30. 12:20
문제 설명 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이루어진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동성남북 중 한 곳을 바라본다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 메뉴얼은 다음과 같다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향 부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3 만약 네 방향 모두 이미 가본 칸..