알고리즘

문제 (Silver 2) https://www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 풀이 접근 설명 1과 0을 1과 -1이라고 생각하자! ( 부호의 차이로 생각하자! ) 2의 제곱 수(2,4,8,16,...)만큼 앞뒤로 대칭되고 있는 문자열! 즉, N보다 작은 2의 제곱수를 뺀 인덱스 값(N - (2*?)) 을 알면 N의 값을 알게 됨 위의 예시로 설명하자면, 27번째 값은 11번째 값과 같음(부호만 반대) 11번째 값은 3번째..

문제 (Silver 2) https://www.acmicpc.net/problem/3184 3184번: 양 첫 줄에는 두 정수 R과 C가 주어지며(3 ≤ R, C ≤ 250), 각 수는 마당의 행과 열의 수를 의미한다. 다음 R개의 줄은 C개의 글자를 가진다. 이들은 마당의 구조(울타리, 양, 늑대의 위치)를 의미한다. www.acmicpc.net 풀이 1. 양 또는 늑대가 있는 영역을 검사 (BFS) 2. 그래프를 돌며 양과 늑대의 위치 저장 3. 탐색 후, 양과 늑대 리스트 크기 비교 후 map에 반영 코드 더보기 import java.util.*; import java.io.*; public class Main { static int[] di = {-1,0,1,0}; static int[] dj =..

문제 (Bronze 5) https://www.acmicpc.net/problem/1032 1032번: 명령 프롬프트 첫째 줄에 파일 이름의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 파일 이름이 주어진다. N은 50보다 작거나 같은 자연수이고 파일 이름의 길이는 모두 같고 길이는 최대 50이다. 파일이름은 www.acmicpc.net 풀이 문자열을 캐릭터 배열로 변환하여 하나씩 비교하는 문제 코드 더보기 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStr..

문제 https://www.acmicpc.net/problem/16118 16118번: 달빛 여우 첫 줄에 나무 그루터기의 개수와 오솔길의 개수를 의미하는 정수 N, M(2 ≤ N ≤ 4,000, 1 ≤ M ≤ 100,000)이 주어진다. 두 번째 줄부터 M개의 줄에 걸쳐 각 줄에 세 개의 정수 a, b, d(1 ≤ a, b ≤ N, a ≠ b www.acmicpc.net 풀이 모든 정점에 대한 최단 경로를 탐색하는 다익스트라 알고리즘 문제 가장 중요한 고려사항은 늑대의 경우 홀수/짝수번째로 건넜을 경우를 각각 저장해 줄 수 있어야 함! 속도가 /2가 될 수 있으므로 소수점 방지를 위해 처음 입력 받을 시 weight에 *2 를 곱하여 저장! 다익스트라 알고리즘은 PriorityQueue를 사용하여 구현..