100세까지 코딩

조합 자체로도 자주 출제되며 동적 계획법을 이해하는데 중요 점화식을 도출하는 것이 매우 중요 기본 지식으로 i C k 이면, k는 (0 ~ i)까지 가능하며 k=0 또는 k=i 이면 1이다. 점화식 도출 특정 문제를 가정 모든 부분 문제가 해결되었다고 가정하고 지금 문제 생각 예시 5개 중에 3개를 고르는 5C3 (1,2,3,4),5가 있으면 괄호안은 이미 선택이 완료된 데이터 5를 선택한다면 이미 선택된 데이터 4개중 2개만 골라야 한다. 4C2 5를 선택하지 않는다면 이미 선택된 데이터 4개중 3개를 골라야 한다. 4C3 즉, 5C3 = 4C2 + 4C3 D[i][j] = D [i-1][j-1] + D [i-1][j] 문제 설명 풀기 전 생각 위에서 얻은 점화식을 활용하여 재귀함수 사용 재귀함수를 멈..

그래프란? 객체 사이의 연결 관계를 표현할 수 있는 자료구조 정점(vertex)과 간선(edge)들의 집합 종류는 무방향 그래프, 방향 그래프 문제 설명 강의 코드 import java.io.BufferedReader; import java.util.ArrayList; import java.io.InputStreamReader; public class Baek1707 { static ArrayList[] A; static int[] check; // 같은 집합인지 다른집합인지 구분 static boolean[] visited; // 방문 여부 static boolean IsEven; // 이분 그래프 인지 아닌지 T / F public static void main(String[] args) throws..

한눈에 보기 기능 설명 및 명령어 1. Fork 다른 사람의 Github repository를 내 Github repository로 그대로 복제하는 기능. original repository에 변화(commit)가 생기면 fork 된 repository도 반영(fetch or rebase)할 수 있다. (원본 추적 가능) 2. Clone 특정 repository를 내 로컬 pc에 복사하여 새로운 저장소를 만든다. original repository에 변화(commit)가 생기면 push가 불가능. 수정된 내용을 내 로컬에 적용(fetch & merge) 한 후 push 가능. git clone https://github.com/본인_아이디/저장소 아이디. git 3. Fetch 원격 저장소에 변경사항들을..

브루트포스 알고리즘이란? 완전 탐색 또는 무차별 대입 알고리즘 쉽게 말해 모든 가능한 숫자들을 대입해 보는 방식 선형 구조 : 순차 탐색, 비선형 구조 : 백트래킹, DFS, BFS 문제 설명 풀기 전 생각 무작정 대입 알고리즘이니 세 자릿수 100부터 999까지 List에 넣기 100부터 999까지 반복을 돌면서 정답과 같은 위치면 strikeCnt++ 그렇지 않고 포함만 돼있으면 ballCnt++ stikeCnt와 ballCnt가 힌트와 같지 않고 가능성 없는 수면 지우기 코드 import java.util.*; import java.io.*; public class Baek2503 { public static void main(String[] args) throws IOException { List..

에라토스테네스의 체란? 소수를 구할 때 자주 쓰이는 알고리즘 구하고자 하는 범위만큼 1차원 배열 생성 2부터 시작하여 현재 선택된 숫자의 배수에 해당하는 수를 배열 탐색하며 지우기 지워지지 않은 처음 선택된 숫자 = 소수 배열의 끝까지 위에 과정 반복 문제 설명 풀기 전 생각 배열 크기를 N+1로 잡고 0부터 index대로 대입 이중 반복문을 사용하여 바깥 반복문은 가장 작은 소수인 i=2부터 시작 안쪽 반복문은 j = i +1부터 시작하여 j가 i로 나눠떨어지면 arr [j] = 0으로 지우기 M~N까지 지워지지 않고 남아있는 소수들 출력 코드 import java.util.*; public class Baek1929 { public static void main(String[] args) { Scan..