CVillain

https://www.acmicpc.net/problem/5022 5022번: 연결 A1과 A2, 그리고 B1과 B2를 연결하는데 필요한 전선의 길이의 최솟값을 출력한다. 만약, 불가능한 경우에는 "IMPOSSIBLE"을 출력한다. www.acmicpc.net 문제 전기 회로에서 두 점을 전선으로 이을 때, 길이는 짧을 수록 좋다. 크기가 N×M인 비어있는 회로판에서 두 점 A1과 A2, 그리고 B1와 B2를 전선을 이용해서 이으려고 한다. 전선은 항상 그리드의 수직, 수평선 위에 있어야 한다. 또, 두 직선은 접하면 안 된다. 이 경우에 필요한 전선의 길이의 최솟값을 구하는 프로그램을 작성하시오. 전선은 회로판 바깥으로 나갈 수 없다. 입력 첫째 줄에 회로판의 크기 N과 M이 주어진다. (2 ≤ N, ..

https://www.acmicpc.net/problem/5213 5213번: 과외맨 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 500) 다음 줄부터 N*N-N/2줄(/는 정수 나눗셈이다)에는 두 양의 Ai와 Bi가 주어진다. (1 ≤ Ai, Bi ≤ 6, 1 ≤ i ≤ N * N - N / 2) 타일 i의 왼쪽에 쓰여 있는 숫자는 Ai, 오른 www.acmicpc.net 문제 과외맨은 평소에 서강대학교 학생 이민혁으로 위장하고 있는 한국의 대표적인 영웅이다. 그는 슈퍼 히어로가 너무 미국에 집중되어 있는 현실을 안타까워했고, 그의 절친한 친구인 스파이더맨과 아이언맨에게 한국으로 와서 같이 영웅 활동을 하자는 제안을 했으나 거절당했다. 얼마 전, 오랜 잠에서 깨어난 고대 마야인들이 과외맨이 수업을 듣는 ..

https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문제 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수빈이는 간단한 게임을 만들기로 했다. 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게임이다. 문자열을 바꿀 때는 다음과..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-y..

RESTful API REST란 Representational State Transfer의 약자로써 ~ful이라는 형용사형 어미를 붙여, REST한 API라는 표현으로 사용된다. 즉, REST의 기본 원칙을 성실히 지킨 서비스 디자인은 RESTful하다고 표현할 수 있다. REST는 "디자인 패턴이다" 혹은 "아키텍처다" 라는 의견이 분분한데, 하나의 아키텍처로 볼 수 있다. 좀 더 정확한 표현으로 말하자면, REST는 Resource Oriented Architecture이다. API 설계의 중심에 자원(Resource)가 있고, HTTP Method를 통해서 자원을 처리하도록 설계하는 것이다. ▣ REST 6가지 원칙 Uniform Interface Stateless Caching Client-Ser..

문제 가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다 타일을 가로로 배치 하는 경우 타일을 세로로 배치 하는 경우 예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. 제한 사항 가로의 길이 n은 5,000이하의 자연수 입니다. 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요. 풀이 전에 풀었던 2 x n 타일링 문제..

문제 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 "hit", target가 "cog", words가 ["hot","dot","dog","lot","log","cog"]라면 "hit" -> "hot" -> "dot" -> "dog" -> "cog"와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환..

문제 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를들어 - 0ms 시점에 3ms가 소요되는 A작업 요청 - 1ms 시점에 9ms가 소요되는 B작업 요청 - 2ms 시점에 6ms가 소요되는 C작업 요청 와 같은 요청이 들어왔습니다. 이를 그림으로 표현하면 아래와 같습니다. 한 번에 하나의 요청만을 수행할 수 있기 때문에 각각의 작업을 요청받은 순서대로 처리하면 다음과 같이 처리 됩니다. - A: 3ms 시점에 작업 완료 (요청에서 종료까지 : 3ms) - B: 1ms부터 대기하다가, 3ms 시점에 작업을 시작해서 12ms 시점에 작업 완료(요청에서 종료까지 : 11ms)..

다음 숫자들을 오름차순으로 정렬하시오. 2, 4, 5, 1, 3 앞의 선택 정렬과 버블 정렬은 시간 복잡도 O(N2)을 가지는 정렬 알고리즘이었다. 그렇다면 삽입 정렬의 시간 복잡도는 어떻게 될까? 우선, 삽입 정렬은 각 숫자를 적절한 위치에 삽입하는 방법으로 동작한다. 선택 정렬, 버블 정렬은 무조건 위치를 바꾸는 방식이었다면, 삽입 정렬은 필요할 때만 위치를 바꾸게 된다. 그럼 앞선 정렬 방식보다 효율적일까? 정답은 NO! 삽입 정렬은 기본적으로 '정렬이 되어있다고 가정'을 한다는 점에서 특정한 경우에 따라 굉장히 빠른 속도를 낼 수 있다. 하지만 반복문이 두 번 들어가있기 때문에 최악의 경우 시간 복잡도가 O(N2)이 될 수 있다. 그림으로 살펴보자! 처음 두 수 2, 5는 2가 더 앞에 있으므로 ..

다음 숫자들을 오름차순으로 정렬하시오. 2, 5, 4, 1, 3 버블 정렬 또한 선택 정렬과 마찬가지로 몹시 직관적인 정렬 방법이다! 바로 옆에 있는 숫자를 비교해서 더 작은 숫자를 앞으로 보내는 방법으로 동작한다. ※ 버블 정렬은 정렬 알고리즘 중에서 구현은 가장 쉽지만 가장 비효율적인 알고리즘 그림으로 살펴보자! 먼저 첫 번째 자리를 구하는 방법이다. 바로 옆에 있는 숫자와 비교해서 더 작은 숫자를 앞으로 보냈다. 두 번째 자리 숫자를 구하는 방법도 같다. 첫 번째 자리는 구했으므로 두 번째까지만 비교를 한다. 계속해서 세 번째 자리를 구해보면 다음과 같다. 이미 정렬이 되었으므로 네 번째 자리는 바꿀 필요가 없다. 코드로 확인해보면 다음과 같다. public class Main { public st..