레벨업 일지

문제 https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/ Minimum Number of Vertices to Reach All Nodes - LeetCode Can you solve this real interview question? Minimum Number of Vertices to Reach All Nodes - Given a directed acyclic graph, with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [fromi, toi] represents a directed edge from leet..

문제 https://leetcode.com/problems/swapping-nodes-in-a-linked-list/description/ Swapping Nodes in a Linked List - LeetCode Can you solve this real interview question? Swapping Nodes in a Linked List - You are given the head of a linked list, and an integer k. Return the head of the linked list after swapping the values of the kth node from the beginning and the kth node from t leetcode.com 알아야 할 개..

문제 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 알아야 할 개념 독해력 DFS 구현 풀이 나의 부족한 문제 이해력으로 문제의 예외 캐이스를 미쳐 생각 못해 머리를 싸메다 백준 질문 게시판에서 힌트를 얻었다. dfs구현은 어렵지 않았지만 예외 케이스가 존재하였다. 바로 빙산이 한번에 녹아 버리는 경우이다. 문제를 다시 보자 한 덩어리의 빙산이 주어질 때, 이 빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성..

문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 알아야 할 개념 2차원 배열 BFS 탐색 풀이 주어진 조건에 따라 bfs 시뮬레이션을 구현하는 문제. 풀이 알고리즘은 다음과 같다. 현재 위치에서 bfs 탐색을 하며 currentSIze 보다 작은 상어들을 priorityQueue에 추가한다. priorityQueue 가 비어 있지 않은 경우 하나 꺼내서 잡아먹는다. 시간, 상어 사이즈 갱신한다. 지금까지의 PriorytyQueue와..

문제 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 특별한 조건 없는 일반적인 2차원 배열 탐색 문제 풀이 풀이 알고리즘은 다음과 같다. 적록색약이 있으면 if문으로 1 또는 2 에 해당하는지 검사하면서 dfs한다. 색약이 없는 경우 dfs 하면서 메소드 부른 횟수를 카운팅 한다. 정답을 리턴한다. 코드 package solve; import java.io.*; import java.util.*; public class Main { i..

문제 https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 알아야 할 개념 모듈러 연산 특징 prefix sum 풀이 처음에 O( n logn ) 인 세그먼트 트리를 만들어서 접근하려고 했는데 역시나 O(N^2) 로 걸렸다. 이 문제의 키 포인트는 모듈러 연산의 분배법칙이다.. 분배법칙 (a + b ) % m == a % m + b % m 풀이과정은 다음과 같다. prefix sum 배열을 만든다.(누..

문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 주어진 배열의 연속된 subarray 에서 subarray.sum()

문제 https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/ Substring with Concatenation of All Words - LeetCode Can you solve this real interview question? Substring with Concatenation of All Words - You are given a string s and an array of strings words. All the strings of words are of the same length. A concatenated substring in s is a substring that contains all l..