전체 글8 [Algorithm] 완전탐색 - 순열 순열이란 ? 순열이란 서로 다룬 n개의 원소 중 r개를 순서 있게 일렬로 나열하는 경우의 수이다. 예) 주사위를 2번 던졌을 때 서로 다른 숫자가 순서 있게 나오는 경우의 수 순열 특징 ? 순열의 특징 몇 가지를 알아보자. 순열은 선택에 중복 없이 순서 있게 결과를 가져온다. 매 자리마다 모든 원소를 확인한다. 중복 여부를 위해 방문 배열을 사용한다. 대표적인 구현 방법은 재귀 구현이다. 재귀의 깊이는 선택된 원소의 개수와 일치한다. 순열 구현 순서? 재귀의 Stack Overflow를 주의하면서 아래와 같이 순서를 잘 따르자. 재귀를 호출하며, 깊이 정도를 전달한다. 이때 깊이는 선택한 원소의 개수와 일치한다. 깊이 정도로 원소를 다 선택했는지 확인한다. 원소를 다 선택했다면 원하는 동작 후 메서드를 .. 2023. 8. 8. [Algorithm] 시간복잡도 문제 시간복잡도 문제 풀기 주어진 문제 또는 코드에서 시간복잡도를 간단하게 구해보자. 문제 주어진 두 자연수를 더하기 : 3번 ~ 4번 1부터 N까지 2의 배수를 찾기 : N번 이상 책을 꺼내는데 1초의 시간이 소요된다. 원하는 책을 찾는 데 걸리는 시간 : N초 책에 번호가 붙여져 있고, 순서대로 꼳혀있는 경우 찾는 데 걸리는 시간 : log N초 주어진 숫자들을 정렬하기 : NlogN번 주어진 숫자들에서 서로 다른 위치의 요소 합이 특정 값이 되는 경우의 수 구하기 : N번 주어진 수가 제곱수인지 구하기 : logN번 1~N까지 수 중에서 가장 큰 2의 거듭제곱 수 구하기 : logN번 코드 public static int N; public static int nums[]; public static boo.. 2023. 8. 8. [Algorithm] 알고리즘 성능 공간복잡도란 ? 공간복잡도란 주어진 문제를 해결하는 데 사용되는 공간의 상관관계이다. 대부분의 문제들은 128MB, 256MB, 512MB 내의 공간복잡도를 조건으로 주어진다. 공간복잡도 계산 ? 정수 타입의 int 를 기준으로 문제에서 사용 가능한 공간을 대략적으로 측정해 보았다. 128MB : 공간 3300개 256MB : 공간 6600개 512MB : 공간 1.2억개 알아둔다면 배열을 사용하거나 다른 자료형을 사용할 때 시간복잡도와의 Trade-off 관계 계산에 유용하다. 시간복잡도란 ? 시간복잡도란 주어진 문제를 해결하는 데 걸리는 시간의 상관관계이다. 대부분의 문제들은 1초, 2초 내의 시간복잡도를 조건으로 주어진다. 시간복잡도 특징 ? 시간복잡도의 시간은 컴퓨터의 연산 횟수를 뜻하며, 아래에.. 2023. 8. 8. [Algorithm] 알고리즘 기초 알고리즘이란 ? 알고리즘이란 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합이다. 좋은 알고리즘을 만들어내고 문제를 잘 해결하기 위해서는 구현력, 이론 및 지식, 응용력이 필요하다. 알고리즘의 조건 ? 알고리즘의 조건은 크게 5가지가 존재한다. 정밀성 : 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 입출력 : 입력을 받아들이고, 답으로 출력 가능해야 한다. 유한성 : 특정 수의 작업 이후 정지해야 한다. 일반성 : 정의된 입력들에 적용이 가능해야 한다. 알고리즘의 성능 ? 알고리즘의 성능을 평가하는데 크게 두 가지의 기준이 존재한다. 시간복잡도 : 주어진 문제를 해결하는 데 걸리는 시간을 측정한 것 공간복잡도 : 주어진 문제를 해결하는 데 사용되는 .. 2023. 8. 7. 이전 1 2 다음
