일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 자바 5464
- 인텔리제이 에러
- 카카오
- 코딩테스트
- 백준 18222
- 리트코드
- 파이썬
- 백준 16935
- 코테
- 리트코드 자바
- java leetcode
- 스프링 에러
- 프로그래머스 java
- 스택
- 자바
- 프로그래머스
- dfs
- DP
- daily challenge
- 리트코드 1557
- 분할정복
- 자바 리트코드
- 백준
- 그래프 자바
- java 프로그래머스
- leetcode 1721
- 구현
- Java
- leetcode
- BFS
- Today
- Total
목록백준 (25)
레벨업 일지
문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 특별한 조건 없는 일반적인 2차원 배열 탐색 문제 풀이 풀이 알고리즘은 다음과 같다. 적록색약이 있으면 if문으로 1 또는 2 에 해당하는지 검사하면서 dfs한다. 색약이 없는 경우 dfs 하면서 메소드 부른 횟수를 카운팅 한다. 정답을 리턴한다. 코드 package solve; import java.io.*; import java.util.*; public class Main { i..
문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 알아야 할 개념 모듈러 연산 특징 prefix sum 풀이 처음에 O( n logn ) 인 세그먼트 트리를 만들어서 접근하려고 했는데 역시나 O(N^2) 로 걸렸다. 이 문제의 키 포인트는 모듈러 연산의 분배법칙이다.. 분배법칙 (a + b ) % m == a % m + b % m 풀이과정은 다음과 같다. prefix sum 배열을 만든다.(누..
https://zero-base.co.kr/event/BE_promotion_cordingtest2303 백엔드 스쿨 미니 코딩테스트 대회 | zero-base 코딩테스트 한 문제 풀면 에어팟 맥스 당첨 기회가! zero-base.co.kr 문제 개수는 한 문제였다. 난이도는 골드 4 로 완전탐색 구현 하는 문제였다. 대회는 5등으로 수상했다. 1년 전만 해도 백준 브론즈 구현도 어려워 했는데 , 알고리즘 문제 풀이를 꾸준히 하여 대회 수상도 하고 짧은 시간에 알고리즘 풀이 실력이 많이 늘어서 좋았다. 앞으로도 블로그에 문제 풀이 포스팅을 계속 해야겠다고 다짐한 수요일 저녁이다. 문제 https://www.acmicpc.net/problem/27958 27958번: 사격 연습 N×N 크기의 보드 판이 존..
문제 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알아야 할 개념 Dynamic Programming 풀이 나이브하게 모든 경우를 완전탐색한다고 하면, 경우의 수는 3^N 이다. 점화식을 사용해 최적화를 한다. 구하고 싶은 단계가 k 라면, k-1 번째에 빨강, 파랑, 초록 으로 칠했을 때 최솟값을 안다면 k번째에 최솟값을 쉽게 구할수 있다. 풀이 알고리즘은 다음과 같다. 주어진 입력을 2차원 배열 map 에 저장한다...
문제 https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net brute force 를 구현하는 문제 풀이 일단 나이브하게 모든 바이러스의 조합을 구하고 완전탐색을 하여 가장 낮은 것을 출력하는 구현 문제이다. 풀이 알고리즘은 다음과 같다. 놓을 수 있는 바이러스의 위치 조합(combination) 을 구한다. 해당 조합에서 바이러스를 활성화시키고 BFS 탐색을 한다. 출력으로 -1 이 나온 경우를 제외하고 최솟값을 구한다. 모든 경우가 -1 이면 -1을 출력한..
문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 알아야 할 개념 DFS 백트래킹 풀이 핵심은 치킨집을 (Math.min (M, 치킨집 개수 ) ) 만큼 뽑았을 때 도시 치킨 거리의 수를 모두 구하면 되는 문제. 나이브한 브루트포스 풀이 알고리즘은 다음과 같다. 일정 개수 (min(주어진 M, 치킨집 개수 )) 만큼 치킨집을 뽑는다. 모든 집의 치킨 거리를 계산한다. 도시 치킨 거리를 계산한다. 알고리즘 (1,2,3) ..
문제 https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 알아야 할 개념 다이나믹 프로그래밍 풀이 풀이는 다음과 같다. dp 배열을 하나 만들고 최대 값 10001로 채운다. dp 배열에 (idx == 3의 배수)를 3으로 나눈 몫으로 채운다. dp 배열을 순회 하면서, dp[i-5] (이전에 최소값 봉지의 개수) + 1 , dp[i] (현재 개수 ) 두 값의 최솟값으로 업데이트한다. dp[ 주어진 숫자 ] 를 리턴한다. 참고 dp[i-5] + 1 을 한 이..
문제 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 풀이 수학 문제를 풀 때 1 부터 n 까지의 수를 for문을 돌리면서 누적합을 하고 싶은가? 아님 n까지의 수의 합 n*(n+1)/2 으로 한 번에 도출 하겠는가? 당연히 후자일 것이다. public int getSum(int n){ int sum = 0 ; for(int i = 1; i < n+1 ;i++) sum += i; return sum; } publi..