1. 💎 문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 2. 🖥️ 코드 import java.util.*; import java.io.*; class Main { static boolean isBaecu [][]; public static void main(String args[]) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter..

1. 💎 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 🤔어떻게 풀까? 이거는 다 더해봐야 풀 수 있겠다고 생각하다가 어떻게 하면 로직을 줄일 수 있을까 고민했다. 결국 구간합을 이용하기로 했다! 구간합을 이용하여 O(n)으로 문제를 풀 수 있다. 만약 구간합을 미리 구하지 않는다면 모든 순서마다 요소들을 구해 더해줘야 하므로 O(M*N)으로 오랜 시간이 걸린다. 3. 💡 풀이 로직 1. 숫자 입력 받기 & 구간 합 구하기 현재 요소의 구간 합은 `sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + nums[i][j]`로 구한다. String [] data = br.rea..

1. 문제 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 2. 어뗗게 풀까 보기에는 쉬워보여서 무작정 4방향에 대해 for문을 쓰면 되지 않을까? 하고 구현을 했지만,, 점점 예상치 못한 곳이 늘어나고, 코드가 바뀌고, 결국 방향성을 잃어서 포기했다가 다시 도전했다. 어려웠던 점은 방향을 언제 바꿔줄지랑 방향을 바꿔주기 위해 체크하는 과정에서 실제 x,y 값을 바꿔주면 안되기에 비교를 어떻게 할까 애먹었다. 또한 2차원 배열을 사용했는데 `array[x][y]` 처럼 x값을 행으로 바라본 바람에 머릿속의 구조랑 전혀 달라져 x,y 위치를 바꿔 다시 구현했다. 이 문제의 핵심은 방향을 언제 바꿔줄지를 잘 선택하..

1. 💎 문제 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 2. 🤔 어떻게 풀까 악 이분 탐색 너무 어렵다!!!! 기준을 못 찾겠어.. 될 때까지 계속 푼다!!!!!😡😡 그래도 이 문제는 기준을 찾았다. 휴  우선 주어진 내용 중 관계를 파악했다. 가위질의 횟수가 많아지면 조각이 증가하고, 가위질의 횟수가 작아지면 조각이 감소할테니, 이를 이용해 계산 값이 주어진 k개의 조각과 딱 맞을 때 가위질의 횟수를 알아낸다. 그러기 위해선 가위질에 따른 잘라지는 색종이의 개수를 찾아야한다. 잘 모르겠다가 몇 번 그려보니 `(가로로 자른 수 +1)*(세로로 자른 수 +1)`이 잘라진 조각의 개수인 것을 알았다...

1. 💎 문제 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 M개의 전투력에 대해 칭호를 매개주면 되는 문제이다. 하지만 문제는 칭호의 개수와 M의 수가 10^5이라는 것이다. 시간 복잡도가 O(n^2)이하로 풀어야한다. 칭호의 상한선이 오름차순으로 주어지기 때문에 정렬된 상태로 이진 탐색을 쓰기 좋은 상태이므로 빠르게 진행하기 위해 이진 탐색을 이용한다. 이분 탐색 시간 복잡도 : O(log2N) 범위를 반으로 나누며 탐색 범위를 줄..

1. 💎 문제 2. 🤔 어떻게 풀까? 그림을 그려보니 가장자리는 무조건 1이고, 중간에 있는 요소들은 위에 있는 요소들을 순서대로 더하면 되는거였다. 그래서 처음에 ArrayList 배열로 구현할까 했지만, 이차원 배열로 구현하는게 더 좋은 방법같았다. 루프를 돌면서 차례대로 값을 채우기 위해서는 비어있는 값은 0으로 처리해야 했는데 ArrayList를 사용하면 0를 넣어주기도 애매하고 훨씬 어려워질 것 같아서, 애초에 처음부터 0으로 초기화되는 이차원 배열을 사용하기로 했다. 이렇게 0번째 요소에는 0를 담아 따로 에외처리를 하지 않도록 하였고, 순서대로 더 해주자고 생각했다. `A[i+1] = A-1[i] + A-1[i+1]`를 적용하도록 생각 후 구현을 시작했다. 3. 💡 로직 1. 솔루션 파스칼 ..

1. 💎 문제 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 2. 🤔어떻게 풀까 처음 봤을 때는 누적하면 풀어야될 것 같아서 DP로 풀어야하나 생각했다. 하지만 보다보니깐 큐를 이용해서 정보를 넣어서 관리해주면 될 것 같았다. 현재 위치에서 이동할 수 있는 경우의 수는 -1, +1, *2로 3가지이다. 그러므로 이 3가지 위치에 대해만 생각하면 되며, 현재 노드를 거쳐서 다음 위치를 갈 때 비용이 적은 경우 => 비용 갱신 및 큐에 추가 하기로 했다. 이 과정을 큐가 빌 ..

1. 💎 문제 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 2. 🤔 어떻게 풀까 무조건 삭제를 해야하므로(자세히 보면 삭제는 선택 사항이었음,,,) 무엇을 삭제할지 생각했을 때 홀수를 우선적으로 삭제해야 한다. 짝수 사이에 있는 홀수를 뺴줘야 이어질 수 있기 때문이다. 그리고 범위안에는 오직 최대 k개의 홀수만 있어야 하므로 홀수가 k개가 넘어가는 시점에서 걸러주는 작업을 하기로 했다. 그러므로 짝수와 홀수의 경우로 나눠 풀자고 생각했고, 투 포인터를 적용하여 `end`로는 수를 더하거나 탐색하고 `start`로는 수를 빼준다. 3. 💡 ..

1. 💎 문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제도 퍼져나가는 형식으로 BFS의 전형적인 문제이다. 현재 요소를 기준으로 주위 요소들이 전염되는 방식으로 이전에 풀었던 문제가 들과 유사하다. 단지 이 문제는 전염 조건과 수행해야 하는 로직이 늘었다. 조건1. 먼저전염 조건은 인접한 칸의 인구수가 L명이상, R명 이하이다. 조건2. 전염된 나라끼리는 인구수를 다시 계산해야한다. 조건3. BFS를 한 번만 돌리는 것이 아니라 인구이동이 없을 때까지 실행해야 ..

1. 💎 문제 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 2. 🤔 어떻게 풀까 이 문제는 점점 물들이는 문제로 익숙한 BFS문제로 느껴졌다. 그래서 BFS로 풀기로 하였고 출력 결과를 봤을 때 시작 점을 기준으로 거리가 늘어나는 것을 보아 시작점부터 탐색을 진행하며, depth을 관리하면서 풀면 되겠구나 생각했다. 3. 💡로직 1. 지도를 입력 및 시작점 받기 이중 for문으로 지도를 입력받는 형태에서 stream을 이용한 형태로 바꿨는데 시간이 훨씬 단축되는 ..