Algorithm
1.[백준]11726 2xn 타일링
DP문제인데,점화식만 찾아내면 금방 풀 수 있는 문제였다
2.[백준] 11727 2xn타일링2
11726 문제와 유사한 문제인데, dpn-2값이 2x1짜리 2개, 2x2짜리 1개씩 붙어서 두 배씩 증가하므로 점화식이 조금 달랐다. 그 외에는 다른 점이 없는 문제점화식 : dp\[n-2] \* 2 + dp\[n-1]
3.[백준] 9095 1,2,3 더하기
dpn-3에 1을 더한 경우, dpn-2에 2를 더한 경우, dpn-1에 3을 더한 경우, 세 가지의 합이 점화식이 되는 문제였다.점화식: dp\[n-3]+dp\[n-2]+dp\[n-1]
4.[백준] 10844 쉬운 계단 수
dp를 이차원 배열로 정의해야하는 문제였다.i는 자리수, j는 시작하는 수이며 dpi는 dpi-1 앞에 j를 붙이고 dpi-1 앞에 j를 붙여서 만들 수 있다. 따라서 j=0인 경우에는 dpi-1과 j=9인 경우에는 dpi-1만 고려해주면 된다. 0으로 시작하는 수는
5.[백준] 2193 이친수
DP문제에 나름대로 적응해가는 중인 것 같아서 뿌듯하다!이 문제도 역시 dp 테이블을 이차원 배열로 정의하는 문제였다.0으로 끝나는 수는 i-1 모든 값들에 0을 붙이면 되고, 1로 끝나는 수는 0으로 끝나는 i-1에 1을 붙이면 된다.점화식dp\[i]\[0] = dp
6.[백준] 9329 패스트 푸드 상금
로직 자체는 어렵지 않았는데 아직도 자바 언어로 알고리즘을 푸는데 익숙지 않다고 느끼게 한 문제였다.상금으로 바꾸기 위한 스티커가 겹치지 않기 때문에, 필요한 스티커들 중 가장 적은 스티커의 갯수만큼 상금을 곱해 더해주면 되는 문제였다.
7.[백준] 10828 스택
자바로 스택을 구현해보는 것은 처음이었다.switch문을 사용했을 때 훨씬 가독성이 좋았다.size와 stack은 전역변수로 정의해서 공유함.후입선출이 핵심
8.[백준] 9012 괄호
간단한 스택 문제였다.
9.[백준] 2257 화학식량
스택을 활용한 문제이다.괄호 안에 들어간 원자들을 스택으로 쌓아주고 괄호를 닫을 때 tmp에 그 값을 저장해준다.숫자가 나왔을 때 tmp \* (N - 1)을 해주는 것이 핵심인 것 같다.
10.[백준] 10799 쇠막대기
자바에도 스택 클래스가 있으니 활용해서 풀 것닫는 괄호를 만났을 때 인덱스 차이가 1일 경우에는 레이저에 더해주고 아닐 경우는 막대로 생각해주면 되는데..다른 사람들이 훨씬 간단하게 풀어서 신기했다.스택 사이즈만큼 답을 더해주고 나중에 막대가 끝날 때 1을 더해줘도 답
11.[백준] 1986 체스
자바로 입력 받는 걸 아직도 헤매고 있다8방향 델타로 풀었다
12.[백준] 17390 이건 꼭 풀어야 해!
정렬해서 누적합을 빼주면 되는 문제선택정렬, 버블정렬 정도는 복습하자..
13.[백준] 1654 랜선 자르기
이분탐색 문제였다.left를 최소값 right를 최대값으로 잡고 조건에 맞으면 left를 mid로 아니면 right를 mid로 바꿔주면 된다. (최대값을 구하는 경우)
14.[백준] 2805 나무 자르기
이분탐색 인데 값에서 mid 값을 빼주는 것이 달랐던 문제.
15.[백준] 14627 파닭파닭
이분탐색으로 최대값을 구해주고 전체 파의 합에서 곱한 값을 빼주면 되는 문제
16.[백준] 2110 공유기 설치
공유기의 거리를 이분탐색해주면 되는 문제.거리가 클 때만 공유기를 세우고 가능한 경우 left를 mid로 옮겨주고 아니면 right를 mid로 옮겨 준다.이분탐색은 어떤 값을 탐색해야하고, 그 값의 최소값과 최대값을 찾은 후에, left와 right를 갱신하는 조건을
17.DFS / BFS
Depth-first search그래프를 깊이 우선으로 탐색하는 알고리즘stack을 사용하여 구현한다재귀를 통하여 구현할 때에는 일단 출력부터 해야 부모 노드부터 탐색할 수 있다Breadth-first search그래프를 너비 우선으로 탐색하는 알고리즘queue를 사용
18.[백준] 15649 N과 M(1)
어떤 노드의 유망성을 판단한 뒤 해당 노드가 유망하지 않다면 부모 노드로 돌아가 다른 자식노드를 찾는 알고리즘이다.DFS로 풀이할 수 있다. (깊이 우선으로 탐색하다가 해당 노드가 유망하지 않을 경우 탐색 중지)arr에 depth에 맞는 값을 담아서 dfs가 depth
19.[BOJ] 16234 인구이동
큐를 돌면서 다른 큐에다 좌표를 담아준다.다 돌고 평균값을 계산해서 다른 큐에 있는 좌표값을 갱신해준다.그리고 더이상 돌지 않을 경우를 flag로 check해준다.
20.[BOJ] 17836 공주님을 구해라
bfs는 너비우선탐색하기 때문에 다 돌고 나면 알아서 최소값이 나옵니다..핵심은 칼을 줍고 난 후에 방문했던 곳도 다시 갈 수 있도록 구현해야한다는 것.그래서 거리와 칼 여부를 큐에 함께 담아줘야 한다.visited가 여러 개 필요할 경우 3차원으로 정의해줘야한다.