티스토리

Hello, Freakin world!

검색하기

블로그 홈

Hello, Freakin world!

javachoi.tistory.com/m

johnna_endure!!!

구독자: 2

방명록 방문하기

주요 글 목록

[백준 1052번][Java] 물병 - 다른 풀이 https://www.acmicpc.net/problem/1052 1052번: 물병 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번 www.acmicpc.net 풀이 방법 이 풀이 방법은 아주 직관적이고 쉽습니다. 1. 1L 물병의 개수가 2의 제곱수인 경우, 하나의 물병에 옮길 수 있다는 점을 이용해, N을 2의 제곱수로 분해한다. (이때 분해된 개수가 물병의 개수다.) 2. 물병의 개수가 K보다 크다면 크기가 작은 물병들부터 합쳐나간다. 예를 들어, N = 11인 경우 8, 2, 1로 분해할 수 있겠죠. 이는 세 개의 물병에 각각 8L, 2L, 1L가 들어.. 공감수 0 댓글수 0 2021. 5. 16.
[백준 15684번][Java] 사다리 조작 www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 풀이 아이디어 놓을 수 있는 사다리 위치에 사다리를 하나씩 놓아보고 그때마다 사다리 게임을 돌려 확인하는 방식으로 풀 수 있습니다. 사실 말이 쉽지, 꽤 까다로웠습니다. 구현 문제는 정말 너무 어려운 것 같네요. 가중 중요하게 신경써야될 한 가지 포인트만 소개하겠습니다. putLadderDown의 재귀 방식 putLadderDown 메서드 안에는 이중 for문이 있습니다. 놓을 수 있는 위치에 사다리를 놓고,.. 공감수 0 댓글수 0 2021. 5. 9.
[백준 1655번][Java] 가운데를 말해요 www.acmicpc.net/problem/16551655번: 가운데를 말해요첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1www.acmicpc.net 단순하게 접근하기문제에서 N개의 다양한 크기의 정수가 주어집니다.이 정수들이 하나씩 주어질 때마다 이전까지의 값들을 고려한 중간값을 찾아내야 합니다.가장 단순한 접근은 값들을 리스트에 넣고 값이 주어질 때마다 리스트를 복사해 정렬한 뒤 중간값을 찾아내는 것입니다.이럴 경우 리스트 복사 비용을 제외하더라도 시간 복잡도는 O(N^2 * logN)이 되기 때문에 시간초과로 실패합니다.(N 3이므로 3이 최.. 공감수 0 댓글수 0 2021. 5. 8.
[백준 3055번][Java] 탈출 - BFS www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS 방식을 사용해 최단 거리를 찾는 문제입니다. 포인트는 두 가지입니다. 1. 노드를 큐에 넣을 때, 물에 잠기는 장소인지 검사할 것 2. BFS의 깊이가 깊어질 때마다 잠기는 부분이 확산되도록 구현 1번은 해당 지역 상하좌우로 물이 있는지 검사하면 됩니다. 2번은 큐에서 꺼내져 나오는 노드의 depth가 깊어질때마 수행해줍니다. 둘 다 그리 어려운 구현은 아니라 딱히 할말은 없지만, 코드를 정리하지 않으면서 구현하면 .. 공감수 0 댓글수 0 2021. 4. 22.
[백준 17144번][Java] 미세먼지 안녕! www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 구현 문제입니다. 중요한 구현 포인트는 두 가지입니다. 1. 미세먼지 확산 2. 바람 방향으로 먼지 이동시키기 1번은 그리 어렵지 않습니다. 동시에 모두 확산해야하므로 임시 배열 하나를 생성해 확산 결과를 통합해주고, 원래 배열에 덮어쓰면 해결 2번은 어떻게 구현하느냐에 따라 꽤 헤깔릴 수 있습니다. 변수 설정하고 값 저장했다가 다시 옮기고... 이런 과정들이 너무 짜증나서 저는 경로를 쭉 따라가 deque에.. 공감수 0 댓글수 0 2021. 4. 21.
[백준 15685번][Java] 드래곤 커브 www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 풀면서 화딱지가 나서 때려칠까 몇번이나 고민했었던 문제였네요. 바로 본론으로 들어가서, 포인트는 한 점을 중심으로 어떤 점을 90도 이동시키는 함수를 만드는 일입니다. 드래곤 커브 특성상, 새로운 세대를 만들때 끝점을 중심으로 그 이전 점들을 하나씩 90도 이동시킵니다. 리스트로 구현하려면 리스트의 마지막이 끝점이 됩니다. 끝점의 참조를 저장해두고 역순으로 리스트를 순회하며 90도 회.. 공감수 0 댓글수 0 2021. 4. 21.
[백준 1662번][Java] 압축 www.acmicpc.net/problem/1662 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 포인트 유효한 괄호 단위로 문자열을 잘라 재귀로 넘기는게 포인트입니다. 여는 괄호가 나오면 이 여는 괄호의 짝인 닫는 괄호를 찾아줘야 됩니다. 그리고 그 문자열을 잘라 재귀로 넘겨주면서 글자 수를 계산하면 됩니다. 짝인 닫는 괄호를 구하는 방법은 간단합니다. 문자열을 순회하면서 openBracketCount(여는 괄호 수)를 세고 있다가 닫는 괄호가 나오면 하나씩 openBracketCount-1 해줍니다.. 공감수 0 댓글수 0 2021. 4. 20.
[14719번][Java] 빗물 www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 해결 방법 물을 가두는데 leftWall, rightWall가 필요하다고 합시다. leftWall에 임의의 높이가 정해졌다고 할때, rightWall의 높이가 이보다 크거나 같을 경우에만 그 사이 담긴 물의 양을 계산합니다. 그리고 이걸 정방향, 역방향으로 둘다 해줍니다. ... public class Main { static int H,N; public static void main(Stri.. 공감수 0 댓글수 0 2021. 4. 20.
[백준 2304번][Java] 창고 다각형 www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 오랜만이라서 그런지 절대 쉽지 않았습니다... 꽤 오래 걸렸네요. 핵심은 기둥이 높아질 때마다 지붕 높이를 갱신하고 넓이를 추가해준다는 점. 그리고 동일한 방법을 정방향, 역방향으로 수행하면서 전체 넓이를 계산하는 겁니다. 처음에 한 방향으로만 풀려고하니 복잡도가 확 올라가 버리더군요. 그리고 주의할 점은 정방향으로 쭉 가서 계산하면서 마지막 가장 높은 기둥의 위치를 저장해두고 그 지점까지만 역.. 공감수 0 댓글수 0 2021. 4. 20.
[백준 2573번][Java] 빙산 - 구현, 그래프 www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 쉬울 줄 알고 덤볐다가 꽤 시간을 잡아 먹은 문제입니다. 문제를 살펴보면 해야될 작업이 딱 두 가지가 떠오를 겁니다. 1. 쪼개지는 빙산의 개수 구하기 2. 배열을 순회하면서 얼음 녹이기 1번은 전형적인 그래프 컴포넌트 개수 구하기 문제입니다. 2번은 하나의 좌표가 주어질 때, 상하좌우에 0이 있는 개수만큼 값을 빼주면 되고요. 저는 1,2번 작업을 분리시켜서 구현했었는데, 시간 초과가 발생했습니다. 그래.. 공감수 0 댓글수 0 2020. 11. 10.
[백준 10757번][Java] 큰 수 A+B - 구현 https://www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 방법 1. 먼저 두 수 중 가장 긴 자릿수에 맞춰서 짧은 수 앞에 0을 붙입니다. 2. 맨 뒤에서부터 덧셈하는 하는데 합이 10 이상일 경우에 다음 자릿수 합에서 1을 더해줍니다. 아래 코드에서 주목할 만한 포인트 - 아래 구현에서 calculate(a,b)에서 항상 a b.length()) { String temp = a; a = b; b = temp; } System.out.println(calculate(a,b)); } /* 항상 b의 길이가 a보다 항상 크거나 같다 */ private stat.. 공감수 0 댓글수 0 2020. 11. 7.
[백준 16234번][Java] 인구 이동 - 그래프 탐색, 구현 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 그래프 탐색을 이용한 구현 문제였습니다. 풀이 방식 1. 전체 나라에 대해서 DFS하면서 인구 이동이 가능한 나라끼리 그룹으로 묶어 줍니다. 2. 1에서의 정보를 바탕으로 같은 그룹의 나라들의 값을 갱신합니다. 2번이 끝나고 다시 1번을 수행합니다. 그룹으로 묶어 주는 과정에서 그 어떠 나라도 국경을 열지 않았다면 그룹의 개수를 N*N개가 됩니다. 각 그룹은 자기 자신을 포함하는 그룹이 되겠지요... 공감수 0 댓글수 0 2020. 10. 31.
[백준 4195번] 친구 네트워크 - 상호 배타적 집합(disjoint set), 유니온 파인드 www.acmicpc.net/problem/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 종만북의 유니온 파인드 코드를 참조한 풀이입니다. 주의할만한 몇 가지 포인트에 대해서만 짚고 가겠습니다. 1. 이름을 int형의 id값으로 변환 문자열로는 트리를 구성하기 불편하기 때문에 int형으로 변환했습니다. 2. find 연산에서의 경로 최적화 이는 중복 연산을 피하기 위해 트리의 구조를 수정하는 작업입니다. find를 수행할 때마다 루트를 찾음과 동시에 경로에 있는 노드의 parent를 모두.. 공감수 0 댓글수 0 2020. 10. 27.
[백준 14890번][Java] 경사로 - 구현, 쉬운 듯 어려운 너 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제도 꽤 까다로웠네요. 주의할 점은 경사로를 만들 수 있는지 체크할 때 올라가는 방향, 내려가는 방향 모두 체크해야 된다는 점입니다. 그리고 해당 블럭에 경사로가 이미 설치되어 있는지도 기록해줘야 합니다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { sta.. 공감수 0 댓글수 0 2020. 10. 26.
[백준 1918번][Java] 후위 표기식 - 스택, 후위 표기식 변환 알고리즘 www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net dblab.duksung.ac.kr/ds/pdf/Chap05.pdf 위 pdf에 모든 알고리즘 설명이 들어가 있다. 꽤 유명한 문제였던 듯하다. 하지만 처음 문제를 접하면 풀기 쉽지 않을 듯한 문제다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class Main { .. 공감수 0 댓글수 0 2020. 10. 25.
[백준 15683번][Java] 감시 - 극한의 구현, 완전 탐색 www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 완전 탐색, DFS를 이용하면 풀 수 있는 문제다. 문제 자체의 알고리즘 난이도는 높지 않다. 하지만 한참 고민했던 문제다. 문제에서 cctv는 5가지 타입이 존재하고 타입별로 가능한 탐색 방향이 존재한다. 이를 단순하게 구현하려면 배열에 5가지 타입별로 각자 방향을 일일이 저장해두고 그대로 이용할 수도 있겠지만... 지저분해지는 코드가 눈에 선했기 때문에 이를 어떻게 구현할지 꽤 오랜 시간동안 생각.. 공감수 0 댓글수 0 2020. 10. 24.
[백준 17070번][Java] 파이프 옮기기 1 - DP, 메모이제이션 www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 자체는 DFS를 이용한 전형적인 길찾기 문제와 비슷했습니다. 주의할 점이라면 다음 좌표로 이동할 때, 주변에 장애물이 없는지 살펴야 합니다. 세로나 가로로 이동할 때는 상관이 없지만 대각으로 이동하는 경우에 이동하려는 좌표 위, 왼쪽이 모두 빈 공간이여야하기 때문입니다. package backjoon.dp.p17070; import java.io.*; import java.util.. 공감수 0 댓글수 0 2020. 10. 23.
[백준 2110번][Java] 공유기 설치 - 이분 탐색/중복된 요소 처리 www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 � www.acmicpc.net 해결하는데 굉장히 오래 걸렸습니다. 계속 분할 정복 방식으로 구간을 나눠 최적의 공유기 위치를 설치하려는 방식으로 접근했기 때문인데, 이 방식은 가능함의 여부를 떠나서(아마도 시간 제한에 걸릴 듯) 문제가 굉장히 복잡해지게 합니다. 관점을 살짝 바꿔야 합니다. 실제 수직선 위의 구간을 나눠가면서 공유기를 설치하는게 아니라, 최적화할 값들의 범위의 구간을 나.. 공감수 0 댓글수 0 2020. 10. 21.
[백준 2522번][Java] 사회망 서비스 - 트리, DP, 메모이제이션 www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망�� www.acmicpc.net 문제 풀이 얼리 어답터(EA)를 이용해 모든 아이디어를 퍼트리기 위해서는 다음의 규칙이 필요합니다. 1. 현재 노드가 EA인 경우 - 자식 노드가 EA인 경우 - 자식 노드가 EA가 아닌 경우 2. 현재 노드가 EA가 아닌 경우 - 모든 자식 노드가 EA여야 한다. 위의 규칙을 적용해 트리 구조에서 재귀를 이용해 해결할 수 있습니다. 재귀를 이용해 구현할 때, 리프노드에서의 종결 조건과 맞물려서 최소값.. 공감수 0 댓글수 0 2020. 10. 18.
[백준 1014번][Java] 컨닝 - 비트마스킹, DP, 메모이제이션 www.acmicpc.net/problem/1014 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 한달 전인가? 너무 어려워서 패스했던 문제였습니다. 그런데 지금은 풀리네요. 풀이가 보였습니다. (오오... 성장해버렸구나) 저는 DP와 비트마스킹을 이용해 풀었습니다. DP 문제를 풀 때 역시 가장 중요한 건 부분 문제를 정의하는 겁니다. arrageStudent(i, previousRowStatus) : 0 ~ i번째 영역에서 이전 행의 상태가 previousRowStatus 일 때 배치할 수 있는 최대 학생 수 위처럼 정.. 공감수 0 댓글수 0 2020. 10. 17.
[백준 1946번][Java] 신입 사원 - 정렬과 스택 www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net 문제 풀이 모든 지원자 중 자신보다 면접, 서류 분야 점수가 더 낮은 사람이 존재하는 경우 탈락하게 됩니다. 입력이 크기 때문에 N^2 로는 통과할 수 없습니다. 아래의 그림을 살펴보면 힌트를 얻을 수 있습니다. 빨간색으로 체크 친 지원자가 떨어지게 되는데, 해당 포인트는 점선으로 이뤄진 영역에 임의의 포인트를 포함합니다. 먼저 x축으로 입력을 정렬한 후 어떤 포인트를 포함하는 경우는 .. 공감수 0 댓글수 0 2020. 10. 16.
[백준 2565번][Java] 전깃줄 - 이름만 바뀐 LIS 문제 www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 바로 전에 LIS 문제를 풀었음에도 한참 헤맸습니다. 기존 LIS 로직을 그대로 쓰려면 입력 배열을 정렬할 필요가 있습니다. 정렬을 하지 않으려면 따로 처리를 해줘야 하는데 이 부분을 간과했네요. 정렬이 필요한 이유는 전깃줄이 꼬이는 조건과 관계가 있습니다. 줄 a,b가 있다고 할 때 줄이 꼬이지 않는 조건은 다음과 같습니다. - a.start b... 공감수 0 댓글수 0 2020. 10. 16.
[백준 1965번][Java] 상자 넣기 - 동적 계획법에 대한 고찰 www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 �� www.acmicpc.net 이 문제를 계기로 다시 종만북을 펼쳐서 DP를 다시 공부했는데, 새로운 깨달음을 얻을 수 있었습니다. 지금까지 DP 문제를 풀 때, 어떤 유형는 메모이제이션을 이용해 풀어야 되고 어떤 문제는 점화식을 찾아서 바텀업으로 풀어야 된다는 식으로 문제를 분류했었는데 그럴 필요가 없었습니다. 이때까지 바텀업 방식의 풀이를 이용했지만 약간은 불편했습니다. 뭔가 직관적이지 않다라는 느낌을 지울 수 없었기 때문입니다. 그럼에도 .. 공감수 0 댓글수 0 2020. 10. 14.
[백준 16236번][Java] 아기 상어 - 최단 거리에 있는 여러 노드들 정렬 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 그래프의 최단 거리 알고리즘을 기반으로 하는 구현 문제입니다. 이 문제의 포인트는 역시 최단 거리의 물고기를 찾고 선택하는 과정에 있습니다. 저도 여기서 한참 헤맸는데요. 문제의 조건을 이렇습니다. 1. 최단 거리의 물고기가 여러 마리일 때, 위쪽에 있는 물고기가 먼저 우선 순위를 가진다. 2. 높이가 같다면 왼쪽에 있는 물고기의 우선 순위가 더 높다. 제가 이 문제에서 헤맸던 이유는 .. 공감수 0 댓글수 0 2020. 10. 14.
[백준 2206번][Java] 벽 부수고 이동하기 - 3차원 BFS 이해하기 www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로�� www.acmicpc.net 이 문제를 제대로 이해하려면 기존의 기본적인 BFS 개념에 차원을 하나 더해야됩니다. 지도 위에 두 개의 층이 있다고 생각할 수 있습니다. 하나는 벽을 부수지 않은 경로를 표시하는 지도, 하나는 벽을 부수고 이동하는 경로를 나타내는 지도. 아래의 그림을 보면 쉽게 이해할 수 있을겁니다. 대부분의 간단한 BFS 예제들은 행렬 상의 2차원 평면에서 움직이지만, 이 문제는 벽을 부쉈는지 .. 공감수 0 댓글수 0 2020. 10. 13.
[백준 11438번][Java] LCA 2 - 희소 배열을 이용해서 LCA 구하기 www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net LCA 은 간단하게 트리 구조의 특성을 이용해 단순하게 해결했는데, 이번 문제는 효율성을 고려하지 않으면 풀 수 없었습니다. 영어로 LCA로 검색을 해보면 이 문제에 관해 여러 가지 풀이가 존재한다는 걸 알 수 있습니다. cp-algorithms.com/graph/lca.html Lowest Common Ancestor - O(sqrt(N)) and O(log N) with O(N) preproces.. 공감수 0 댓글수 0 2020. 10. 12.
[백준 11437번][Java] LCA - 최소 공통 조상 찾기 www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정� www.acmicpc.net 트리 구조의 특성을 생각해보면 풀이를 떠올릴 수 있다. 트리 구조에서 하나의 노드는 다수의 자식을 가질 수 있지만 부모 노드를 오직 하나만 가진다. 그렇기 때문에 각 노드에서 부모 노드의 참조를 저장해두면 두 개의 노드에서 따라올라가면서 최소 공통 조상을 찾을 수 있다. 까다로운건 이 문제에서 입력으로 트리를 구성하기 위해서는 일단 양방향 노드 그래프를 만들어야 되는데, 나는 그냥 한번 임시 트리를 만들.. 공감수 0 댓글수 0 2020. 10. 11.
[백준 1915번][Java] 가장 큰 정사각형 - 2차원 배열, DP www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net DP 문제를 계속 풀고 있는데, 패턴이 참 다양하다는 생각이 듭니다. 그리고 꽤 재밌네요 ㅋㅋㅋ 핵심 아이디어는 위처럼 (i,j) 위치의 값이 1일 때 위, 왼쪽 위, 왼쪽 위치의 요소도 1이면 정사각형 만들어 진다에서 출발합니다. 나머지는 저 위의 아이디어를 기반으로 점화식을 작성하면 됩니다. import java.io.*; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.. 공감수 0 댓글수 0 2020. 10. 10.
[백준 1937번][Java] 욕심쟁이 판다 - DP에서 메모이제이션 가능한 상황 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 이때까지 DP와는 성격이 조금 다른 문제였다. 이전까지는 단순히 완전 탐색의 바텀업 버전이었지만 이 문제는 재귀를 이용한 탑다운 방식에 cache배열을 추가하면서 해결할 수 있다. 이 문제에서 가장 중요한 한 문장이 있다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는.. 공감수 1 댓글수 0 2020. 10. 10.
[백준 9372번][Java] 상근이의 여행 - 그래프 순회 www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제를 제대로 이해만 하면 쉽게 풀 수 있는 문제입니다. 비행기의 종류에 간선 하나가 대응하기 때문에모든 도시를 탐색할 수 있는 최소한의 비행기 종류는 그냥 단순히 모든 노드를 다 탐색하는데 필요한 간선의 수입니다. 네. 그냥 단순 그래프 순회 문제입니다. import java.io.*; import java.util.ArrayList; import java.util.Lis.. 공감수 0 댓글수 0 2020. 10. 9.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.