Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처고층건물 골드 4 📖 문제 핵심사실상 수학문제라고 봐도 과언이 아니라 생각한다.기울기의 증감을 따져서 비교하면 되는데  빌딩중 하나를 기준으로 생각해보자. 좌측 부분은 기울기가 증가 하는 형태이고우측 부분은  기울기가 감소하는 형태이다.  대략 이렇게 볼 수 있다.  뒷건물에 대해서는 기울기 최솟값을 저장하고 최솟값보다 기울기가 크다면 그 빌딩은 볼 수 없는 빌딩이다. 앞 건물에 대해서는기울기 최대값을 저장하고최댓값보다 기울기가 작다면 그 빌딩은 볼 수 없는 빌딩이다.  문제에서 A-B 빌딩 선분이 다른 빌딩을 지나거나 접하지 않아야한다 했으므로 기울기가 같으면 그 빌딩은 볼 수 없다.  🔅 문제 풀이import java.io.*;import java.util.StringTo..

🧫 문제 분석 ✔️ 출처감소하는 수 골드 5 📖 문제  핵심감소하는 수는 완전탐색 + 백트래킹 문제이다. 먼저 문제를 보면 321, 950 같은 수는 감소한다. 즉 각 앞 자리수보다 뒷 자리수가 더 작아야한다. ex)321이면 3보다 작은 수가 와야하고 여기서는 2 가 왔다2보다 작은수 1이 왔다. 수를 생각해보면 0~9 까지 있고 나올 수 있는  감소하는 수 최대 값은9 8 7 6 5 4 3 2 1 0 이다. (98억7654만..)즉 10자리수까지만 탐색하면 된다는 의미이다.  문제에서 주어지는 N번째 수가 무엇인지를 출력하면 된다.예제 1번을 예시로 보자 0~9까지는 각 수에 대한 각 번호이다. 0 은 0번째 , 1은 1번째그리고 10 은 10번째이고 11부터 19까지는 감소하는 수가 아닌 같거나..

🧫 문제 분석 ✔️ 출처암호 만들기 골드 5 📖 문제  조건최소 한개의 모음 && 두 개 이상의 자음 알파벳이 사전 순서대로 정렬   ex) ba 불가능, ab 가능  알파벳을 배열에 담고 오름차순 정렬한 다음 길이를 주고 각 자리수에 맞게 완전탐색을 해본다. 처음(0일때) a일 경우 a를 방문했다고 하고 나머지 c i t s w 에 대해서 또 DFS를 한다. 중요한 것은 이전 사전 순이기에 이전 알파벳보다 현재 알파벳이 커야한다.(순서로 따지자면 뒷 번호여야 한다.)따라서 이전 알파벳에 대한 인덱스를 매개변수로 넘긴다.   그리고 모음의 만들어야하는 암호의 길이 L - 모음의 개수 = 자음의 개수이다.    🔅 문제 풀이import java.io.BufferedReader;import java.i..

🧫 문제 분석✔️ 출처이진수 실버 3 📖 문제  내가 이해한 바로는    이런느낌이다.3번째를 만들어준 2번째의 수의 경우와 2번째를 만들어준 1첫째 수의 경우의 합이라는 느낌이다.  🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;public class Main { public static long[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); ..

🧫 문제 분석✔️ 출처스택 수열 실버 2 📖 문제 1~N까지의 숫자들이 오름차순으로 스택에 push될 수 있고,입력된 수열, 여기서는[4 3 6 8 7 5 2 1] 이라는 수열을 만들기 위해 스택이 해야하는 연산을 출력하는 문제이다.push : + pop : - 우선 먼저 수열의 맨 처음인 4를 놓기 위해서는 1~4까지 스택에 push 후 1번 pop한다. 그럼 스택에는 1 2 3 이 남게 된다. 그다음은 3이므로 pop 한 번 한다.다음 6이므로 5 6 을 push하고 pop 하여 6을 빼낸다. 즉 수열의 각 순서에 따른 수만큼 push하고 top의 수가 현재 순서의 수면 pop하고 아니라면 NO를 출력하고 중단한다.push는 현재 까지 넣은 수에 따라서 진행한다. 현재까지 넣은 수보다 큰 수가 오..

🧫 문제 분석✔️ 출처1, 2, 3 더하기 실버 3 📖 문제  DP(동적계획법) 문제이다. 우선 1 과 2 그리고 3을 구하는 경우의 수를 봐보자 1 1 21 + 1231 + 1 + 12 + 11 + 23 문제에서 예시로 4를 구하는 방법이 나와있다. 4를 구하는 방법은 크게 보면1 + 3 2 + 23 + 1 이 세가지 경우라고 볼 수 있다. 우리는 1, 2, 3을 통해서 방법의 수를 구하기에 1을 고정해놓고 3을 구하는 경우의 수2를 고정해놓고 2를 구하는 경우의 수3을 고정해놓고 1을 구하는 경우의 수이 세가지의 합이 4를 구하는 경우의 수라고 볼 수 있다. 표로 보자면 이렇게 볼 수 있다.고정경우의 수1 + 1 + 1 + 11 + 22 + 132 + 1 + 123 + 1  🔅 문제 풀이impo..

🧫 문제 분석 ✔️ 출처봄버맨 실버 1 📖 문제 그래프를 써야할것 같은 느낌이 솔솔 느껴진다.그러나 DFS / BFS 문제는 아니다. 문제에서 '연쇄 반응이 없다' 하였다. 문제 실행 단계0. 초기상태 (폭탄이 미리 심어져있음)1. 아무것도 안한다.2. 모든칸에 폭탄 설치3. 3초전 설치된 폭탄 모두 폭파  4. 2번 부터 반복  초로 예시를 보면  0초 : 초기 상태1초 : 아무것도 안함2초 : 모든 칸에 폭탄 설치3초 : 3초전에 설치된 폭탄 모두 폭파 (0초 때 설치한 폭탄들)         - 이때 폭파되지 않은 부분이 다음 초기상태 (0초때 설치한 폭탄들)가 된다.4초 : 모든 칸에 폭탄 설치5초 : 3초전 설치된 폭탄 모두 폭파    0 과 1로 폭탄을 구분하여 설명하자면먼저 0초때에 초기..

🧫 문제 분석 ✔️ 출처인구 이동 골드4 📖 문제 랜덤 문제를 돌리다가 나왔다. 그래프 탐색 냄새가 솔솔 난다. BFS를 사용하면 될것 같다.  1. 한 나라의 좌우 상하로 인접한 다른 나라와의 인구차를 M명이라 했을 때 L 해야한다.2. 조건을 만족한 나라들과는 연합을 하여 국경선을 하루 연다. 3. 인구가 이동하며 각 나라의 인구수는 (연합 인구수 / 연합한 나라 개수) 가 되며 소수점은 버린다. 4. 이동후 연합 해지 및 모든 국경선을 닫는다.5. 인구 이동이 없을때까지 반복한다.6. 인구 이동이 며칠동안 발생했는지가 문제이다.  내가 생각한 방법1. 우선 연합가능한 나라들을 찾고, 그 나라에 연합 번호를 매기며 각 인구수를 더해놓는다. 2. 연합은 1개 이상 생길 수 있다. 3. 만약 1번 연..

🧫 문제 분석 ✔️ 출처숨바꼭질 1697번 - 백준 📖 문제🔅 문제 풀이수빈이의 위치 x동생의 위치 k수빈이는 -1, +1, *2 로 이동할 수 있고 이는 1초를 사용한다.graph를 조건에 만족하는 최대 크기로 만들어서 각 위치에 따른 초를 적을 것이다.처음 수빈이가 있는 장소는 1로 초기화한다. 너비우선탐색으로 하되 문제에서 주어진 위치에 대한 조건식을 걸어주고 (0 이동하려는 곳에 이전에 이동한 흔적이 있는지 확인하여 걸린시간이 덮어씌어지는 것을 방지한다.x-1, x+1, x*2 3번의 위치이동을 하고 graph 인덱스의 값에 현재 위치의 걸린시간 +1 초를 더해 이동한 흔적을 남긴다. 그리고 이동한 위치를 queue에 넣는다. 방문하지 않은 곳은 걸린시간이 0이다. 왜냐하면 graph를 만들..

백준 2667번 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 풀이 미로 찾기와 매우 유사한 문제이다. 다른점은 단지라는 그래프의 개수와 각 단지의 집들 즉, 각 그래프의 노드들의 개수를 오름차순으로 출력하는 문제이다. 그저 그래프를 찾아내서 얼마만큼의 노드들이 연결되어 있는지만 확인하기에 BFS, DFS 둘다 사용이 가능하다. 여기서는 BFS를 사용하였다. import java.io.*; import java.util.*; public class Main { static int[][] graph; st..