본문 바로가기

Algorithms

 (17)
[Algorithms] Binary Tree Search Binary Tree 비선형 자료구조이다. 선형자료의 대표적인 것으로는 stack , queue가 있다. 정렬된 배열 또는 리스트에 적합한 고속 탐색 방법이다. 이번에는 실질적으로 이진트리를 탐색하는 방법을 알아보도록 하겠다. 🖛 데이터의 삽입이나 삭제가 빈번할 시에는 적합하지 않고 주로 고정된 데이터에 대한 탐섹에 적합하다. 따라서 이진 탐색의 시간 복잡도는 O(log n)이 된다. 전위 순회 P-> L -> R 순으로 탐색한다. 중위 순회 L -> P -> R 순으로 탐색한다. 후위 순회 L -> R -> P 순으로 탐색한다. public class BinarySearch { static int[] arr = {1, 3, 5, 7, 8, 10, 20, 35, 99, 100}; public static..
[Algorithms] 백준 11727번 2x타일링 import java.util.Scanner; /* * 점화식 : meme[i] = mem[i-1]+2*mem[i-2]; * */ public class boj_11726_2x타일링 { private static int N; private static long [] mem; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); mem = new long [N+1]; if(N>1) { mem[0]=0; mem[1] = 1; mem[2]=3; } else { mem[0]=0;mem[1]=1; } for(int i =3; i
[Algorithms] palindrome 회문 단순코드 회문(완전탐색) 접근 방법 문자열의 길이를 N이라고 했을때, 앞에서 읽거나 뒤에서 읽거나 같은 문자열을 회문이라한다. 1. 2n-1개의 문자열을 모두 탐색해서 각각이 회문이 되는지 탐색 -> 앞의n개의 문자가 일치하는것 찾기 이 방법은 구현은 쉽지만 시간 제한이 있을때 시간초과가 날 확률이 높다 2. 문자열에 추가할 n-1개의 문자열을 모두 탐색, 각각의 것이 회문이 되느지 확인하기 n번째 문자가 고정되어 1번보다는 좋은 접근 방법이지만 문자열의 길이가 10000이면 9999번을 탐색하게된다. 3. 2n-1의 회문을 완전탐색하고 앞의 n개의 문자가 일치하는것을 찾기 회문을 모두 찾는것은 힘들지만 모두 찾으면 n개의 문자가 ㅇ리치하는지 쉽게 확인할 수 있으며 그 중에서 문자열의 길이가 가장 짧은 것을 선택..
[Algorithms] 백준 11726 2XN 타일링 Dynamic programming 사용 n =1일때 방법 1개 n =2일때 방법 2개 n =3일때 방법 3개 n =4일때 방법 5개 n =5일때 방법 8개 n =6일때 방법 13개 이처럼 dp[n] = dp[n-2]+ dp[n-1] 이다. 이를 활용해서 문제 해결 package boj; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class boj_11726_2xn타일링 { private static int N; private static int[] dp; public static void main(String[] args) throws Exception { Buffer..
[Algorithms] 2차원 배열 순회 /* * 행 우선 순회 * -----------> * -----------> * -----------> * 순서 */ int i; int j; map = new int [10][15]; for( i =0; i
[Algorithms] 백준 비밀번호 찾기 아이디어 hashmap을 사용하여 키값을 통해서 value를 찾아 출력할 수 있다. package boj; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class boj17219_비밀번호찾기 { private static int N; private static int M; public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..
[Algorithms] 백준 7662 이중 우선순위큐 개념 PriorityQueue : 자료형을 사용했을때 오름차순으로 자동 정렬된다. 아이디어 1.내림차순 큐, 오름차순 큐 두개 만들기 2. D -1 일때, D 1일때 각각 제거 3. qMax 와 qMin에서 각각 중복 제거 해주기 다른 아이디어 덱 사용하거나 트리맵을 사용해서 할 수 있을것 같다. 문제점 테케는 맞는데 틀렸습니다가 떠서 아직 해결 못했습니다. package boj; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Comparator; import java.util.PriorityQueue; import java.util.StringTokenizer; public class boj7662_이중..
[Algorithms] 백준 10816 숫자카드 해쉬맵 사용해보려고 풀어봤던 문제 Idea 해쉬맵은 키가 distinct하기 때문에 키별로 value를 +1씩 증가하면서 입력 받음 M배열로 입력받르떼 키값을 찾아 있으면 value를 return, 아니면 0return 하여 코드작성 문제점 시간초과가나서 해쉬맵으로 풀면 안되는줄 알았는데 StringBuilder를 사용해서 풀었더니 해결됨 package boj; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class boj10816_숫자카드2 { private static int N; private static in..

티스토리툴바