나의개발일지

https://www.acmicpc.net/problem/1138 처음엔 순서대로 주어진 위치만큼 앞에 자리를 남겨두고 저장하고, 기존 수와 비교하며 뒤로 밀고 넣으면 되겠다하고 구현 했다.하지만 그렇게 하니 예제 4에서 결과값이 6 2 3 4 5 7 1 이 나왔다.작은 키부터 넣으면 앞에 큰 키의 개수를 제대로 고려하지 못하는 것이었다. 그래서 큰 키부터 넣어야 된다는 것을 깨달았다.1. 큰 키서부터 주어진 위치만큼 앞에 남겨두고 위치시킨다.2. 만약 해당 자리에 값이 이미 들어있다면 해당 값은 무조건 더 큰 값이 있을 것이므로 뒤로 쭉 밀고, 지금 값을 자리에 위치시킨다.3. 그렇게 위치시킨 값을 출력하면 끝! package BOJ.Greedy;import java.io.BufferedReader;i..

https://www.acmicpc.net/problem/18352 오늘 문제는 단순 BFS지만 고려해야 하는 조건이 많은 문제였다,,1. 양방향이 아닌 단방향 그래프2. 방문 가능한 도시를 오름차순으로 출력 -> pq에 넣어서 출력했다.3. 방문 가능한 도시가 0이면 -1 출력 -> 도시 방문 여부를 flag로 검사했다. 요 3개 조건만 잘 적용하면 되는 문제였는데, 난 여기에 방문 조건을 잘못 걸어서 출력초과와 틀렸습니다를 계속 받았다,,** 고려하지 못했던 부분1. 거리가 K를 넘어가면 q에 넣을 필요가 없다.2. q에 안넣어도 방문 처리는 해줘야 한다!!!package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;im..

https://www.acmicpc.net/problem/7562 최소 몇 번만에 이동할 수 있는지 = BFS이동가능한 방향은 8가지 (-2, 1) (-1, 2) (1, 2) (2, 1) (2, -1) (1, -2) (-1, -2) (-2, -1) 이다.큐에 들어있는 모든 칸들이 한꺼번에 1번씩 이동하다가 목적지에 도착하는 이동 거리를 계산해야 하므로 qSize 만큼 돌리면서 cnt++ 해주고,목적지에 도착했을 때의 cnt 값이 답이된다.  package STUDY.Week02;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import jav..

https://www.acmicpc.net/problem/16953 A에서 B를 만드는 방법은 여러개이고, 현재 값에서 다음 값으로 갈때 어떤 연산을 해야 더 빠른지 알 수 없다.하지만 역순으로 생각하면 다르다! B에서 1이 있으면 무조건 1을 더하는 연산을 쓸 수 밖에 없으니 이 연산을 우선순위로 두고 나아가면 된다.즉, B -> A로 가면서 1이 있으면 1을 제외하고, 1이 없으면 2를 나누고, 두 연산 다 되지 않거나 B의 연산값이 A보다 작아지면 -1을 출력한다. package BOJ.Greedy;import java.util.Scanner;public class BOJ_16953_AtoB { public static void main(String[] args) { Scanner..

https://www.acmicpc.net/problem/19941 처음으로 그리디 문제 읽으면서 떠오른 생각왼쪽에 있는 버거부터 먹어야 사람이 먹을 수 있는 버거의 수가 최대가 된다.사람을 만났을 때 왼쪽부터 k만큼 탐색해서 버거가 있으면 먹고, 없으면 오른쪽 버거를 먹으면 된다.한번 먹은 버거는 또 먹을 수 없으니 check 배열로 먹은 버거는 체크해준다.  package BOJ.Greedy;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class BOJ_19941_햄버거분배 { static int n, k; ..

https://www.acmicpc.net/problem/1449  그리디는 항상 해결방법을 떠올리는 게 참 어려운 것 같다,,이 문제는 주어진 물이 새는 곳의 위치를 정렬 해 두고, 주어진 테이프 길이 안에 위치하는 지 확인하면 되는 문제이다.즉, 첫번째 위치에서 -0 .5를 시작지점(left)로 두고 + 테이프의 길이(l) 안에 다음 물이 새는 위치가 더 오른쪽에 위치한다면테이프의 개수를 1 카운트하고, 시작지점을 다음 물이 새는 위치 - 0.5 지점으로 변경해주면 된다.  package BOJ.Greedy;import java.util.Arrays;import java.util.Scanner;public class BOJ_1449_수리공항승 { public static void main(Str..

https://www.acmicpc.net/problem/2217 각 각의 로프의 최대 중량이 주어지고, n개의 로프를 병렬로 이용하면 물체 무게를 n빵해서 들어올릴 수 있다.주어진 예제로 생각해 보자면, 15 로프를 이용하면 최대 15까지 들 수 있지만 10 로프를 함께 이용하면 최소 중량인 10의 2배(로프가 2개니까)까지 들 수 있다.그럼 10과 15 로프를 병렬로 이용하는 게 최선이다.만약, 주어진 로프가 5와 20 이라면 20 로프 하나로 20을 들 수 있고, 5 로프를 함께 이용하면 5*2=10밖에 들지 못한다.따라서 20로프를 하나만 이용하는 게 최선이다.이를 통해, 우선 병렬보다는 최대 중량의 로프 1개를 이용할 때를 확인해보는 게 우선순위라는 것을 알 수 있고, 그 뒤로는 n빵일 때를 차..

https://www.acmicpc.net/problem/1789 https://www.acmicpc.net/problem/2457 문제 부분집합으로 풀다가 시간초과 나서 보니 그리디,,,어려워 그리디,, 이번주는 그리디 뿌셔야겠다싶어서 시작으로 고른 문제N의 최댓값을 고르기 위해서는 1부터 1+2+3+4+5+... 더해가다가 S를 딱 넘은 시점에 숫자 하나만 빼주면 된다.즉, S가 11 이라고 했을 때, 1+2+3+4+5 일 때 4를 빼주면 됨!package BOJ;import java.util.Scanner;public class BOJ_1789 { public static void main(String[] args) { Scanner sc = new Scanner(System.in..

https://www.acmicpc.net/problem/3079 문제를 읽다보니 너어무 익숙했던,, 프로그래머스 문제와 동일했다https://dev-zsunny.tistory.com/23 99클럽 코테 스터디 3일차 TIL 이분탐색(입국심사)https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 시간의 최솟값을 구해dev-zsunny.tistory.com그래서 금방 풀어서 제출했지만 2%, 13%, 30% 계속  틀렸구,,, 또 자료형 문제였다!!!!!분명 자료형 고려해줬다고 생각했는데, 심사 가..

https://www.acmicpc.net/problem/2805 이분탐색 문제를 여러개 풀다보니 이제 문제를 읽으니까 언제 이분탐색을 써야할지 감이 살짝 온다1. 변수 범위가 클 때! (1억 이상)2. 구해야하는 값이 랜덤이 아닌, 특정 기준에 맞춰 지속적으로 범위를 찾아주어야 할 때! 즉 문제에서 구하는 값이 최대, 최소인 경우큰 범위 내에서 특정 값을 범위를 통해 찾아야 할 때 => 이분탐색을 쓰자! 무튼 이 문제는 전에 풀었던 예산과 비슷하게 풀었는데 2%에서 틀려서 당황했다,,여러 테케 만들어서 넣어봐도 다 분명 정답이 나오는데,, 문제는 자료형이었다!!!나무의 길이 M이 최대 20억인데 calc 함수에서 상근이가 집으로 가져가려고 하는 나무의 길이 result가 int형 범위를 넘어가는 것이었..