Hi/Algorithm(9)
-
[BOJ] Queue, DeQue/ 19단계
1 18258 큐 2 성공 7886 26220 30.958% 큐의 개념을 익히고 실습하는 문제. 연산 당 시간 복잡도가 O(1)이어야 한다는 점에 유의하세요. def push(num) : list.append(num) def pop() : if len(list) != 0 : print(list.popleft()) else : print(-1) def size() : print(len(list)) def empty() : if len(list) != 0 : print(0) else : print(1) def front() : if len(list) != 0 : print(list[0]) else : print(-1) def back() : if len(list) != 0 : print(list[-1]) e..
2021.08.08 -
[BOJ] Stack / 18단계
1 10828 스택 성공 41369 108817 38.494% 스택의 개념을 익히고 실습하는 문제 def push(num): arrayList.append(num) def pop() : if len(arrayList) == 0 : print(-1) else : print(arrayList.pop()) def size() : print(len(arrayList)) def empty() : if len(arrayList) == 0 : print(1) else : print(0) def top() : if len(arrayList) == 0 : print(-1) else : print(arrayList[-1]) import sys arrayList = [] T = int(input()) for i in ran..
2021.07.13 -
[BOJ] 정수론 및 조합론 / 17단계
자바로만 풀다가 파이썬 공부할겸 이번 단계에서는 파이썬으로만 풀었습니다. 1 5086 배수와 약수 성공출처다국어분류 7239 10516 70.288% 배수와 약수를 배우는 문제 def test(num01, num02) : if num02 % num01 == 0 : print("factor") elif num01 % num02 == 0: print("multiple") else : print("neither") while True : number01, number02 = map(int, input().split()) if number02 == 0 and number01==0 : break test(number01, number02) 2 1037 약수 성공분류 12488 25527 49.747% 약수의 성질..
2021.05.24 -
[BOJ] Greedy Algorithm / 16단계
1 11047 동전 0 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer bd = new StringTokenizer(bfr.readLine()); int T = Integer.parseInt(bd.nextToken()); int money = Integer.parseInt(bd.nextT..
2021.05.24 -
[BOJ] dynamic programming / 14단계
1 1003 피보나치 함수 단순 재귀로 피보나치 수를 구하면 왜 느릴까요? 함수 호출의 개수가 기하급수적으로 늘어나기 때문입니다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); int T = Integer.parseInt(bfr.readLine()); for(int i=0; i
2021.03.19 -
[BOJ] 15단계 / Greedy Algorithms
1 11047 동전 0 동전의 조건이 특별해서 동적 프로그래밍보다 빠르게 답을 찾을 수 있는 문제 import java.io.*; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ BufferedReader bfr = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer bd = new StringTokenizer(bfr.readLine()); int T = Integer.parseInt(bd.nextToken()); int money = Integer.parseInt(bd.nextT..
2021.03.14 -
동적계획법(Dynamic Programming) / Memoization
-동적계획법 (dynamic programming) 복잡한 문제를 간단한 여러개의 문제로 나누어서 푸는 방법. 부분문제반복과 최적부분구조를 가지고있는 알고리즘을 일반적인 방법보다 더 적은 시간내에 풀 때 사용. 문제를 여러개의 하위 문제(subproblem)로 나누어 품. 이 하위문제들을 결합하여 최종적인 문제에 도달하는 것. 메모이제이션(memoization) 컴퓨터 프로그램이 동일한 계산을 반복할 때, 이전에 계산한 값은 메모리에 저장해서 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술. 동적 계획법의 핵심 기술. 처음 방문하는 재귀문제면 계산을 통해 얻은 값을 메모리에 저장, 이 후 재방문을 하면 계산하지 않고 저장 된 값 사용. ex) import java.util.Sc..
2021.03.05 -
[BOJ] BackTracking /13단계
13 백트래킹 모든 경우를 탐색하는 백트래킹 알고리즘을 배워 봅시다. 1 15649 N과 M (1) 백트래킹 입문 문제 1 import java.util.Scanner; public class Main { public static int[] array; public static boolean[] visit; //방문했는지 확인. default = False public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); int M = scan.nextInt(); array = new int[M]; visit = new boolean[N]; dfs(N, M, 0); } public st..
2021.02.24 -
Backtracking
백트래킹(=퇴각검색) , 일종의 트리 탐색 알고리즘.해를 찾아가는 중에 막히면 다시 이전으로 돌아가서 해를 찾아가는 기법으로, 최적화 문제와 결정 문제를 풀 때 사용. 더보기- 깊이우선탐색 (Depth First Search, DFS)- 너비우선탐색 (Breadth First Search, BFS) - 최선우선탐색 (Best First Search/Heuristic Search) 모든 경우의 수를 검색 > DFS.트리의 깊이가 무한대이면 BFS DFS는 가능한 모든 경로를 탐색함. 일일이 하나씩 체크해보면서 노가다하는 탐색임.백트래킹은 DFS 방식과 비슷한데, DFS처럼 해를 찾아가는 중에, 다음에 갈 경로로 하면 해가 절대 안나올것 같으면 그 경로는 가지않고 되돌아감.이렇게 조건을 설정해서 안가는 경로..
2021.02.19