sezeme

난이도 : 실버 2유형 : 이분탐색구현 시간 : -문제 링크 : https://www.acmicpc.net/problem/16401풀이 링크 : https://www.acmicpc.net/source/98101657풀이 힌트과자 하나 당 N의 길이를 가진 과자를 만들려면 어떻게 해야 할까?M명의 조카에게 N길이를 가진 과자를 줄 수 있는지 어떻게 판단할 수 있을까?생각해보기과자 하나의 길이를 L로 잘라 조카들에게 나누어주려면, 각 과자를 snack / L 개로 나눌 수 있다.모든 과자에 대해 잘라낸 개수를 합산하면, 총 몇 명의 조카에게 나눠줄 수 있는지가 나온다.그 개수가 조카 수 M보다 크거나 같으면 길이 L은 가능 → 더 큰 값도 가능한지 확인해야 한다.반대로 M보다 작으면 길이 L은 불가능 → 더..

난이도 : Level 3유형 : 그리디구현 시간 : 20분링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42884 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 풀이 힌트차량 구간을 정렬해보자.시작점 기준일까? 종료점 기준일까?카메라 설치 위치를 정하면 그 이후 구간을 어떻게 커버할 수 있을까?겹치는 구간이 있으면 한 카메라로 여러 차량을 커버할 수 있겠지?그리디 선택 가능성“현재 구간을 가장 효율적으로 커버할 수 있는 위치”에 카메라를 설치하면 이후 구간에도 최적 선택으로 이어질까?"생각해보기힌트를 보면 겹치는 구간을 최대한 활용하는 방식이 ..

난이도 : Level 2유형 : 큐 / 구현 / 시뮬레이션구현 시간 : 40분링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 풀이시뮬레이션 표를 통해 1초에 한 대씩 움직인다는 것을 유추하고, 1초마다 트럭의 동작이 어떻게 변하는지를 나타내면 되는 문제였다.아래는 1초 마다 조건을 만족하면 트럭이 나가고, 조건을 만족하면 트럭이 다리 위로 올라오는 코드이다. 현재 문제에서는 괜찮지만, 시간복잡도가 올라간다. 1초를 기준으로 while문이 돌아가기 때문이다.import java.uti..

이 문제는 MST(최소 신장 트리)이다. MST인지 알아보는 근거는 아래와 같다.🔎 MST 문제의 전형적인 특징여러 개의 정점(섬, 도시, 컴퓨터, 송전탑 …) 이 있고정점들을 연결하는 간선(다리, 도로, 케이블, 전선 …) 들이 주어지며각 간선마다 비용(길이, 공사비, 연결비, 전력량 …) 이 있음모든 정점을 연결해야 하는데총 비용이 최소가 되어야 함🔹 MST (최소 신장 트리)에서의 Greedy 알고리즘MST 문제를 풀 때 가장 대표적으로 쓰이는 Greedy 알고리즘은 Prim과 Kruskal 두 가지이다.Prim 알고리즘아이디어: “시작 노드에서 출발해 가장 작은 간선만 선택하며 MST를 확장”구현 특징:보통 Priority Queue(최소 힙) 사용 → 가장 작은 간선을 빠르게 찾기 위해인접 ..

Java에서 객체 비교, 진짜 똑같은지 어떻게 알까? equals()와 hashCode()는 서로 연관이 있을까?겉보기엔 같아 보여도, 사실 내부 동작은 전혀 다릅니다.Object 클래스 기본 구현public boolean equals(Object obj) { return this == obj; // 주소값 비교}public native int hashCode(); // 보통 객체 주소 기반오버라이딩하지 않은 상태에서는:equals() → this == obj → 주소값 동일 여부hashCode() → 객체 주소 기반 값 반환중요 포인트: equals()는 hashCode를 직접 사용하지 않습니다.기본 구현에서 주소값 비교와 hashCode 반환 방식이 같은 이유는 Java 내부 구현상의 우연일 뿐..

문제 설명일할 수 있는 요일을 지정해서 최대 요금을 구해야 하는문제여러 방법을 생각했는데, 가장 효율적인 방법은 아니게 풀었다.방법 1. 이중 for문방법 2. 완전 DP풀이내 풀이해당 날짜가 되면 그 날짜에 도달할 수 있는 경우의 수가 있는지 for문으로 탐색한다. 시간복잡도가 그렇게 크지 않아서 가능했던 풀이 방식이다.import java.util.*;import java.io.*;class Main { static int N; static int[][] arr; static int[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader..

문제문제 설명'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다.게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다.뱀은 매 초마다 이동을 하는데 다음과 같은 규칙을 따른다.먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치시킨다.만약 벽이나 자기자신의 몸과 부딪히면 게임이 끝난다.만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않는다.만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가..

문제문제 설명두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.한 번에 한 개의 알파벳만 바꿀 수 있습니다.words에 있는 단어로만 변환할 수 있습니다.예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다.두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는..

문제문제 내용n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.입력첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 11010 -4 3 1 5 6 -35 12 21 -1예제 출력 133풀이아이디어경우의 수를 두 가지로 나누어 생각할 수 있다.arr[..

- 문제 유형 : DP문제 내용0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다.이친수는 0으로 시작하지 않는다.이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N이 주어진다.출력첫째 줄에 N자리 이친수의 개수를 출력한다.예제 입력 13예제 출력 12풀이해당 자..