본문 바로가기

전체 글

백준 - 1865 웜홀(Java) https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 벨만-포드 문제입니다. 벨만-포드 알고리즘은 음의 가중치가 있을 때, 최소 거리를 구하기 위해 사용됩니다. 만약, 양의 가중치만이 있을 때 사용되는 다익스트라와 대조됩니다. 벨만-포드는 노드 n개가 있을 때, n-1 번 거리를 갱신한 후에 한 번 더 갱신합니다. 만약 한 번더 갱신이 되면 음의 사이클이 존재하는 것입니다. 이 문제의 경우 음의 사이클이 발생하는지 확인하기 위해 벨만-포.. 더보기
백준 - 5639 이진 검색 트리(Java) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 탐색 문제입니다. 전위 탐색 정보를 사용하여, 후위 탐색 정보를 출력해야 합니다. 전위 탐색은 다음과 같습니다. void pre(Node node){ print(node); pre(node.left); pre(node.right); } 즉, 전위 탐색은 현재 노드를 출력하고 좌측부터 탐색을 하는 방법입니다. 때문에, 입력에서 주어지는 첫 번째 입력은 루트 노드라는 것을 알 수 있습니다.. 더보기
백준 - 2230 수 고르기(Java) 투포인터 문제입니다. n개의 숫자 중 두 개의 숫자를 고를 때, 두 수의 차이가 m이상이면서 최소가 되는 경우를 구해야합니다. 문제 접근 순서는 다음과 같습니다. 입력 값을 정렬한다. 두 개의 포인터(lp, hp)를 움직여 차이를 구한다. 초기 위치는 lp=0, hp=1이다. lp, hp위치의 값 차이가 m보다 크면 차이를 줄인다. (lp를 앞으로 움직인다.) lp, hp위치의 값 차이가 m보다 작으면 차이를 늘린다. (hp를 앞으로 움직인다.) lp가 n-1에 도달할 때 까지 반복한다. (hp가 n에 도달하고, lp가 n-1까지 도달하는 경우이다.) 저장된 최소 차이를 출력한다. [구현 코드] import java.io.*; import java.util.Arrays; import java.util.S.. 더보기
백준 - 17609 회문(Java) 구현 문제입니다. 각 테스트 케이스에서 문장이 주어질 때, 해당 문장이 회문 or 유사 회문 or 일반 문장인지 확인하는 문제입니다. 회문일 경우 0 유사 회문일 경우 1 일반 문장일 경우 2 회문을 판단하는 방법은 앞, 뒤의 문자를 확인하면 됩니다. for(int i=0; i < (n/2); i++){ if(senChars[i] != senChars[n-1-i]){ // 앞, 뒤 문자가 같지 않을 경우(회문이 아닌 경우) } } 문제 접근 순서는 다음과 같습니다. 큐에 문장을 넣는다. 문장이 회문인지 확인한다. 회문이 아니라면 회문이 아닌 곳을 기준으로 문장을 자른다. 자른 문장을 큐에 넣는다. 회문인지 확인한다. 큐의 반복 횟수에 따라 회문 or 유사 회문 or 일반 문장을 판단한다. 그림과 같이 x.. 더보기
백준 - 17406 배열 돌리기4(Java) 순열 문제입니다. 회전 정보가 주어졌을 때, 각 행의 최소 합을 구하는 문제입니다. 문제 조건에 나와있듯이, 회전 순서에 따라 행의 최소 합이 달라집니다. 접근 순서는 다음과 같습니다. 회전 정보를 저장한다. 회전 정보를 바탕으로 정보의 순열을 구한다. 순열 만큼 반복하여 회전하여 행의 최소 합을 구한다. ※ 주의할 점 직사각형 회전이 아닙니다. 제일 먼저 바깥쪽 테두리를 회전하고, 안쪽 테두리를 회전해야 합니다. 재귀를 통해 구현할 수 있습니다. [구현 코드] import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { private static.. 더보기
백준 - 15686 치킨 배달(Java) 조합(백트랙킹) 문제입니다. N*N의 맵에서 M개 이상의 치킨 집이 주어집니다. M개 이상의 치킨 집을 M개의 치킨 집만을 만들어 각 집에서의 최소 거리를 구해야 하는 문제입니다. 즉, M개 이상의 치킨 집을 조합으로 M개로 만들어 거리를 구하는 완전탐색 문제인 것입니다. [구현 코드] import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { private static int n, m; private static List chickens, homes; private static List combis; // 치킨 집 조합 public static.. 더보기
백준 - 24955 숫자 이어 붙이기(Java) bfs 문제입니다. 문제의 설명이 복잡하지만, 요약하면 다음과 같습니다. 노드의 개수는 N개이다. 간선의 개수는 N-1개이다. (최소신장트리) 각 노드마다 숫자(가중치)가 주어지는데, 시작 노드 부터 도착 노드 까지 갈 때의 숫자를 이어 붙여라. (덧셈 아닙니다. 문자열로 만들어 이어 붙이는 것입니다.) 입력을 요약하면 다음과 같습니다. 첫 번째 줄에는 노드의 개수인 N과 탐색 횟수인 Q가 주어진다. 두 번째 줄에는 각 노드의 가중치가 주어진다. 세 번째 줄 부터 N-1개 만큼 연결 정보(간선)이 주어진다. 마지막으로 Q개 만큼 탐색할 시작 노드와 도착 노드가 주어진다. 예제 입력1을 그림으로 표현하면 다음과 같습니다 예제 입력 네 번째 줄 까지가 트리의 정보입니다. 다 섯번째 줄 부터 Q개 만큼 탐색할.. 더보기
백준 - 16197 두 동전(Java) bfs 문제입니다. 보드의 크기는 N*M입니다. 보드 위에 두 개의 동전, 빈칸, 벽(이동 불가능한 위치) 가 주어집니다. o : 동전 . : 빈칸 # : 벽 버튼을 누르면 두 개의 동전이 동시에 네 방향(상, 하, 좌, 우) 중 한 방향으로 움직일 때, 단 한 개의 동전만 떨어뜨리는 최소 경우의 수를 구하는 문제입니다. 문제 접근 순서는 다음과 같습니다. 동전이 하나만 떨어져 있는지 확인한다.(최소 갱신) 동전을 네 방향으로 움직인다. (벽이 있는지 확인해야 한다.) 동전을 움직였을 때, 두 개의 동전 상태를 구한다. 1번을 반복한다. ※ 주의 사항 최소 버튼을 누르는 경우의 수가 10 초과일 경우 -1을 반환해야 합니다. 저는 10 이상으로 했었어서 오늘도 삽질을 했습니다.... 또한, 문제를 잘못 .. 더보기

티스토리툴바