티스토리

다온 개발 일지

검색하기

블로그 홈

다온 개발 일지

daon-programming.tistory.com/m

공부하는_다온 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

알고리즘 리셋 작년 상반기에는 꽤나 열심히 알고리즘을 풀었다. 그러나 하반기부터 서서히 멀어졌고 점점 쉬운 문제만 찾아 풀게 되었다. 풀었던 문제라고 넘어가기도 하면서 알고리즘에 대한 기본기가 너무나 약해졌다는 생각이 들었다. 결론은새로운 백준 계정을 만들었고, 오늘부터 천천히 기본기를 탄탄히 쌓을 예정이다. (아무도 안 볼 글이겠지만 나 혼자 다짐하기 위해 이렇게 글을 남기고 간다.) 공감수 0 댓글수 0 2024. 3. 13.
백준 15565 귀여운 라이언 (Java) 1. 문제 링크 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 라이언이 K개 이상 포함되는 범위의 크기를 위해 투포인터로 구했다. 2. K개가 될때까지 오른쪽으로 늘리는데, 오른쪽에 라이언이 오면 추가하고, K개 이상이 되면 넘어간다. 3. K개의 경우, 최솟값이 되는지 확인한다. 4. 다음으로 넘길 때, 제일 왼쪽이 라이언일 경우 1을 뺀다. 4. 코드 import java.io.BufferedReader; import java.io.IOException;.. 공감수 0 댓글수 0 2023. 9. 19.
백준 13335 트럭 (Java) 1. 문제 링크 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 트럭 큐에 각 트럭의 무게를 저장한다. 2. 다리의 각 위치마다 트럭 무게를 넣는 큐를 만든다. 2-1. 처음에는 다리에 아무 트럭이 없기 때문에 모든 위치에 0을 넣는다. 3. 시간이 지나면서 다리 위치를 옮기기 위해 다리 큐에서 하나를 뺀다. 4. 지나올 트럭이 남아있으면 최대 하중을 확인한다. 4-1. 지금 순서의 트럭이 추가되어도 최대 하중을 넘지.. 공감수 0 댓글수 0 2023. 9. 17.
백준 1939 중량제한 (Java) 1. 문제 링크 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 최대 중량을 넘지 않는 최댓값을 찾아야 한다. 2. 두 섬을 연결시켜야 해서 BFS 탐색을 이용했고, 시간 초과를 생각해 이분 탐색을 함께 이용했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ja.. 공감수 0 댓글수 0 2023. 9. 16.
백준 2056 작업 (Java) 1. 문제 링크 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 위상정렬을 이용하여 문제를 풀었다. 2. 선행되는 작업을 먼저 처리한 후, 진입 차수가 0이 되면 큐에 넣어 작업이 되도록 했다. 3. dp를 이용하여 지금까지 누적 + 다음 노드의 시간 vs 다음의 누적 중 큰 값을 저장했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR.. 공감수 0 댓글수 0 2023. 9. 14.
백준 2831 댄스 파티 (Java) 1. 문제 링크 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 키가 작은 여자와 키가 큰 여자, 키가 작은 남자와 키가 큰 여자로 나누어서 저장한다. 2. 전부 정렬한다. 3. 여자와 남자 각각 인덱스 번호를 가지고, 조건이 성립하는 경우에만 커플의 수를 증가한다. 4. 그 외에는 조건에 맞을 때까지 키가 커야 하는 조건의 사람이 커질 때까지 인덱스 번호를 증가한다. 4. 코드 import java.io.BufferedReader; import java.io.. 공감수 0 댓글수 0 2023. 9. 12.
백준 15684 사다리 조작 (Java) 1. 문제 링크 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 사다리의 연결된 가로선으로 (1) - (-1)로 저장해 연결 여부를 판단했다. 2. 가로선을 1, 2, 3개 추가한 순서로 dfs를 진행했다. 3. 선을 하나씩 추가하는데 3개가 넘지 않도록 하면서, 다른 가로선과 연결되지 않게 했다. 4. 한 가로선을 추가할 때마다 i번이 i번에 도착하는지 확인하고, 다른 사다리에 영향을 끼치지 않도록 다시 뺐다. 4. 코드 import java.io.Buffere.. 공감수 0 댓글수 0 2023. 9. 11.
백준 2623 음악프로그램 (Java) 1. 문제 링크 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. PD의 수만큼 ArrayList를 만든다. 2. 입력받은 순서대로 list에 넣으면서 진입차수를 더해준다. 3. 위상정렬을 진행한다. 3-1. 처음에 진입차수가 0인(선행되는 수가 없는) 숫자를 큐에 넣는다. 3-2. 큐에서 빼고 결과 list에 추가한다. 3-3. 그 수와 연결된 숫자들의 진입차수를 하나씩 빼면서 0이 될 때 큐에 넣는다. 4. 위상 정렬이 끝난 후 결과 list.. 공감수 0 댓글수 0 2023. 9. 9.
백준 14226 이모티콘 (Java) 1. 문제 링크 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 최소 시간을 구하는 문제라 BFS 탐색을 이용했다. 2. 큐에 지금 이모티콘 수(now), 클립보드에 있는 이모티콘 수(save), 연산 횟수(cnt) 3가지를 넣는다. 3. 원하는 이모티콘 수가 나올 때까지 반복한다. 3-1. now가 0보가 크고, [now][now]에 방문한 적이 없는 경우에, 클립보드로 복사한다. 3-2. save가 0보다 크고, now+save가 2000보다 작고, [now+sa.. 공감수 0 댓글수 0 2023. 9. 8.
백준 2448 별 찍기 - 11 (Java) 1. 문제 링크 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 아래의 모양이 반복된다는 규칙을 찾을 수 있다. * * * ***** 2. 위에서 아래로 트리의 가지를 치는 느낌으로 가면서 삼각형을 만들어가기 위해 재귀를 이용했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; public class Main { static char[][] m.. 공감수 0 댓글수 0 2023. 9. 7.
백준 1744 수 묶기 (Java) 1. 문제 링크 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 큰 순으로 정렬해서 곱한다. 2. 1은 무조건 더한다. 3. 양수의 경우 조건 3-1. 양수가 짝수일 경우, 큰 순서대로 2개씩 묶어서 더한다. 3-2. 양수가 홀수일 경우, 큰 순서대로 2개씩 묶어서 더하고, 남은 하나는 그냥 더한다. 3-3. 양수가 하나인 경우, 그냥 더한다. 4. 음수의 경우 조건 4-1. 음수가 짝수일 경우, 큰 순서대로 2개씩 묶어서 큰 양수로 만들어 더한다. 4-2. 음.. 공감수 0 댓글수 0 2023. 9. 6.
백준 1726 로봇 (Java) 1. 문제 링크 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. BFS 탐색을 통해 도착점에 원하는 방향으로 도착하면 끝낸다. 2. Go 1,2,3 을 이용한 1번 명령을 진행하여 이동 위치를 가지고 판단한다. 2-1. 이동 위치가 공장 내에 위치하는지 확인한다. 2-2. 이동 위치에 궤도가 깔려 있는지 확인한다. 2-3. 이동 위치를 방문한 적이 있는지 확인한다. 3. Turn left, right를 이용해 90도 회전한다. 3-1. 동/서 => 남/북, 남/북 => 동/.. 공감수 0 댓글수 0 2023. 9. 5.
백준 1749 점수따먹기 (Java) 1. 문제 링크 1749번: 점수따먹기 동주는 항상 혼자 노느라 심심하다. 하지만 혼자 놀기의 고수가 된 동주는 매일매일 게임을 개발하여 혼자놀기의 진수를 우리에게 보여준다. 어느 날 동주는 새로운 게임을 개발하였다. 바로 점 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 2차원 배열을 이용한 구간 누적 합으로 구했다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new.. 공감수 0 댓글수 0 2023. 9. 4.
백준 1238 파티 (Java) 1. 문제 링크 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 시작점 리스트에 끝점과 소요 시간을 담는다. 2. 다익스트라를 이용해서 최단 시간을 구한다. 3. 파티에 가는 시간과 파티에서 오는 시간을 합쳐 최댓값을 구한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.A.. 공감수 0 댓글수 0 2023. 9. 3.
백준 12904 A와 B (Java) 1. 문제 링크 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A로 B를 만들기에는 매번 2연산씩 하면서 계산이 많아질 것으로 생각했다. 2. B의 마지막 자리를 확인하고 그 문자에 따른 연산을 실시했다. 2-1. 마지막 문자를 저장한다. 2-2. 마지막 문자를 문자열에서 지운다.(deleteCharAt()) 2-3. 마지막 문자가 B였다면 뒤집는다. (reverse()) 3. 남은 문자열이 같은 경우에 1을 출력하고, 다르다.. 공감수 0 댓글수 0 2023. 9. 2.
백준 1188 음식 평론가 (Java) 1. 문제 링크 1188번: 음식 평론가 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100) www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. M과 N의 최대공약수를 구한다. 2. 나눠줄 양이 최대공약수이기 때문에 평론가 수에서 빼면 된다. +) 나눠야 된다는 생각에 어떻게 나눌지 생각하다가 최대공약수로 풀게 되었다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { Buffer.. 공감수 0 댓글수 0 2023. 9. 1.
백준 22945 팀 빌딩 (Java) 1. 문제 링크 22945번: 팀 빌딩 개발자 $N$명이 팀 빌딩을 위해 한 줄로 서있다. 하나의 팀을 만들기 위해서는 개발자 2명이 반드시 모여야 한다. 개발자 A와 개발자 B가 팀을 만들 때 팀의 능력치는 아래와 같이 계산이 된다. (개 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 맨 앞의 사람과 맨 뒤의 사람을 기준으로 능력치를 계산한다. 2. 두 개발자 사이의 거리와 능력치의 곱이 최대가 되어야 하기 때문에 둘 다 최대인 경우를 찾아야 한다. 3. 비교 대상 중 큰 값은 유지하고, 거리를 줄이면서 그 곱이 최댓값이 되는지 확인한다. 4. 계산에 사용되는 더 작은 값의 인덱스를 바꾸고 반복한다. 4. 코드 import java.io.BufferedReader; impo.. 공감수 0 댓글수 0 2023. 7. 9.
백준 8983 사냥꾼 (Java) 1. 문제 링크 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 이분탐색을 위해 입력받은 사대의 위치들을 정렬한다. 2. 동물마다 이분탐색을 진행하여 사냥이 가능한지 확인한다. 3. 중간 사대 기준으로 해당 사대가 사정거리 내에 있는지 판단한다. 3-1. 사정거리 내에 있다면 true를 리턴한다. 3-2. 사정거리 밖인데 x좌표가 같은 경우 사냥이 불가능하기 때문에 false를 리턴한다. 3-3. 동물이 앞.. 공감수 0 댓글수 0 2023. 7. 7.
백준 14938 서강그라운드 (Java) 1. 문제 링크 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 다익스트라를 이용해 풀었다. 2. 연결 노드를 가면서 저장된 거리보다 작은 경우이면서 수색 범위 안에 있는 노드를 찾는다. 3. 저장된 거리를 갱신하고, 우선순위 큐에 집어 넣는다. 4. 각 지역에서 다익스트라를 진행했을 때 최댓값을 찾아 출력한다. 4. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStre.. 공감수 1 댓글수 1 2023. 7. 6.
백준 2615 오목 (Java) 1. 문제 링크 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 바둑이 놓여져 있는 칸에서 팔방탐색을 통해 오목이 만들어지는지 확인한다. 2. 한 방향으로 5칸을 가면서 5칸까지만 같은 색인지 확인하고, 같은 색이면 PriorityQueue에 좌표를 넣는다. 3. 다섯 알 연속이 만들어졌으면 반대 방향 한 칸을 확인해 여섯 알 이상이 되는지 확인한다. 4. 오목이 만들어졌다면 PriorityQueue에서 정렬된 좌상단 위치를 저장한다. 4. 코드 import ja.. 공감수 0 댓글수 0 2023. 7. 5.
백준 17218 비밀번호 만들기 (Java) 1. 문제 링크 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dp 이차원 배열을 만들어 현재 위치까지의 최장길이를 저장한다. 2. 뒤에서부터 둘 중 하나를 다 읽을때까지 반복한다. 2-1. 현재 두 인덱스에서의 값이 동일할 경우 결과 앞에 더하고 각 인덱스 값에 1을 뺀다. 2-2. 같지 않은 경우에는 dp배열에서의 값이 작은 문자열 길이 인덱스 값에서 1을 뺀다. 4. 코드 import java.io.BufferedReader; import java.io.. 공감수 0 댓글수 0 2023. 7. 4.
백준 2666 벽장문의 이동 (Java) 1. 문제 링크 2666번: 벽장문의 이동 첫 번째 줄에 벽장의 개수를 나타내는 3보다 크고 20보다 작거나 같은 하나의 정수, 두 번째 줄에 초기에 열려있는 두 개의 벽장을 나타내는 두 개의 정수, 그리고 세 번째 줄에는 사용할 벽장들 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 열러 있는 두 곳의 위치와 사용 벽장 위치, 총 이동 횟수로 DFS 탐색을 진행한다. 2. 이동 횟수가 결과 보다 크다면 끝낸다. 3. 마지막 벽장까지 다 사용했다면 결과와 이동 횟수 중 작은 값을 결과로 저장한다. 4. 왼쪽 벽장을 사용 벽장으로 정한 경우와 왼쪽 벽장을 사용 벽장으로 정한 경우 각각으로 DFS 탐색을 진행한다. 4. 코드 import java.io.BufferedReader; .. 공감수 0 댓글수 0 2023. 7. 2.
백준 17836 공주님을 구해라! (Java) 1. 문제 링크 17836번: 공주님을 구해라! 용사는 마왕이 숨겨놓은 공주님을 구하기 위해 (N, M) 크기의 성 입구 (1,1)으로 들어왔다. 마왕은 용사가 공주를 찾지 못하도록 성의 여러 군데 마법 벽을 세워놓았다. 용사는 현재의 가지고 있는 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 저주 제한 시간 동안 BFS 탐색으로 사방탐색을 한다. 2. 빈 공간이라면 가서 큐에 넣고 방문처리한다. 3. 무기가 있는 곳이라면 큐에 좌표와 1(무기 소지)을 넣고 방문처리한다. 4. 벽이라면 큐에서 꺼낸 배열의 마지막 값이 1인 경우에만 큐에 넣고 방문처리한다. 5. 저주 시간 안에 공주에 도착하면 도달 시간을 출력하고, 도착하지 못하면 Fail을 출력한다. 4. 코드 import.. 공감수 0 댓글수 0 2023. 7. 1.
백준 16197 두 동전 (Java) 1. 문제 링크 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 주어진 보드를 입력받으면서 동전을 따로 저장한다. 2. BFS 탐색을 이용하여 최소 횟수를 구한다. 3. 현재 동전 2개를 큐에 넣고, 해시값으로 방문처리를 진행했다. 4. 큐에서 꺼낸 동전들을 각각 사방탐색을 진행한다. 4-1. 1번 동전만 떨어진 경우와 2번 동전만 떨어진 경우 종료해야 하기 대문에 현재 횟수를 리턴한다. 4-2. 두 동전이 다 떨어진 경우나, 둘 다 벽으로 간다면 넘어간다. 4-.. 공감수 0 댓글수 0 2023. 6. 30.
백준 1937 욕심쟁이 판다 (Java) 1. 문제 링크 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dfs 탐색으로만 하려다 크기가 큰 것 같아 이동 칸을 저장하기 위한 dp까지 함께 사용했다. 2. 모든 칸에서 dfs 탐색을 진행한다. 2-1. dp가 이미 채워져 있을 경우, 그 값을 반환한다. 2-2. 첫 방문일 경우, 한 칸을 뜻하는 1을 저장한다. 2-3. 사방 탐색을 하면서 지금보다 더 많은 대나무가 있는 곳으로 이동한다. 4. 코드 import java.io.BufferedRe.. 공감수 0 댓글수 0 2023. 6. 29.
백준 1647 도시 분할 계획 (Java) 1. 문제 링크 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. MST 문제로 크루스칼 알고리즘을 이용했다. 2. 노드를 가중치 기준으로 정렬한다. 3. 두 집이 연결되어 있지 않다면 연결한다. 4-1. 1번 코드는 전체를 다 연결하고 최대 연결 수까지의 값을 더한 것이다. 4-2. 2번 코드는 전체를 다 연결하고 최댓값 하나만 빼준 것이다. 4. 코드 import java.io.BufferedReader; import jav.. 공감수 0 댓글수 0 2023. 6. 28.
백준 18430 무기 공학 (Java) 1. 문제 링크 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. DFS 탐색을 통해 만들 수 있는 모든 부메랑의 경우를 찾는다. 2. 방문하지 않은 곳에서 만들 수 있는 4가지 부메랑을 만들어본다. 2-1. 각 부메랑의 조건을 통과하면 방문처리 후 dfs를 진행한다. 2-2. DFS가 끝나고 돌아오면 방문처리를 다시 원래대로 돌려둔다. (다른 경우에 영향 끼치지 않도록) 4. 코드 import java.io.BufferedReader; import.. 공감수 0 댓글수 0 2023. 6. 26.
백준 2156 포도주 시식 (Java) 1. 문제 링크 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. dp로 풀었다. 2. 2번째 잔까지는 3연속을 신경쓰지 않아도 되기에 더한 값을 넣는다. 3. 3번째 잔 부터는 연속 3개가 안되기 때문에 비교하여 더 큰 값을 저장했다. 3-1. 지금잔을 선택하지 않는 경우 3-2. 하나 앞의 잔을 선택하지 않고, 지금 잔을 선택하는 경우 3-3. 두개 앞의 잔을 선택하지 않고, 하나 앞의 잔과 지금 잔을 선택하는 경우 4. 코드 import java.io.Buffe.. 공감수 0 댓글수 0 2023. 6. 25.
백준 12886 돌 그룹 (Java) 1. 문제 링크 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. A, B, C를 입력받고, 만들 수 있는 돌 개수로 2차운 배열을 만든다. 2. 3 그룹의 합이 3의 배수가 아니라면 같은 개수로 나눌 수 없다. 3. DFS 탐색을 진행하며 A, B, C가 같은 개수가 나오는지 확인한다. 3-1. A와 B, B와 C, C와 A를 각 단계에서 전부 비교해보면서 나오는지 확인한다. 3-2. 방문 배열을 통해 작은 값과 큰 값이 나왔었는지 확인하고, 그 값들로 DFS.. 공감수 0 댓글수 0 2023. 6. 24.
백준 14442 벽 부수고 이동하기 2 (Java) 1. 문제 링크 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 2. 문제 및 입출력예제 3. 문제 풀이 1. 입력을 받고 시작 위치인 0,0에서 부순 벽 개수 0으로 시작한다. 2. BFS로 돌면서 방문 처리를 한다. (해당 위치에서 몇개의 벽을 부쉈는지 확인) 3. size만큼 반복하면서 이동 거리를 더한다. 4. 큐에서 하나씩 뺀다. 4-1. 뺀 위치가 종료 위치라면 끝낸다. 4-2. 아니라면 사방탐색을 진행한다. 4-3. 해당 위치에 벽이 없으면 현재 부순 벽 개수로 .. 공감수 0 댓글수 0 2023. 6. 23.

문의안내

티스토리
로그인
고객센터

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