본문 바로가기

알고리즘/알고리즘 이론10

투 포인터 - 알고리즘 👩‍💻 투 포인터 (Two Pointers)배열에서 "두 개의 포인터"를 사용하여 원하는 결과를 얻는 방법 ✨ 두 개 포인터의 배치 방법같은 방향에서 시작 : 첫 번째 원소에 둘 다 배치서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있다!! ✏️ 투 포인터의 예시ex01) 아래 배열에서 부분합이 9가 되는 구간을 찾는 방법* 기존 단순 for 문 이용시 : 시간 복잡도 O(n^2)* 투 포인터 사용시 : 시간 복잡도 O(n) ✏️ Java 구현public class Main{ // 위의 예시를 기존의 2중 for문으로 풀었을 때 : O(n^2) pubic static int[] forLoop(int[] arr, int tar.. 2024. 7. 20.

이진 탐색 - 알고리즘 👩‍💻 이진 탐색 (Binary Search) 란?이진 탐색은 (= 이분 탐색) 정렬된 상태의 데이터에서 특정 값을 빠르게 탐색하는 방법이다.찾고자 하는 값과 데이터 중앙에 있는 값을 비교찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 ✏️ 시간 복잡도알고리즘 시간 복잡도 : O(logN) ✏️ 이진 탐색 과정* 데이터가 우선 정렬된 상태여야 이진 탐색 진행이 가능하다.찾고자 하는 데이터 x를 기준으로 mid 값과 비교하여 범위를 줄여나가며 찾아가는 방식이다. ✏️ 이진 탐색 구현 과정✨ 반복문 구조public class Main{ public static int binarySearch(int arr[], int target){.. 2024. 7. 20.

정렬 (Sort) - 알고리즘 👩‍💻 정렬이란?특정 값을 기준으로 데이터를 순서대로 배치하는 방법✨ 정렬의 종류 구현 난이도는 쉽지만, 속도는 느린 알고리즘버블 정렬삽입 정렬선택 정렬 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘합병 정렬 (Merge sort)힙 정렬퀵 정렬 (Quick Sort)트리 정렬하이브리드 정렬팀 정렬블록 병합 정렬인트로 정렬기타 정렬 알고리즘기수 정렬카운팅 정렬셀 정렬보고 정렬 1. 버블정렬 (Bubble Sort)인접한 데이터를 비교하며 자리를 바꾸는 방식알고리즘 복잡도 : O(n^2) 2. 삽입정렬 (Insertion Sort)앞의 데이터를 정렬해가면서 삽입 위치를 찾아 정렬하는 방식알고리즘 복잡도 : O(n^2)index0이 아닌 1부터 시작, 현재 index와 그 전 index들을 비교.. 2024. 6. 25.

Knapsack problem - Dynamic Program 중요한 알고리즘 세 가지중 하나인 Dynamic Program 의 유명한 예제인 백준 12865번 배낭문제를 풀어보았다. Knapsack problem은 주어진 무게 제한 안에서 각 아이템들의 무게와 가치를 조합하여 수 있는 최대 가치를 구하는 문제이다. 해당 문제를 Dynamic Program으로 접근하는데에는 이유가 있다.우선 단순 접근법으로 해당 문제를 푼다면 item 하나당 선택 또는 비선택의 경우를 고르게 되므로 총 2^n 이란 시간이 걸린다. Greedy Algorithm 으로 해당 문제를 접근한다면 어떤것을 greedy 전략으로 선택해야할지 골라야 하는데 value 값이 큰 것부터 선택하게 된다면 optimal한 solution을 가지지 못하는 경우가 생긴다.그렇다고 무게가 적은 것 부터 .. 2023. 5. 20.

이전 1 2 다음

티스토리툴바