비밀일기

섹션 9동적 계획법(DP, 다이나믹 프로그램)복잡한 문제를 여러개의 간단한 문제로 분리하여 해결하는 것 point..큰 문제를 작은 문제로 나눌 수 있어야함작은 문제들의 결과값이 항상 같아야함작은 문제들을 최초의 한번만 계산하고 DP 테이블에 저장다시 같은 작은 문제가 발생했을 때 다시 계산하는 것이 아니라 테이블에 저장 된 값을 활용 ex(피보나치 수열) a(n+3)=a(n+1)+a(n+2)수열을 구하기 위해 모든 값을 계산하는게 아니라 점화식을 이용하여 계산함동적 계획법으로 풀이할 수 있는가?== 작은 문제로 나눌 수 있나? 값이 항상 같은가? 6번째 피보나치 수열의 값은 5번쨰 피보나치 수열의 값+4번쨰 피보나치 수열의 값수열의 값은 항상 같음 동적 계획법으로 풀이 가능하고 수열의 값은 항상 같은 ..

매서드동일한 구조의 기능을 여러개 구현하고자 할 떄 중복을 제거하기 위해 매서드(함수) 사용.수학에서 함수 개념을 차용해서 가져온 개념이다함수를 한번 정의해두면 재사용이 가능하다매서드는 함수의 한 유형이라 생각하면 된다 메서드 작성 방법  public static int 변수명 (파라미터 목록){           함수 내용...                                         } 매서드 선언과 매서드 본문으로 나눌 수 있음매개변수 목록에서는 매개변수들의 타입을 명시해준다 public: 다른 클래서에서 호출 가능한 매서드 라는 의미static: 객체를 생성하지 않고 호출 가능한 매서드라는 의미int: 반환 타입 정의add: 매서드의 이름. 이 이름으로 매서드를 호출 할 수 있다 매..

조합조합 자체로 코딩테스트에 많이 등장함점화식, 동적 계획법을 이해하는데 기초가 되는 내용임 순열: n개의 숫자에서 r개를 뽑아 나열하는 경우의 .조합: 순열과 다르게 순서를 고려하지 않음. 분모에 추가된 r!부분은 순서를 제거하는 역할.  조합의 점화식1. 특정 문제 가정    5개중에 3개 선택2. 모든 부분 문제가 해결된 상황이라 가정하고 지금 문제 생각    5를 선택했을 때->앞에서 2개의 수가 선택된 상황 4C2    5를 선택하지 않음-> 앞에서 3개의 수가 선택된 상황 4C3        따라서 5C3 = 4C3+4C23. 일반화 점화식 도출  백준 11051 이항계수: 이항식을 이항 정리로 전개했을 때 각 항의 계수이며, 주어진 크기의 (순서 없는) 조합의 가짓수이다.

보호되어 있는 글입니다.

배열 학생 수에 따라 같은 타입 변수를 여러개 선언하고 사용하는 문제 발생. 반복문으로 해결 가능?-> 반복문으로 변수 명을 선언할 수 없기 때문에 배열이 필요  배열의 선언과 생성 배열: 같은 타입의 변수를 사용하기 편하게 하나로 묶은 변수.int[] 변수 명변수 명 new int[num]  5칸 짜리 students 배열 변수 선언new는 새로 생성한다는 의미 int 형 배열 변수 student에는 배열을 담을 수 있음 숫자는 자동으로 0 할당, 부울 값은 거짓으로, 스트링은 null 값 자동으로 삽입 생성된 메모리의 참조값을 배열변수에 저장한다  배열에 접근할 때에는 인덱스를 이용해 배열에 접근한다. 배열은 0부터 시작한다.new int[5] 와같은 정수형 배열변수를 선언해주었을 경우에는 정수형 변..

트리 그래프의 특수한 형태로 노드와 엣지로 연결된다. 순환 구조가 없고 1개의 루트노드가 존재한다.  트리에서 임의의 두 노드를 이어주는 경로는 유일하다. 노드: 데이터의 인덱스와 값을 표현엣지:노드사이의 연결루트: 최상위 노드리프노드:최하위에 존재하는 노드자식노드: 두 노드 사이에서 하위노드에 해당하는 노드 tree 문제:1) 그래프 풀이   dfs, bfs 문제2) tree만을 위한 문제   이진트리, 세그먼트 트리,lca (최소 공통 조상)      1차원 배열로 트리를 표현      (자식으로 이동할 때는 index*2 or index*2+1 부모로 이동할 때는 index/2...) [백준 11725] 인접리스트 자료구조 사용일반적으로 dfs, bfs사용dfs를 사용해 쉽게 해결 가능 깊이우선 탐..

섹션 7-1 scanner system.out 을 통해 출력하였듯이 system.in을 통해서 입력을 받을 수 있음.하지만 매우 복잡하고 어렵기 때문에 자바에서 제공하는 scanner를 사용한다.  자바 라이브러리에서 제공하는 스캐너를 사용한다.Scanner scanner=new Scanner(System.in);  Snanner 스캐너 이름=new Scanner(System.in);String str=scanner.nextLine();nextLine 에서 L이 대문자임에 유의 sout에서  System.out.print("문자열을 입력");print와 println의 차이점은 줄바꿈 문자의 삽입 여부임.    실수와 정수의 입력 예제)만약 자료형을 다르게 입려받는다면 오류가 발생한다. 사용자로부터 입력..

섹션 6) 다익스트라에서 최소 신장 트리까지1.다익스트라 알고리즘시작 노드와 그 외 노드들 간의 최단 거리를 구하는 알고리즘. 엣지는 항상 양수여야 한다.  1. 인접리스트로 그래프 구현하기 (각 노드에서 갈 수 있는 노드와 가중치를 리스트 원소로)(인접행렬로도 구현 가능하지만 시간복잡도 측면에서 인접리스트로 구현해주도록 한다.)2. 최단거리 배열을 초기화한다. (시작노드는 0 나머지는 무한대)3. 값이 가장 작은 노드 고르기(처음은 시작노드가 된다)4. 최단거리 배열 업데이트하기5.모든 노드가 처리될때까지 3, 4 반복. 방문 배열을 만들어 재방문이 일어나지 않도록 한다. 2.벨만포드그래프에서 최단거리를 구하는 알고리즘.출발 노드에서 다른 노든까지의 최단 경로 탐색.엣지는 음수여도 된다.(음수 사이클 ..

1.지역변수와 스코프지역변수: 특정 지역(변수가 선언된 특정 지역)을 벗어나면 사용될 수 없음.   x 변수는 if블럭 안에서 정의 되었기 때문에 밖에서 출력을 시도할 경우 java: cannot find symbol 오류가 남 블럭 내부에서 블럭 외부에서 선언된 변수 접근 가능블럭 외부에서 블럭 내부에서 선언된 변수 접근 불가능 변수의 접근 가능한 범위를 스코프(scope)라고 한다 for문의 조건식 내부에서 선언된 변수의 경우도 지역변수로 해당 범위를 벗어나면 사용할 수 없다. 2. 스코프의 존재 이유임시적으로 m변수의 값을 변경해주기 위해 temp변수를 사용해주고 있다. 즉 불필요한 메모리를 사용하고 있어 코드블럭 밖에서 temp의 메모리를 제거하면 메모리를 더 효율적으로 쓸 수 있게 된다. 또한 ..

5-1) 그래프노드와 엣지의 집합 유니온 파인드그래프의 사이클이 생성되는지 판별하는 알고리즘위상 정렬사이클이 없는 방향 그래프에서 사용가능.그래프의 노드들을 선형으로 정렬. 정렬 결과가 꼭 한개는 아님 ex)수강신청다익스트라시작점이 존재하고 그 노드에서 다른 모든 노드로 가는 최단 거리를 구하는 알고리즘.단 음수 간선은 있으면 안됨  =>최단거리 알고리즘 벨만-포드다익스트라 알고리즘인데 음수 간선이 가능함.  음수 사이클이 존재하는가=>최단거리 알고리즘 플로이드-워셜벨만 -포드 알고리즘 인데 시작 노드가 없음. 즉 모든 노드 사이의 최단거리 측정. (시간복잡도가 안좋음)=>최단거리 알고리즘 최소 신장 트리 mst. 그래프에서 최소의 가중치 합으로 모든 노드를 연결할 수 있게 해주는 알고리즘. 사이클이 없..