자료구조와 알고리즘
-
재귀 - 백준 15655 N과 M (6) - 중복 없는 오름차순 조합자료구조와 알고리즘/문제풀기 2024. 4. 28. 15:30
N과 M (6) 시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB22723190351541884.408%문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열고른 수열은 오름차순이어야 한다.입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으로 증가하는 순서로 출력해야 한다.예제 입력 ..
-
재귀 - 백준(15654) N과 M(5) - 중복없는 오름차순 순열자료구조와 알고리즘/문제풀기 2024. 4. 16. 17:28
N과 M (5)시간 제한메모리 제한제출정답맞힌 사람정답 비율1 초512 MB37243273202185572.945%문제N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.N개의 자연수 중에서 M개를 고른 수열입력첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.수열은 사전 순으..
-
완전탐색 - 백준[2840] 행운의 바퀴자료구조와 알고리즘/문제풀기 2024. 4. 16. 13:38
import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main (String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); char[] ans = new char[N]; Arrays.fill(ans, '?'); int curIndex = 0; while (K-- > 0) { int backStep = sc.nextInt(); char backAlphabet = sc.next().charAt(0); int nextIndex = ((curIndex - backStep) % N + N) % ..
-
완전탐색 - 백준(10250) ACM 호텔자료구조와 알고리즘/문제풀기 2024. 4. 16. 13:14
- 풀이 import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int n = Integer.parseInt(br.readLine()); while (n-- > 0){ String[] input = br.readLine().split(" "); int h = Integer.parseInt(input[0]); int w = ..
-
완전탐색 - 백준 (10448) 유레카 문제자료구조와 알고리즘/문제풀기 2024. 4. 16. 12:49
- 풀이 import java.io.*; public class Main{ static boolean[] isEurekaNumber = new boolean[1001]; public static void main(String[] args) throws IOException{ int[] triangleNumber = new int[50]; int triagleCnt = 0; for(int i =1;;i++){ int number = i*(i+1)/2; if(number > 1000) break; triangleNumber[triagleCnt++] = number; } BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int ..
-
우선순위 큐와 힙자료구조와 알고리즘/자료구조 2023. 5. 18. 06:34
1. 우선순위 큐란 > 데이터가 삽입된 순서와 상관없이 우선순위가 높은 데이터가 먼저 나온다. > 데이터의 우선순위는 우선순위 큐를 구현하면서 임의로 설정하도록 한다. > 우선순위 큐는 배열, 연결리스트, 힙(heap)등을 이용하여 구현할 수 있는데 일반적으로 힙을 이용한다. 2. 힙 > 완전 이진 트리이다. > 부모노드와 자식노드간 대소관계가 있다. > 이진탐색트리와 달리 중복 값을 허용한다. 최대힙 :루트노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 말한다. 최소힙: 루트노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 말한다. 3. 힙의 구현 및 우선순위 큐 완성 - 힙의 데이터 저장: 새로운 데이터는 우선순위가 제일 낮다는 가정하에 마지막 위치에 저장 적절한 위치를 찾을 때 까지 ..
-
Tree - 수식 트리 (Expression Tree)자료구조와 알고리즘/자료구조 2023. 5. 16. 12:05
앞 서 만든 이진트리를 만드는 도구를 활용하여 이진트리 구조 중 하나인 수식트리를 만들어보자 1. 수식트리란? 중위,후위,전위 표기법과 같은 여러가지 표기법 중 하나로 메모리에 수식을 표기하는 방식이다. 루트 노드에 연산자를, 두 개의 자식노드에 피연산자를 두어 연산이 진행된다. 이를 그림으로 표기하면 위와 같다. 이러한 수식트리의 장점은 한번 트리를 완성해두면, 중위,후위,전위 표기법으로 쉽게 전환할 수 있다. 2. 구현 중위표기법을 바로 수식트리로 나타내는 것보다 중위표기법을 후위표기법으로 전환한 뒤에 수식트리로 나타내는 것이 간편하므로, 여기서는 후위표기법을 수식트리로 변환하는 과정만 보일 것이다. 수식트리를 표현하기 위한 도구 : 1. Stack, 2 BTree 헤더 #ifndef __EXPRES..
-
Tree - 이진 트리의 구현과 순회자료구조와 알고리즘/자료구조 2023. 5. 15. 22:48
1. 배열? 연결리스트? 이진트리는 배열로 구현할 수도 있고 연결리스트로 구현할 수 도 있다. 이때 트리가 완성 된 후 빈번한 탐색이 이루어지는 등 특정한 필요에 따라 배열로 구현할 수 있지만 (ex heap) 일단 연결리스트로 구현해 보자. 2. 이진 트리의 ADT BTreeNode* MakeBTreeNode(void) - 이진 트리 노드를 생성하여 그 주소 값을 반환 BTdata GetData(BtreeNode*bt) - 노드에 저장된 데이터를 반환 void SetData(BTreeNode*bt, BTdata data) - 노드에 데이터를 저장함 BTreeNode* GetLeftSubTree(BTreeNode* bt) - 왼쪽 서브트리의 주소를 반환 BTreeNode* GetRightSubTree(B..