1. 문제 설명 📌문제 링크동영상 재생기의 작동을 구현하는 간단한 문제이다.skip: 현재 user의 위치가 오프닝 구간 안이면, 오프닝이 끝나는 지점으로 JUMP 한다.next: 10초 뒤로 위치를 움직인다. 만약 남은 동영상 시간이 10초 미만이면 동영상의 마지막 위치로 간다.prev: 10초 앞으로 위치를 움직인다. 만약에 현 위치가 10초 미만인 상태에서 prev를 누르면 동영상 맨 처음 위치로 움직인다. (첫 위치 0분 0초)2. 접근 방식 🗃️KEY WORD: SIMULATION그냥 구현 문제이다. 한 가지 까다로운 것은 입력이 String으로 주어지고, 그것을 int로 변환해 작업을 수행해야 하는 점과 답변은 또 String 형태로 변환하여 해야하는 점이다.(1) 첫 번째 접근 방식: C..

1. 문제 설명 📌문제 링크문제 내용이 직관적이기 때문에 부가 설명은 생략하겠다.2. 접근 방식 🗃️KEY WORD: BFSoils라는 1차원 배열을 만든다. 해당 배열의 index 는 land의 열이고, value는 열 당 얻을 수 있는 석유의 양이다.land 전체에 대해서 이중 반복문으로 석유(1)이 있는 위치를 찾는다만약 석유를 찾는다면 해당 위치부터해서 연결된 석유 덩어리를 BFS로 찾는다.BFS로 해당 위치에서 시작해 석유 덩어리를 모두 찾았으면, 지금까지 거친 적 있는 열에 지금까지 찾은 석유량을 더한다.(예를 들어, 열을 1,2,3 거쳤고, 찾은 석유량이 7이면 oils[1] += 7, oils[2] += 7, oils[3] += 7 이 된다.)3. 코드 소개 🔎먼저 전체 코드를 보여주..

1. 문제 설명 📌문제 링크문제에서는 다음 3가지 단방향 그래프를 제시하고 있다.도넛형은 순환형 그래프이고, 간선의 개수와 정점의 개수가 같다.막대형은 비순환형 그래프이고, 정점의 개수 - 간선의 개수 = 1 이다.팔자형은 순환형 그래프이고, 간선의 개수 - 정점의 개수= 1 이다.이러한 3가지 유형에 해당하는 그래프가 최소 2개 이상 주어진다. 이때 주어진 모든 그래프를 잇는 정점을 하나 그린다. 우리는 이번 문제 풀이에서 해당 정점을 뿌리 정점이라 부르겠다. (문제에서 마땅히 해당 정점을 지칭하는 용어가 없어서 임의로 명명하겠다.) 뿌리 정점을 부착한 예시는 다음과 같다.이때 뿌리정점의 번호, 도넛형 그래프의 수, 막대 그래프의 수, 팔자형 그래프의 수 를 순서대로 기록한 1차원 배열을 출력하면 된..

1. 문제 설명 📌문제 링크무지랑 어피치랑 야근을 끝내고, 집에 갈려고함.버스가 끊겨서 택시를 타야 하는데, 택시 요금이 걱정됨.마침 무지랑 어피치가 집 가는 방향이 같은 쪽이라, 최대한 합승해서 전체 택시 비용을 줄이려고 함. 다만 합승하지 않고 가는게 전체 택시 비용이 더 작을 경우, 그 경우의 수를 선택함.회사 위치 : s, 무지 집: a, 어피치 집: b 의 위치가 주어진다고 치자.어피치와 무지의 택시 요금을 전부 합쳤을 때, 최소 택시 요금을 반환하라.힌트만 얻고 가실 분들은 접근 방식까지만 보고 가시길 바라고, 풀이법을 보실 분들은 끝까지 읽어주시라2. 접근 방식 🗃️KEY WORD: 다익스트라해당 문제가 다익스트라인 것을 알아채기는 쉽지만 거기에 더해 아이디어가 필요하다. 왜냐하면 그저 ..

4. 구현(1) 순차 탐색저번 게시글에서 설명한 작동원리 그대로 구현한 방식이다.방문한 정점과 그렇지 않은 정점 구분을 위해서, 방문배열을 사용한다.현재 정점에서 갈 수 있는 간선을 통해 dist[] 배열을 최신화하고, 방문 배열을 통해, 현재까지 방문하지 않은 정점 중 시작 정점에서 최단 거리로 갈 수 있는 정점을 택해야 한다.여기서 최악의 경우, 정점의 수가 N개라면, 매번 N번의 정점을 탐색해 다음 방문해야할 정점을 찾아야 하고, 이 행위를 모든 정점을 방문할 때까지 반복해야 하므로 최악의 시간복잡도는 O(N^2)이 든다.import java.io.*;import java.util.*;public class 순차탐색_다익스트라 { static int [] dist = new int [N]; ..

1. 문제 설명 📌문제 링크문제의 설명만 보면 이해하기가 어려운데, 밑의 시뮬레이터를 보면 문제에서 주어진 조건과 로봇의 작동원리는 이해할 만하다.하지만 헷갈리는 것이 있다면 바로, points와 routes의 의미 및 관계라고 할 수 있겠다.(1) 헷갈리는 것 바로 잡기points: 로봇이 방문해야하는 지점의 좌표를 배열 형태로 저장해놓았다.points[i]일 때, 이 i가 방문할 지점의 번호 이고, point[i]의 value가 각각 i란 지점의 행과 열 즉 좌표이다.routes; 로봇별로 방문해야할 지점을 순서대로 나열한 1차원 배열의 묶음이다.routes[i]의 i는 로봇의 번호이고, routes[i]에는 로봇이 방문해야할 지점의 번호가 순서대로 저장되어 있다.예를 들어, routes[2] = ..

1. 문제 설명 📌문제 링크1번 퍼즐사용자의 레벨이 1이라 했을 때, 첫 번째 퍼즐은 사용자의 레벨 >= 퍼즐의 난이도 조건에 부합함으로 시간을 3분 드려서 퍼즐을 완료한다.2번 퍼즐사용자의 레벨 퍼즐의 난이도 이다.이 경우 문제의 요구조건처럼 직전 퍼즐을 (퍼즐의 난이도 - 사용자의 레벨) 만큼 다시 풀어야 한다. 그래서 2번 퍼즐을 푸는데는 1*3+4 = 7분의 시간이 든다.3번 퍼즐이것도 마찬가지로 사용자의 레벨 퍼즐의 난이도 임으로 (퍼즐의 난이도 - 사용자의 레벨)*4 + 2 = 10분 이 든다.따라서, 사용자의 레벨이 1이면 모든 문제를 푸는데 총 20분이 소요된다.문제에서는 limit 이라는 제한시간이 주어진다.제한 시간 안에 퍼즐을 다 풀 수 있는 최소 레벨이 몇인지 구하여라2. 접근 방..

1. 개념(1) What? 다익스트라 알고리즘이 무엇인가요? 💡다익스트라 알고리즘은 한 정점에서 다른 정점으로 가는 최단 거리 비용을 구하는 알고리즘이다.다익스트라를 사용하면 시작 정점 S에서 직,간접적으로 연결된 모든 정점으로 가는 최단 거리 비용을 한 번에 구할 수 있다.(2) Why? 왜 해당 알고리즘을 써야 하나요? 🤔💭해당 알고리즘을 처음 접한다면 아마 지금까지 가중치가 없는 그래프에 대해서 정점 간의 최단 거리를 구하는 문제만 접해왔을 가능성이 높다. 가중치가 없는 그래프에서의 정점 간의 최단 거리는 BFS를 활용하면 쉽게 풀렸다. 왜냐하면 정점 사이를 잇는 간선의 개수가 곧 비용임으로 BFS를 돌렸을 때, 만나기까지 사용하는 간선의 개수만 세면 되었기 때문이다.하지만 가중치가 있는 그래..