Algorithm
-
[Array, Sorting] 문제 이름 : Picking TicketsAlgorithm/HackerRank 2021. 7. 17. 17:33
문제 설명 주어진 배열을 정렬시킨 후 조건을 만족하는 부분 배열의 최대 크기 구하기 조건 1. 부분배열의 원소들은 이어져 있어야 함 2. 모든 원소 j와 j+1의 값의 차이의 절대값은 0 이나 1 이어야 함 1. 사용 알고리즘 배열 정렬 2. 문제 해결 아이디어 우선 주어진 리스트를 오름차순 정렬시킨 후, 첫번째 원소부터 시작하여 조건을 만족하지 않는 원소를 만날 때까지 반복하여 조건을 만족하는 부분 배열들을 구하고, 그 중 가장 큰 크기의 부분배열을 찾는다. 3. 코드 구현방식) 주어진 리스트 오름차순 정렬 -> Collections 클래스의 sort() 사용 첫번째 원소부터 조건 만족하는 부분 배열 찾기 -> 반복문 사용하여 각 리스트의 원소 접근 //부분배열의 최대 크기 반환! static int ..
-
[DFS/BFS] 개념정리3 - DFS과 BFSAlgorithm/개념정리 2021. 7. 17. 14:29
그래프 탐색이란? → 하나의 정점을 시작으로 다수의 정점을 방문하는 것 DFS(Depth First Search) 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘임 사용 자료구조 : 스택 동작 과정 : 탐색 시작 노드를 스택에 삽입하고 방문 처리함 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고 방문처리 함 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄 2번의 과정을 더 이상 수행할 수 없을 때까지 반복함 —> 방문 처리 : 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않..
-
[추가] 복잡도Algorithm/개념정리 2021. 7. 9. 10:58
복잡도?! 복잡도(Complexity)는 알고리즘의 성능을 나타내는 척도 시간복잡도 + 공간복잡도 시간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 → 알고리즘을 위해 필요한 연산 횟수 측정 공간복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 → 알고리즘을 위해 필요한 메모리의 양 측정 → 둘은 일종의 거래 관계가 성립함 → 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하는 등 → 메모리를 더 많이 사용해서 시간을 비약적으로 줄이는 방법을 '메모이제이션' 기법이라고 함 복잡도가 낮을수록 좋은 알고리즘 시간 복잡도 알고리즘 문제 풀 때 단순히 '복잡도'는 시간 복잡도를 의미함 시간복잡도 표현 시 '빅오(Big-O) 표기법'을 사용함 →..
-
[DFS/BFS] 문제 이름 : 미로 탈출Algorithm/유형별 문제 풀기 2021. 7. 8. 11:34
문제 설명 N x M 크기의 직사각형의 미로가 주어질 때, 주인공의 위치는 (1,1)이고 미로의 출구는 (N,M)의 위치에 존재하며 한번에 한 칸식 이동할 수 있다. 이때 괴물이 있는 부분은 0, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시되는데, 이때 주인공이 미로를 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다. 1. 사용 알고리즘 그래프 탐색 - BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 2. 문제 해결 아이디어 주어진 문제는 미로를 탈출하기 위한 최소 칸의 개수를 구하는 것이므로, 탐색 시 더 이상 길이 없다면 다시 되돌아오게 되고 그러면 이때까지 잘못된 길로 갔을 때의 이동횟수..