레벨업 일지

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알아야 할 개념 2차원 배열 BFS 탐색 풀이 주어진 조건에 따라 bfs 시뮬레이션을 구현하는 문제. 풀이 알고리즘은 다음과 같다. 현재 위치에서 bfs 탐색을 하며 currentSIze 보다 작은 상어들을 priorityQueue에 추가한다. priorityQueue 가 비어 있지 않은 경우 하나 꺼내서 잡아먹는다. 시간, 상어 사이즈 갱신한다. 지금까지의 PriorytyQueue와..

문제 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://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 주어진 배열의 연속된 subarray 에서 subarray.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/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 문제에서 주어진 것들을 적용하여 풀이하는 문제. L 메소드 ( 왼쪽으로 쉬프트 ) 를 잘못 구현하여서 틀렸다. 내가 구현한 코드 int L(int n){ if(n ==0 )return 0; int temp = n; temp *= 10; if(temp /limit >= 1){ temp = (temp/limit) % limit; } n = temp; return n; } 이때 ..