본문 바로가기

Algorithm3

[인터뷰] 자주 사용되는 코딩 패턴 안녕하세요, 인터뷰에서 자주 나오거나 사용되는 20가지 코딩 패턴에 대해 자세히 설명하겠습니다. 1. Two Pointers - 투 포인터 투 포인터 알고리즘(기법)은 말 그대로 두 개의 포인터를 이용해 문제를 해결하는 알고리즘을 뜻합니다. 보통 특정 조건을 만족하는 배열 내의 쌍이나 배열을 찾아야 할 때 또는 정렬된 배열에서 특정 요소를 찾을 때 사용됩니다. DSA: Array, String, LinkedList 문제를 해결하는 예시 1. 정렬된 배열이나 정렬되지 않은 배열에서 목표 합계를 이루는 숫자 쌍을 찾기 입력: [3,5,2,8,11], 목표 합계 = 10 출력: [2, 8] 자바 코드 import java.util.Arrays; public class TwoPointerSum { public .. 2024. 4. 16.
88. Merge Sorted Array 다음과 같은 문제는 두 개의 졍렬된 배열을 하나의 정렬된 배열로 합치는 작업을 수행하는 것입니다. 문제를 풀기 위한 접근 방법은 다음과 같습니다. 1. 두 배열의 끝부터 시작합니다. 즉, 배열의 가장 큰 값을 가리키는 포인터를 각각 두 배열에 대해 설정합니다. 2. 한 배열에서 다른 배열로 원소를 복사하면서 합칩니다. 큰 값을 가진 원소를 결과 배열의 끝에 넣어주면서 포인터를 이동합니다. 3. 만약 두 배열 중 하나의 배열을 모두 처리하면, 남은 원소는 이미 결과 배열의 올바른 위치에 있으므로 추가 작업이 필요하지 않습니다. 이 솔류션의 시간복잡도는 O(m+n) 병합을 위해 상수 공간을 사용합니다. O(1) Java로 푸는 방법: class Solution { public void merge(int[] .. 2023. 9. 15.
버블 정렬 - 알고리즘 버블 정렬 - Bubble Sort 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘 정렬 과정 5,3,7,9,1 원소들을 배열에 추가하고 버블 정렬 해보겠습니다 1회전 5,3,7,9,1 2회전 3,5,1,7,9 3회전 3,1,5,7,9 4회전 1,3,5,7,9 알고리즘 분석 비교 횟수 -> 버블 정렬은 한번의 순화를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝납니다. 위의 예제에서는 총 원소 개수가 5개 이므로, 4+3+2+1 = 10번 비교하게 됩니다. 이를 수식으로 일반화 시키면 다음과 같습니다. 따라서 평균적으로 O(n^2)의 시간복잡도를 가지게 됩니다 슈도코드 자바 소스코드: public class BubbleSor.. 2022. 9. 6.

티스토리툴바