처음부터 차근차근

문제 https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 문제 이미지만 보면 엄청 복잡할 것같고, 풀기 싫어지는데 조금만 생각해보면 쉽게 풀 수 있는 문제였다. 내 풀이 이런 류의 문제들은 제일 먼저 규칙성을 찾아야한다. 1에서 부터 차례대로 주변 벌집이 확장되는데 각 개수가 6의 배수만큼 늘어나는 걸 알 수 있다. 그래서 어느 구간에 있는지만 알면 최소로 거칠 수 있는 벌집의 개수를 쉽게 구할 수 있다. 나는 if문의 구간을 6의 배수만큼 차례대로 늘려가..

동적계획법 동적 계획이란 큰 문제를 작은 문제로 나눠서 작은 문제들을 해결해 최종적으로 큰 문제를 해결하는 방법이다. 동적 계획법 핵심 이론 1. 큰 문제를 작은 문제로 나눌 수 있어야 한다. 2. 작은 문제들이 반복되서 나타나야하고, 이 작은 문제들의 결과가 항상 같아야 한다. 3. 작은 문제들은 한 번만 계산해서 저장해두고, 추후에 계산해둔 작은 문제들을 재사용 해야한다. - 메모제이션 원리 4. 톱-다운 방식, 바텀-업 방식으로 구현할 수 있다. 톱 다운 방식 위에서 아래로 문제를 계산하는 방식 바텀 업 방식 아래에서 위로 문제를 계산하는 방식 예시 arr[0] = 0; arr[1] = 1; for (int i = 2; i

그리디 알고리즘 현재 상태에서 최선의 선택지를 고르는 알고리즘이다. 지금까지 공부했던 알고리즘 중 개인적으로 가장 쉬웠던 알고리즘이었다! 문제 https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전을 최소로 사용해서 입력된 금액을 만드는 문제이다. 예제 입력1을 보면 10 4200 // 동전 총 개수, 만들어야하는 금액 1 5 10 50 100 500 1000 5000 10000 5..

DFS =Depth First Search =깊이 우선 탐색 깊은 부분을 우선으로 탐색하는 알고리즘 스택 자료구조를 이용한다. or 재귀함수를 사용한다. BFS =Breadth First Search =넓이 우선 탐색 가까운 노드부터 우선으로 탐색하는 알고리즘이다. 큐 자료구조를 이용한다. DFS와 BFS는 코딩테스트에서 빈출하는 개념이다. 그래서 두 개념을 잘 숙지해두는게 좋다. * 개념 정리 잘해둔 블로그 : https://devuna.tistory.com/32 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다..

문제(제한 시간 : 2초) https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제를 해석해보자면 여기서 말하는 좋은 수란 두 번째 줄에 주어진 수 중 5로 예를 들어보자. 5는 두 번째 줄에 있는 수 중에 2 + 3이라는 조합으로 만들 수 있는 수이다. 그래서 5를 좋은 수라고 한다. 두 번째 줄에 있는 수 중 좋은 수의 개수를 구하는 것이 이 문제의 목표이다. 문제 풀이 이 문제는 투포인터 알고리즘을 사용해야한다. 투포인터 알고리즘을 사용해서 양 쪽 끝에서부터 가운데로 오..

문제 (시간제한 : 1초) https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 문제부터 이해가 잘 안됀다 ㅠㅠ 예제 입력 1로 문제를 설명해보면 5 3

문제 https://www.acmicpc.net/problem/1546 1546번: 평균 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보 www.acmicpc.net 내 풀이 import java.io.*; import java.util.*; import java.lang.Math; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..

문제 https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 문제 읽으면서 뼈맞았다ㅋㅋㅋ 내 풀이 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { int num, arr_num, sum, st_num; int[] arr; double avg; BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..