공부 !/Algorithm
-
알고리즘은 순조부 .. Java로 구현해보자 !공부 !/Algorithm 2022. 8. 20. 18:28
순조부 순조부란 순열, 조합, 부분집합을 의미하는데 대다수의 알고리즘의 풀이는 순열, 조합과 부분조합으로 가능하다 ! 본 게시글은 이전의 파이썬으로 알고리즘을 정리하던 것과 달리 자바를 기준으로 코드 예시를 들려고 한다 ! 주언어를 드디어 .. 자바로 바꾸었기 때문이다 후후 순열 nPr 서로 다른 n개 중에 순서를 고려하여 r 개를 뽑는 것으로 예시로는 반장과 부반장 뽑기, 1,2,3 등 선물 추첨하기, 급식 받는 순서 정하기 등이 있다 순열은 순서를 고려하기 때문에 숫자를 사용하기 전에 해당 숫자가 사용된 적 있는지에 대한 확인이 필요하다 ! //순열 : 1부터 n 까지 순서를 고려하여 r 개를 뽑는 경우 public class Permutation { static int N, R; static int..
-
탐욕 알고리즘 ( Greedy Algorithm )공부 !/Algorithm 2022. 3. 27. 10:42
Greedy Algorithm 그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘이라고도 한다 이름에서 알 수 있듯이 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다 정렬이나 최단경로 등의 알고리즘 유형은 알고리즘의 사용 방법을 정확히 알아야 하지만 그리디는 단순하면서 강력한 해결법이기 때문에 딱히 그렇지 않다 ! 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로' '가장 작은 순서대로' 같은 힌트를 잘 캐치하면 된다 ! 그리디 알고리즘 문제는 주로 정렬 알고리즘과 함께 출제된다 대표적인 거스름돈 ! 거스름돈으로 500원, 100원, 50원, 10원짜리 동전이 무수히 존재한다고 가정한다 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 ..
-
Kruskal Algorithm 크루스칼 알고리즘 ?!공부 !/Algorithm 2022. 3. 22. 14:12
Kruskal Algorithm 크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다 다시 말해 최소비용 신장트리를 만들기 위한 대표적인 알고리즘 ! 프로그래머스 섬 연결하기 문제를 풀다가 개념을 정리한다 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr 노드와 간선 노드 = 정점 = 도시 를 의미하며 동그라미에 해당하는 부분이고 간선 = 거리 = 비용 을 의미하며 선에 해당하는 부분이다 예시로 살펴보면 아래 그래프는 노드가 4개 간선이 5개 이다 핵심개념 간선을 거리가 짧은..
-
Complexity 복잡도 !공부 !/Algorithm 2022. 1. 13. 17:38
복잡도란 ? 복잡도는 알고리즘의 성능을 나타내는 척도 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지 알고리즘을 위해 필요한 연산의 횟수는 시간 복잡도와 연관있으며 알고리즘을 위해 필요한 메모리의 양은 공강 복잡도와 연관있다 ! 시간복잡도 알고리즘 문제에 명시된 시간제한과 연관되며 작성한 프로그램이 모든 입력을 받아 이를 처리하고 실행 결과를 출력하는데까지 걸리는 시간을 의미한다 시간복잡도 표현 빅오 표기법 (Big - O) 를 사용한다 가장 빠르게 증가하는 항만을 고려하는 표기법이다 아래 예제의 연산 횟수는 데이터의 개수 n 에 비례한다 소스 코드에서 가장 영향력이 큰 부분은 n 에 비례..