✔ 그리디 그리디란? 현재 알고리즘에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 최적의 해를 보장하지 않으므로 그리드 알고리즘을 선택해야 하는지, 아닌지 고민이 필요 그리디 알고리즘 수행 과정 현재 상태에서 가장 최선이라고 생각되는 해를 선택 현재 선택한 해가 전체 문제의 조건에 벗어나지 않는지 적절성 검사 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사하고 전체 문제를 해결하지 못하면 앞으로 돌아가 반복 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 수 찾기 [백준 1920] 문제 분석하기 N의 범위가 100000이므로 단순 반복문으로는 문제를 풀 수 없음 이진 탐색을 적용하면 O(MlogN) 시간 복잡도로 해결할 수 있으며, 자바의 기본 정렬을 사용하더라도 O(NlogN) 시간 복잡도를 가짐 손으로 풀어보기 탐색 데이터를 1차원 배열에 저장한 다음 저장된 배열을 정렬 X라는 정수가 존재하는지 이진 탐색을 사용해 확인 슈도코드 작성하기 N(정렬할 수 개수) M(탐색할 숫자의 개수) A(정렬할 배열 선언하기) for(N의 개수만큼 반복하기) { A 배열 저장하기 } A 배열 정렬하기 for(M의 개수만큼 반복하기) { target(찾아야 하는 수) start(시작 인덱스) end(종료 인덱스) while(시작 인덱스 target) { 종료 인덱스 ..
✔ 이진 탐색 이진 탐색이란? 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음 시간 복잡도는 O(logN) 원하는 데이터를 찾을 때 사용하는 가장 일반적인 알고리즘 구현 및 원리가 비교적 간단하므로 많은 코딩 테스트에서 부분 문제로 요구하는 영역 이진 탐색 과정 현재 데이터의 중앙값을 선택 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터를 선택 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터를 선택 위 과정을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료 더보기 Do it! 알고리즘 코딩테스트 with JAVA https://inf.run/w9Tn
✔ 미로 탐색 [백준 2178] 문제 분석하기 N, M의 최대 데이터의 크기가 100으로 매우 작기 때문에 시간 제한은 별도로 생각하지 않아도 됨 지나야 하는 칸 수의 최솟값을 찾아야하므로 BFS를 이용해 완전 탐색을 진행하며 몇 번째 깊이에서 원하는 값을 찾을 수 있는지 구함 BFS는 해당 깊이에서 갈 수 있는 노드 탐색을 마친 후 다음 깊이로 넘어가기 때문에 적합 손으로 풀어보기 시작 위치인 (1, 1)에서 BFS를 실행하여 상, 하, 좌, 우 네 방향을 보며 인접한 칸을 살펴봄 인접한 칸의 숫자가 1이면서 아직 방문하지 않았다면 큐에 삽입 이때 방문한 노드의 배열의 값을 깊이 + 1로 업데이트 종료 시점 (N, M)에서 BFS를 종료하여 깊이를 출력 슈도코드 작성하기 dx, dy (상하좌우를 탐색하..
✔ 너비 우선 탐색 너비 우선 탐색이란? 그래프 완전 탐색 기법 중 하나 시작 노드에서 출발하여 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘 큐 자료구조를 이용하여 구현이 가능 (FIFO) V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E) 목표 노드에 도착하는 경로가 여러 개일때의 최단 경로를 보장할 때 사용 너비 우선 탐색 과정 BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 방문 배열 초기화하기 시작 노드 큐에 삽입하기 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 poll을 수행하여 노드 꺼내기 꺼낸 노드를 탐색 순서에 기입하..
✔ 연결 요소의 개수 [백준 11724] 문제 분석하기 노드의 최대 개수가 1000이므로 시간 복잡도 N² 이하의 알고리즘을 모두 사용할 수 있음 연결 요소는 엣지로 연결된 노드의 집합이며, 한 번의 DFS가 끝날 때까지 탐색한 모든 노드의 집합을 하나의 연결 요소로 판단 손으로 풀어보기 그래프를 인접 리스트로 저장하고 방문 배열도 초기화 이때, 방향이 없는 그래프이므로 양쪽 방향으로 엣지를 모두 저장함 임의의 시작점인 1에서 DFS를 수행 아직 방문하지 않은 노드 중 시작점을 다시 정해 탐색을 진행 모든 노드를 방문한 후 전체 탐색을 종료 총 DFS의 횟수가 연결 요소의 개수가 되게 됨 만약 그래프가 모두 연결되어 있었다면 DFS는 1번 실행되게 됨 슈도코드 작성하기 n(노드 개수) m(에지 개수) A..
✔ 깊이 우선 탐색 깊이 우선 탐색이란? 그래프 완전 탐색 기법 중 하나 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘 재귀 함수 또는 스택 자료구조를 이용하여 구현이 가능 (FILO) V는 노드 수, E는 엣지 수일때, 시간 복잡도는 O(V + E) 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로에 유의 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상정렬에 응용 깊이 우선 탐색 과정 DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 인접 리스트로 그래프 표현하기 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 방문 배열 초기화하기 시작 노드 스택에 삽입하기 스택에서 노드를 꺼낸..
✔ 기수 정렬 기수 정렬이란? 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식 값을 비교하지 않는 특이한 정렬 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표함 (0 ~ 9) 시간 복잡도는 O(kN)으로, 여기서 k는 데이터의 자릿수 시간 복잡도가 가장 짧은 정렬이므로, 정렬해야 하는 데이터의 개수가 너무 많을 시 사용 기수 정렬 과정 일의 자릿수를 기준으로 배열 원소를 큐에 집어넣음 0번째 큐부터 9번째 큐까지 pop을 진행하여 일의 자릿수를 기준으로 정렬된 데이터를 꺼냄 이어서 십의 자릿수를 기준으로 같은 과정을 진행 십의 자릿수에서 같은 자릿수일 때, 일의 자릿수가 더 작은 데이터가 큐에 먼저 들어가게 되어 오름차순 정렬이 가능..
