kwang2134 님의 블로그

[Grind75-LeetCode] Rotting Oranges - Medium접근bfs풀이썩은 오렌지 옆에 있는 오렌지는 1분이 지날 때마다 썩어가고 모든 오렌지가 다 썩기까지 걸리는 시간을 구하는 문제이다. 백준의 토마토 문제와 동일한 문제로 일이 분으로 각 과일의 상태를 나타내는 값이 조금씩 달라졌을 뿐 다른 게 없는 문제이다.2024.09.29 - [알고리즘/코딩테스트-백준] - [백준] 토마토 JAVA [백준] 토마토 JAVA[백준] 토마토 - GOLD V 7579, 7576번7576번: 토마토 (acmicpc.net)7569번: 토마토 (acmicpc.net)접근bfs풀이토마토 농장에는 덜 익은 토마토와 다 익은 토마토가 존재하는데 덜 익은 토마토가 다 익은 토마토 옆kwang2134.tisto..

[Grind75-LeetCode] Number of Islands - Medium 접근bfsdfs풀이0과 1로 이루어진 2차원 배열에서 1이 섬을 나타내고 0이 물을 나타낼 때 좌표 평면 위에 몇 개의 섬이 존재하는지 구하는 문제이다. 비슷한 유형이 굉장히 많은 문제로 비슷한 문제를 풀어 올렸던 기억이 있다.2024.09.26 - [알고리즘/코딩테스트-백준] - [백준] 단지번호 붙이기 JAVA [백준] 단지번호 붙이기 JAVA[백준] 단지번호 붙이기 - SILVER I 2667번2667번: 단지번호붙이기 (acmicpc.net)접근bfs풀이2차원 배열로 주어지는 지도를 탐색하며 붙어 지도에 총 몇 단지가 존재하는지와 단지를 이루는 집들의 수를kwang2134.tistory.com백준의 단지번호 붙이기 ..

[Grind75-LeetCode] Validate Binary Search Tree - Medium접근재귀풀이BST(Binary Search Tree) 이진 탐색 트리를 검증하는 문제이다. 주어지는 트리를 보고 이진 탐색 트리가 맞는지 확인지만 확인하면 되는 문제로 이진 탐색 트리가 어떤 건지 알아야 하는 문제다.  이진 탐색 트리는 이진트리의 형태를 가진 자료구조로 효율적인 데이터 저장과 검색을 위해 사용된다. 이진 탐색 트리의 특징은 모든 왼쪽 서브트리에 있는 값은 루트 노드의 값 보다 작아야 하고 모든 오른쪽 트리에 있는 값은 루트 노드의 값 보다 커야 한다. 이러한 특징이 재귀적으로 적용되기 때문에 단순 부모 노드의 값 보다만 작고 크면 되는 것이 아니라 해당 노드보다 상위레벨에 있는 모든 노드보..

[Grind75-LeetCode] Min Stack - Medium접근스택 + 우선순위 큐스택 + 스택스택 + 객체객체 (연결 리스트)풀이기본적인 스택에 최솟값을 반환받을 수 있는 최소 스택을 구현하는 문제이다. 간단하게 생각하여 풀 수 있는 두 가지 방법을 먼저 풀어보고 가장 좋은 성능을 보여준 코드를 가져왔다.스택 + 우선순위 큐 가장 쉽게 풀 수 있으나 성능이 좋지 않은 방법이다. 내부에 기본 스택 연산을 위한 스택 하나와 최솟값 반환을 위한 우선순위 큐를 두고 푸는 방식이다.class MinStack { private Stack stk; private PriorityQueue pq; public MinStack() { stk = new Stack(); pq..

[Grind75-LeetCode] Product of Array Except Self - Medium접근누적곱풀이주어지는 정수 배열에서 각 인덱스 값을 제외한 나머지 값의 곱을 배열 형태로 반환하는 문제이다. 2중 for문을 사용해 현재 인덱스를 제외한 나머지를 곱하면 되는 간단한 문제이지만 조건으로 O(n)의 시간 복잡도를 만족하는 코드를 제출해야 하기에 다른 방법을 선택해야 한다. 비슷한 형태의 값을 더하는 문제에서 사용했던 누적합 방식을 곱하기로 가능한지 찾아봤다. 당연하게도 누적곱 방식이 존재했고 이 문제는 누적곱 방식으로 O(n) 시간 복잡도를 만족하며 풀 수 있다. 누적곱이란 배열의 요소를 순차적으로 곱해나가는 방식이다. 누적곱을 만드는 방식은 누적곱 배열의 인덱스에 들어있는 값과 원본 배열의..

[Grind75-LeetCode] Coin Change - Medium접근dp풀이주어진 동전을 가지고 원하는 금액을 만들 수 있는지 만들 수 있다면 최소 몇 개의 동전을 사용해야 하는지 구하는 문제이다. 동전의 개수는 무한대로 주어지고 동전을 100원짜리, 500원짜리처럼 특정 값의 동전이 주어지기 때문에 주어진 값의 동전만 사용해서 만들어야 한다. 원하는 금액을 맞출 수 있으면 만드는데 필요한 최소 동전 개수를 구하고 만들 수 없다면 -1을 반환한다. 문제에 주어지는 내용이 동전일 뿐이지 비슷한 내용의 문제가 매우 많은 전형적인 dp 문제이다. dp 배열을 통해 Bottom-Up 방식으로 값을 채워나가면 해결이 되는 문제이다. public int coinChange(int[] coins, int ..

[Grind75-LeetCode] Implement Trie (Prefix Tree) - Medium접근Trie풀이이 문제는 Trie 자료 구조를 통한 삽입, 검색, 접두사 검색을 구현하는 문제이다. 이 문제를 풀기 위해서는 우선 Trie 자료 구조에 대해 알아야 한다.  Trie란 문자열을 검색하고 저장하기 위해 최적화된 트리 기반 구조이다. 단어 집합을 다루는 데 효율적이며, 주로 자동 완성, 접두사 검색, 사전 구현 등에 사용된다. 기본적인 트리 구조를 따르기 때문에 자식 노드와 마지막인지를 나타내는 플래그를 가진다. 기본적으로 한 문자 단위로 쪼개져 저장이 된다. 아래는 Trie에 저장된 모습이다.현재 Trie에 apple, app, aproach, ban, banana, call, cash라는 ..

[Grind75-LeetCode] Course Schedule - Medium 접근위상 정렬 (Topological Sort)DFS풀이2차원 배열로 주어지는 강의를 모두 수강할 수 있는지 구하는 문제이다. 강의 정보는 2차원 배열로 주어지며 [a, b] 형태이다. a라는 강의를 수강하기 위해 b라는 선수 과목을 수강하여야 한다. 언뜻 봤을 때 간단해 보이는 문제로 Set에 강의를 넣어두고 선수 과목이 Set에 들어있는지 확인하고 수강하는 방식으로 진행하면 되지 않을까?라는 접근으로 간단하게 코드를 작성해 봤다. 그럴 경우 예제 2번과 같이 [ [0, 1], [1, 0] ] 0번 강의를 수강하기 위해 1번 강의를 수강해야 하고 1번 강의 수강을 위해 0번 강의를 수강해야 하는 말도 안 되는 경우를 걸러내지..

[Grind75-LeetCode] Evaluate Reverse Polish Notation - Medium 접근스택Deque풀이후위 표기식으로 표현된 식을 계산하는 문제로 연산식은 배열을 통해 주어진다. 스택 자료구조를 공부할 때 후위 표기식을 스택을 통해 계산한다는 내용이 나오기 때문에 쉽게 풀 수 있는 문제이다. 간단하게 후위 표기식에 대해 설명을 하고 넘어가겠다.  후위 표기식이란 쉽게 말해 연산 기호가 숫자 뒤에 나오는 형태를 말한다. 우리가 익숙하게 사용하는 3 + 2 = 5와 같은 형태는 연산자가 가운데 오는 중위 표기식이고 연산자가 앞에 오는 전위 표기식도 존재한다. 이 문제에서 주어지는 후위 표기식의 경우 연산자가 숫자 뒤에 오기 때문에 3 + 2는 32+ 로 표현할 수 있다. 후위 표기..

[Grind75-LeetCode] Clone Graph - Medium접근재귀풀이노드 객체로 주어진 무방향 그래프를 형태 그대로 복제하는 문제이다. 그래프를 형태 그대로 복제하면 되는 간단한 문제이지만 참조 값을 복사하는 얕은 복사가 아닌 깊은 복사를 진행해야 통과가 가능한 문제이다. 말 그대로 참조 값이 주어지는 노드와 동일할 경우 통과하지 못한다.  public Node cloneGraph(Node node) { if (node == null) return null; Map map = new HashMap(); return clone(node, map); }이번 문제의 경우 Map을 사용해줬는데 원본 객체를 Key로 사용하고 복사한 객체를 Value로 ..