Algorithm22 Sorting Algorithms 재밌는 소팅 알고리즘 영상 퍼왔어요~S2 우하하 https://youtu.be/kPRA0W1kECg 2023. 4. 3. [1053] 팰린드롬 공장(작성중) 문제 팰린드롬이란, 앞에서부터 읽었을 때와, 뒤에서부터 읽었을 때가 같은 문자열이다. 모든 문자열이 팰린드롬이 아니기 때문에 다음과 같은 4가지 연산으로 보통 문자열을 팰린드롬으로 만든다. 문자열의 어떤 위치에 어떤 문자를 삽입 (시작과 끝도 가능) 어떤 위치에 있는 문자를 삭제 어떤 위치에 있는 문자를 교환 서로 다른 문자를 교환 1, 2, 3번 연산은 마음껏 사용할 수 있지만, 마지막 연산은 많아야 한 번 사용할 수 있다. 문자열이 주어졌을 때, 팰린드롬으로 만들기 위해 필요한 연산의 최솟값을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 문자열이 주어진다. 영어 소문자로만 이루어져 있고, 길이는 최대 50이다. 출력 첫째 줄에 문제의 정답을 출력한다. 예시 babacvabba //2 abba //.. 2022. 8. 2. 순열,중복순열/조합,중복조합 구현 순열(Permutation) 요소 n개 중 r개를 뽑아 정렬하는 경우의 수로 요소의 순서를 구분한다. e.g. [1,2]와 [2,1] 은 순서가 다르기 때문에 다른 경우의 수로 판단 구현 pubilc class Solution{ public static void permutation(int arr[],int[] out,boolean[] visited,int depth,int r){ if(depth==r){ for(int num:out) System.out.print(num); System.out.println(); return; } for(int i =0; i 2022. 8. 1. Greedy 개요 그리디 알고리즘은 매 선택에서 현재 당장 최적인 답을 선택하여 적합한 결과를 도출하도록 한다. 다시 말해 현재 조건에서 최적의 선택을 했다면 더 이상 다른 가능 케이스는 검증하지 않는 것이다. 그 결과 그리디 알고리즘은 전체에서 최적값을 보장할 수 없다. 그럼에도 불구하고 그리디 알고리즘은 처리 속도가 매우 빠르기 때문에 특정 조건을 만족할 경우 자주 사용될 수 있다. 최적의 해를 보장하는 조건 탐욕 선택 속성(Greedy Choice Property) 이전의 선택이 이후의 선택에 영향을 주지 않아야 한다. 최적 부분 구조(Optimal Substructure) 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 한다. 2022. 7. 28. 우선순위 큐(Priority Queue) 개요 우선순위 큐는 일반적인 큐의 구조를 가지지만 결정된 우선순위에 따라 데이터를 꺼낼 수 있다. 일반적으로 Heap을 이용하여 구현하며 이진트리 구조로 구성되어있다. 데이터를 삽입할 때 우선순위를 기준으로 최대 혹은 최소 힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다. 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행된다. 우선순위 큐 사용법 Priority Queue 선언 import java.util.PriorityQueue; //우선순위 : 낮은 숫자순 PriorityQueue q1 = new PriorityQueue(); //우선순위 : 높은 숫자순 PriorityQueue q2 = new Priorit.. 2022. 7. 26. Dynamic Programming 개요 동적 계획법(DP)은 하나의 큰 문제를 작은 문제로 나누어서 그 결과를 저장 후 다시 재활용하는 방식으로 특정된 알고리즘이 아니라 하나의 문제 해결 방법론이며, 아래 조건을 만족할 때 사용할 수 있다. 최적 부분 구조(Optomal Substructure) 겹치는 부분 문제(Overlapping Subproblems) 동작 원리 DP는 일반적인 재귀 방식과 매우 유사하다. 만약 피보나치 수열을 재귀 방식으로 푼다면 작은 문제들이 여러번 반복되어 비효율적인 계산이 될 수 있지만 한 번 구한 작은 문제의 결과 값을 저장하여 재사용한다면 앞서 계산된 값을 다시 반복할 필요가 없어 보다 더 효율적으로 문제를 해결할 수 있다. 시간복잡도 기준 O(n^2) -> O(f(n))으로 개선 가능하다.(문제 별 상이.. 2022. 7. 20. 이전 1 2 3 4 다음
