본문 바로가기

분류 전체보기119

[너비 우선 탐색 BFS] 백준 2178 [너비 우선 탐색 BFS] 도 그래프를 완전 탐색하는 방법 중 하나로 시작 노드에서 출발해 시작노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘(FIFO) 입니다. 선입선출 방식으로 탐색하므로 큐를 이용해 구현합니다. 너비 우선 탐색의 핵심 이론 1.BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화 하기 (DFS와 동일하지만 스택대신 큐를 사용한다는 점에서 다름) 2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기 3. 큐 자료구조에 값이 없을 때 까지 반복 백준 2178 미로 찾기 문제에 적용해보기 public class 미로탐색 { static int[] dx = {0,1,0,-1}; static int[] dy = {1,0,-1,0}; //각각 위, 오른쪽,.. 2024. 2. 28.
[이진 탐색] 백준 1920 이진 탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘으로 시간 복잡도는 nlogn이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터 크기를 절반씩 줄이면서 대상을 찾는다. 탐색 방법 1. 데이터에서 중앙값(median)을 선택한다. 2. 중앙값>타깃 데이터 라면, 중앙값을 기준으로 왼쪽 데이터셋을 선택한다. 3. 반대인 경우라면 오른쪽 데이터셋을 선택한다. 4. 1~3을 반복하면서 중앙값 == 타깃 데이터를 찾는다. 더보기 내가 찾고자 하는 데이터 = 55 3 7 13 15 23 35 38 41 46 49 55 57 68 72 77 68 -> 오름차순으로 배열 되어있는 상태, 중앙값을 41로 설정 41과 55 비교 -> 55가 더 크므로 오른쪽 데이터 셋 선택 46 49 5.. 2024. 2. 28.
아틸러리를 활용한 스트레스 테스트 msa 프로젝트를 하며 배웠던 개념인데 복습을 하고자 아틸러리 공식 문서에서 제공해주는 예제를 참고해 다시 정리해보도록 하겠다. 따라서 재밌는 시도 한 번 해보시길~ (내 컴퓨터 내에서 일어나는 요청에 대한 테스트이므로 완벽히 신뢰할 수 있는 결과를 얻을 수는 없다. 이것을 감안하고 진행해야 한다 ㅜ.) 아틸러리를 사용하는 이유?? 논리적 문제가 없는데 하드웨어 제약으로 서비스가 중단된다면 좀 당황스러울 것 같다. 서버마다 cpu가 다르기 때문에 수용할 수 있는 인원의 수에 차이가 발생할 수 있고 미리 스트레스 테스트를 해서 예측할 수 있는 툴이 아틸러리이다. 이렇게 미리 부하 테스트를 하면 서버가 얼마큼의 트래픽을 수용할 수 있는지, 더 수용하려면 어떻게 로드밸런싱을 하면 좋을 지, 사양을 업그레이드할.. 2024. 2. 28.
[깊이 우선 탐색 DFS] 백준 11724 [깊이 우선 탐색 DFS]은 그래프 완전 탐색 기법 중 하나로 그래프의 시작 노드에서 출발해 탐색할 한 쪽 분기를 정해 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동해 다시 탐색하는 알고리즘이다. 깊이 우선 탐색은 실제 구현 시 재귀 함수를 이용하므로 스택 오버플로를 유의해야 한다! 깊이 우선 탐색은 단절점 찾기, 사이클 찾기, 위상 정렬 등에 응용하여 문제를 풀 수 있다. 깊이 우선 탐색의 핵심 이론 DFS는 한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 배열이 필요하며, 그래프는 인접 리스트로 표현하겠다. 그리고 DFS의 탐색 방식은 후입선출 특성을 가지므로 스택을 사용하여 설명하겠다. 1.DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기 원본 그래프를 인접리스.. 2024. 2. 27.
[삽입 정렬] & [퀵 정렬] & [병합 정렬] & [기수 정렬] 삽입 정렬이란? 이미 정렬된 데이터 범위에서 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식이다. 시간복잡도도 O(㎡)로 느린 편이지만 구현하기 쉽다! 선택 데이터는 현재 정렬된 데이터 범위내에서 정확한 위치에 삽입하는 것이 중요하다. 퀵 정렬이란? 기준값(피벗)을 선정해 해당 값보다는 작은 데이터와 큰 데이터로 분류하는 것을 반족해 정렬하는 방식이다. 기준값에 따라 시간 복잡도에 많은 영향을 미치고 평균 시간 복잡도(O(nlogn))이며 최악의 경우에는 시간 복잡도가 O(㎡)! -> 시간복잡도가 불규칙하며 운이 따르는 알고리즘임 ㅜ.ㅜ 따라서 피벗을 설정하는 것이 가장 중요하며 투 포인터(start, end)를 설정하여 피벗과 비교하며 정렬한다. 더보기 오름차순으로 정렬 42 32 24 6.. 2024. 2. 27.
[선택 정렬] 백준 1427 선택 정렬이란? 대상 데이터에서 최대나 최솟값을 갖는 데이터를 선택하는 정렬이다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도가 O(㎡)으로 효율적이지 않아 많이 사용하지는 않는다. 구현 방법은 최솟값 또는 최댓값을 찾고 남은 정렬에서 가장 앞에 있는 데이터와 swap하는 것을 반복하는 것이다. 예를 들어 최솟값을 기준으로 정렬할 때, 더보기 1 3 2 5 4 -> 1과 5 비교 -> 1이 더 작음 -> 그대로 둠 : 남은 정렬 3 2 5 4 1 3 2 5 4 -> 3과 2비교 -> 2가 더 작음 -> swap : 남은 정렬 3 5 4 1 2 3 5 4 -> 3과 5비교 -> 3이 더 작음 -> 그대로 둠 : 남은 정렬 5 4 1 2 3 5 4 -> 5와 4 비교 -> 4가 더 작음 -> swap 1.. 2024. 2. 27.

티스토리툴바