BIcOding

import java.util.Arrays; import java.util.Scanner; /* 총 개수: N 뽑는 개수: R 순열과는 다르게 isSelected를 사용하지 않고, 재귀 내의 반복문의 시작점인 start를 변경해줌으로써 조합 형태의 경우의 수 구현 */ public class Combination { static int N, R, totalCnt; static int[] totals, selected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); totals = new int[N]; selected = new int[R]; for ..

import java.util.Arrays; import java.util.Scanner; /* 총 개수: N 뽑는 개수: R isSelected를 사용함으로써 사용 체크 및 순열의 형태의 경우의 수를 만들어냄 */ public class Permutation { static int N, R, totalCnt; static int[] totals, selected; static boolean[] isSelected; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); R = sc.nextInt(); totals = new int[N]; selected = new int[R]; isSel..

재귀 호출 [대표문제] 피보나치 수열 피보나치 수열 이전의 두 수 합을 다음 항으로 하는 수열 점화식 A0 = 0 A1 = 1 Ai = Ai-1 + Ai-2 (i >= 2)재귀함수를 사용한 피보나치 수열 수도 코드 /* fibo(n) if n < 2 : return n; else : return fibo(n-1) + fibo(n-2); */ 자바 코드1; 단점. 중복 호출이 매우 많음. 최적화 필요 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Java4150_피보나치수 { static BufferedReader bf = new BufferedReader(new ..

회의실 배정_그리디 기법 활용 문제 포인트 회의는 시작 시간과 종료 시간이 존재하며, 회의가 겹치는 회의는 동시에 열릴 수 없음 하나의 회의실을 공통으로 사용하고, 이를 예약하는 개념으로 생각 가능한 많은 회의가 열리기 위해서 회의를 어떻게 배정해야 할 지에 대해 생각하는 문제 활동 선택 문제_일반화 시작 시간과 종료 시간이 있는 n개의 활동들의 집합에서 서로 겹치지 않는 최대 갯수의 활동들의 집합 S를 구하는 문제 양립 가능한 활동들의 크기가 최대가 되는 S의 부분집합을 선택하는 문제 해결 포인트 종료 시간 순으로 활동들을 정렬한다. 종료 시간이 같다면, 시작 시간이 빠르던 늦던 혹은 회의 시간이 짧던 길던 하나의 회의밖에 올 수 없는 점이 중요한 포인트이다. 다른 포인트 빨리 시작하는 순으로 정렬 :..

위상 정렬 의미 방향이 존재하는 유향 그래프 내에서, 방향을 거스르지 않으면서 순서를 부여해서 탐색(방문)하는 방법 조건 및 특징 유향 그래프 Cycle이 존재하면 안된다. => cycle 판단도 동시에 가능하다는 말과도 같다 관계성이 있는 그룹 내에서만 순서를 지키면 된다. => 때문에 여러 순서 결과가 도출되는 경우가 많다. 위상 정렬의 목적 Cycle 여부 확인 탐색 순서 정렬 문제 예시 B 작업을 하기 위해서는 A 작업을 먼저 수행해야 한다. 대표: 백준2056 작업, https://www.acmicpc.net/problem/2056 BFS를 이용한 구현 1. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다. - 차수 : 정점에 연결된 간선 수 - 진입차수, 진출차수 : 유향 그래프에서의 차수..

재귀 함수 반복(Iteration)과 재귀(Recursion) 재귀 의미 자신을 정의하는데 그 내용안에 다시 자신을 포함하는 형태의 함수 반복과 재귀 반복과 재귀는 굉장히 유사함. 동일한 작업 형태로 더 작은 문제로 쪼갤 수 있으면 재귀 개념을 사용할 수 있음. 재귀 함수 내부 구분 기본 부분(basis part) => 기저 조건 유도 부분(indective part) => 재귀 파생 반복문 만들때 고려할 점 반복의 단위를 찾음 : 규칙을 찾는다. 재귀 함수 만들때 고려할 점 함수(메서드) 정의를 명확히 할 것 문제를 작은 단위로 쪼개보기. basis part를 찾을때까지 => 기저 조건 확인 함수가 자신의 작업을 수행하기 위해 결정하는 값을 매개변수로 지정 재귀 종류 선형 재귀 상황에 따라서 반복문으로..

알고리즘 성능 무엇이 좋은 알고리즘인가 정확성 : 얼마나 정확하게 동작하는가 작업량 : 얼마나 적은 연산으로 원하는 결과를 해결하는가 메모리 사용량 : 얼마나 적은 메모리를 사용하는가 단순성 : 얼마나 단순한가 최적성 : 더 이상 개선할 여지가 없는가(처음부터 고려할 사항은 아님)시간 복잡도, 공간 복잡도 시간 복잡도, 공간 복잡도 시간 복잡도 최선의 경우 빅 오메가 표기법 사용 최선일 경우 최소 이 시간이 걸림 최악의 경우 빅 오 표기법 사용 최악이어도 이 시간보다 덜 걸림. 우리가 말하는 일반적인 시간 복잡도는 빅 오 표기법 평균적인 경우 빅 세타 공간 복잡도 알고리즘 성능 java 연산 기준 작업략 기준 1억번의 연산은 1초라고 대충 기준 1초를 넘어서는 알고리즘은 피하기 재귀 호출 횟수 재귀 호출..

SW 문제 해결 문제 해결 과정 문제 읽고 이해 익숙한 용어로 문제를 재정의 어떻게 해결할지 재정의 계획 검증 프로그램 구현 어떻게 풀었는지 재검토 및 개선점 찾기 문제 해결 전략 주요 체크 단순한 방법으로 시작할 수 있는지 문제를 작은 문제로 분해할 수 있는지 뒤에서부터 생각해서 문제를 풀 수 있는지 정렬해서 문제를 풀 수 있는지 // TODO : 체크 사항 추가 및 체크 사항에 대한 대표 알고리즘 작성 필요