알고리즘공부

- 알고리즘 분류 : 다이나믹 프로그래밍, Bottom-Up 방식 - 사용 언어 : JAVA - 문제 요점 3잔 연속으로 마시는 것 금지 현재 잔으로부터 이전 3번 째 잔까지만 확인 3번 째 잔부터 아래 3개의 항목 중 값이 큰 항목으로 적용 현재 잔 안마시기 2번째 전의 잔까지 마셨던 거 + 현재 잔 마시기 3번째 잔의 전까지 마셨던 거 + 이전 잔 마시기 + 현재 잔 마시기) 포도주의 잔 갯수는 1이상이므로, d[2] 계산식을 조건에 두어 처리 소스 설명은 주석을 참고해주세요. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static..

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 1. 1로 만들기 import java.util.Scanner; public class Main { // 30000까지 포함이므로 30000+1하여 선언 public static int[] d = new int[30001]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); sc.close(); // 다이나믹 프로그래밍 (Bottom-up 방식) for (int i = 2; i

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 다이나믹 프로그래밍(Dynamic Programming) 1. 피보나치 수열을 재귀함수로 구현 public class Main { public static void main(String[] args) { // TODO Auto-generated method stub int result = fibonacci(4); System.out.println(result); } static int fibonacci(int num){ if(num == 1 || num == 2) { return 1; } return fibonacci(num-1) + fibonacci(num-2); } } 위처럼 재귀함수로 구현한 경우, ..

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 순차 탐색(Sequential Search) - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에 있는 데이터를 하나씩 확인하는 방법 public class Main { public static void main(String[] args) { // TODO Auto-generated method stub System.out.print("문자열 갯수와 찾을 문자열을 입력 : "); Scanner sc = new Scanner(System.in); String temp = sc.nextLine(); // 문자열 갯수 int N = Integer.parseInt(temp.split(" ")[0]); // 찾을 ..

이 포스팅에서 작성하는 내용은 이것이 취업을 위한 코딩테스트다 (나동빈 지음) 에서 발췌하였습니다. 정렬(Sorting) - 정렬 : 데이터를 특정한 기준에 따라서 순서대로 나열하는 것 - 정렬을 잘 터득하면 이진 탐색(Binary Search)가 가능하니 기초를 잘 잡아야 한다. 선택 정렬(Selction Sort) - 데이터가 무작위로 여러개 있을 때, 가장 작은 데이터와 맨 앞에 있는 데이터를 바꾸고 그 다음 작은 데이터를 앞에서 두번 째 데이터와 바꾸는 과정을 반복하는 알고리즘. - '매번 가장 작은 것을 선택하는 알고리즘' - 시간복잡도 : O(N2) public class Main { public static void main(String[] args) { // 선택 정렬 이용. int[] a..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { // 그래프 변수 public static int[][] graph; // 방문 체크용 변수 public static boolean[][] visited; // 그래프 크기 변수 public static int N; // 이동할 네 가지 방향 정의 (상, 하, 좌, 우) public static int[] dnum1 = {-1, 1, 0, 0}; public static int[] dnum2 = {0, 0, -1, 1}; public static void ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; class Node{ private int num1; private int num2; public Node(int num1, int num2) { this.num1 = num1; this.num2 = num2; } public int getNum1() { return this.num1; } public int getNum2() { return this.num2; } } public cla..

그래프를 인접리스트로 표현 import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { // 그래프 변수(인접리스트 이용) public static ArrayList graph = new ArrayList(); public static int N,M,V; // 방문 체크 변수 public static boolean[] visited; // DFS 함수 public static void DFS(int num) { // 현재 노드 번호 방문 처리 visited[num] = true; Syst..