Algorithm

[완전탐색] BOJ 15654 N과 M (5)

15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 1) 아이디어 N개의 숫자 중 중복없이 M개를 순서 있게 나열하는 문제이기 때문에 완전탐색의 순열 문제이다. 각 자리에서 재귀호출로 다음 자리로 올 수 있는 모든 경우의 수를 백트래킹으로 탐색하면 된다. 단, 중복을 허용하지 않으므로 visit[]으로 방문처리를 해서 방문안해본 경우만 탐색한다. 2) 시간복잡도 순열 문제이므로 O(N^M)인데 N과 M의 최댓값이 8 이므로 O(8^8) < 1억 3) 구현 // 언어 : JAVA , (성공/실패) : 1/0..

[자료구조] LinkedList

LinkedList 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식의 자료구조 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 데이터를 담고 있는 노드들이 연결되어 있고, 노드의 포인터가 이전 노드와 다음 노드와의 연결을 담당 Linked List 특징 ArrayList에 비해서 데이터의 추가나 삭제가 용이 미리 데이터 공간 할당하지 않아도 됨 ( 배열) 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어짐 배열은 index로 바로 찾음 -> 탐색, 정렬에 유리 연결을 위한 별도 데이터 공간 필요 → 저장공간 효율 떨어짐 LinkedList 직접 구현 class LinkedList { // head 노드 지정 public Node..

[Algorithm] 완전탐색 - 조합

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복없이 M개를 고르기 : 조합 백준 15652) N과 M (2) htt..

[Algorithm] 완전탐색 - 중복조합

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복을 허용하여 M개를 고르기 : 중복조합 백준 15652) N과 M (..

[자료구조] 배열 (Array), 큐(Queue), 스택(Stack)

배열 (Array) 같은 타입의 데이터를 순차적으로 저장하여 관리 index 번호로 빠른 데이터 접근이 가능 데이터 추가/삭제의 어려움 미리 최대 길이를 지정해야 하고 바꿀 수 없음 ArrayList 클래스로 배열 다루기 // int 형 데이터를 담을 수 있는 가변 길이의 배열 선언 ArrayList list1 = new ArrayList(); // 배열에 아이템 추가 시 add(아이템) 메서드 사용 list1.add(1); list1.add(2); // 배열에 특정 아이템을 읽을 시 get(인덱스번호) 메서드 사용 // (굳이 System.out.println() 을 사용하지 않아도 됨) list1.get(0) // 1 // 특정 인덱스에 해당하는 아이템 변경 시, set(인덱스번호, 변경할값) 메서드..

[Algorithm] 완전 탐색 - 순열

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 백준 15649) N과 M ..

[Algorithm] 완전 탐색 - 중복순열

류호석님의 패스트캠퍼스 강의 자료를 참고하여 정리한 글입니다. 출처 : https://github.com/rhs0266/FastCampus 완전 탐색 문제 해결을 위해 모든 경우를 전부 탐색하는 방법으로 정답을 무조건 구할 수 있다. 장점 : 부분 점수를 얻기 좋음 단점 : 모든 경우의 수를 전부 탐색하기에 시간 복잡도가 높음 완점 탐색 종류 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 N개중 중복없이 M개를 순서 있게 나열하기 : 순열 N개중 중복을 허용하여 M개를 고르기 : 중복조합 N개중 중복없이 M개를 고르기 : 조합 완전 탐색 문제 접근 시 고를 수 있는 값의 종류 파악 중복 여부 순서를 따지는 지 N개중 중복을 허용하여 M개를 순서 있게 나열하기 : 중복순열 백준 15651)..