Midnight Coder's Lounge

실버1 티어 DFS 문제인 단지번호붙이기 문제 풀이입니다.제법 많은 분들께서 제 문제 풀이를 조회해 주셔서, 블로그에 직접 문제 해설을 올리기로 마음먹었습니다.    * 선수지식 : DFS, PriorityQueue 문제 링크 https://www.acmicpc.net/problem/2667   개요  "이차원 평면 위에 1로 표현된 '집'들을 상하좌우로 연결한 묶음을 '단지'라고 하겠습니다. 첫째 줄에 총 단지 수가 몇 개인지 출력해 주세요. 그 후 단지별로 들어 있는 집의 수를 오름차순 정렬해서 한 줄씩 출력해 주세요."   코드 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import..

스택 자료구조를 다루는 감이 떨어져 스택 문제를 복습했습니다. 풀고 나니 예상보다 티어가 높은 문제였네요. * 선수지식 : Stack, (List)  문제 링크 https://www.acmicpc.net/problem/2504  개요 "괄호의 짝이 맞는지 확인하고, 괄호의 쌍이 나타내는 값의 합계를 구하세요".- 괄호 '()'는 감싸고 있는 값들을 전부 합해서 2를 곱해줍니다. 괄호 안이 비었다면 2를 나타냅니다.- 괄호 '[]'는 감싸고 있는 값들을 전부 합해서 3을 곱해줍니다. 괄호 안이 비었다면 3을 나타냅니다.() = 2[] = 3([]) = 2 * 3 = 6()[] = 2 + 3[()[]] = 3 * (2 + 3) = 15[([])[]] = 3 * ( (2 * 3) + 3 ) = 27 이 규칙에..

이른 아침에 산책을 나가서 아침밥을 먹다가 심심해서 예전에 실패했던 백준 문제들을 둘러보았습니다. 실버3 문제 하나를 빠른 방법으로 풀게 되어서 공유하려고 합니다. 문제 링크https://www.acmicpc.net/problem/3273  개요"주어진 배열에서 서로 다른 원소 두 개의 합이 X가 되는 경우의 수를 구하시오". 알고리즘을 처음 배울 때 조합으로 접근했다가 어리둥절했던 문제입니다.'분명 배운 대로 했는데 왜 통과를 못하는 거지?'물론 이제는 순열, 조합과 같은 완전탐색보다 훨씬 빠른 알고리즘이 많다는 걸 깨달았으니더 빠른 풀이방법을 생각해 낼 줄 알아야겠죠.  조합으로 풀 경우시간 제한이 1초인 문제입니다. 배열의 크기는 최대  100,000으로 주어집니다.배열에서 2개의 원소를 찾기 위해..

정말 오랜만에 올리는 포스팅입니다. 백준 알고리즘 문제를 하나 풀어보도록 하겠습니다. 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 개요 골드 4 난이도 시뮬레이션 문제입니다. 골드 난이도라지만 복잡한 알고리즘 지식이 필요한 문제는 아닙니다. 이차원 배열과 큐 Queue 정도의 자료구조를 문제풀이에 응용할 줄 알고, 문제의 요구사항을 꼼꼼히 구현하는 능력이 있다면 풀 수 있는 문제였습니다. 코드 [제출 결과] [코드] import java.io.BufferedReader; import java.io.IOExcept..

https://atomicliquors.tistory.com/8 [Leetcode][Java] 투 포인터로 더욱 빠른 배열 연산을 수행해 보자(1) 투 포인터 알고리즘 : 배열을 효율적으로 탐색하기 위해, 동시에 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘입니다. 별도의 정렬 알고리즘 없이 정렬된 배열을 얻을 수 있게 해 주거 atomicliquors.tistory.com 지난 시간에 이어서, Leetcode에 등록된 배열 문제의 투 포인터 알고리즘 솔루션을 알아보겠습니다. 167. Two Sum II - Input Array Is Sorted Given a 1-indexed array of integers numbers that is already sorted in non-decreasing o..

투 포인터 알고리즘 : 배열을 효율적으로 탐색하기 위해, 동시에 두 개의 포인터를 사용하여 배열을 순회하는 알고리즘입니다. 별도의 정렬 알고리즘 없이 정렬된 배열을 얻을 수 있게 해 주거나, 이중반복문으로 처리해야 할 문제를 반복문 하나로 처리하거나, 추가적인 배열 생성 없이 그대로 배열을 수정하는(in-place modification) 등등, 시간/공간복잡도를 줄여주는 유용한 접근법입니다. Leetcode에 등록된 실제 예제를 통해 투 포인터 알고리즘에 대해서 알아보겠습니다. 977.Squares of a Sorted Array Given an integer array nums sorted in non-decreasing order, return an array of the squares of eac..

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면 10장과 20장을 합친 뒤, 합친 30장 묶음과 40장을 합친다면 (10 + 20) + (30 + 40) = 100번의 비교가 필요하다. 그러나 10장과 40장을 합친 뒤, 합친 50장 묶음과 20장을 합친다면 (10 + 40) + (50 + 20) = ..