문제 https://programmers.co.kr/learn/courses/30/lessons/17683?language=java# 코딩테스트 연습 - [3차] 방금그곡 방금그곡 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, programmers.co.kr 풀이 문자열 파싱을 잘 하면 어렵지 않게 풀 수 있는 문제다. 아래와 같은 함수들을 작성해서 이용했다. 1. C# -> c, D# - >d 처럼 #이 붙은 문자열을 바꿔주는 함수 2. 12:00, 12:10 -> "10을 반환" 하는 것처럼 문자열에서 시간을 구하는 함수 자세한 내용은 코드를 참고하자. 코드 HTML ..
문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 트리의 지름을 구하기 위해서는 한 가지 규칙을 찾아내야한다. 그 규칙은 바로 트리의 지름은 리프노드와 리프노드 간의 거리라는 것이다. 따라서 모든 리프 노드에서 DFS탐색을 하여 다른 리프노드까지의 거리를 구하고, 최대 거리를 갱신하면 된다. 이때, 리프노드를 구별하는 방법은 루트노드가 아니면서 연결 노드가 1개(부모노드)뿐인 노드를 구하면 된다. 리프노드를 따로 구..
컴파일러(Compiler)란? 컴파일러는 특정 프로그래밍 언어로 쓰여 있는 문서를 다른 프로그래밍 언어로 옮기는 언어 번역 프로그램을 말한다. (출처:https://ko.wikipedia.org/wiki/%EC%BB%B4%ED%8C%8C%EC%9D%BC%EB%9F%AC) 컴파일러는 high-level 프로그래밍 언어(ex: C언어)를 low-level 언어(ex: 어셈블리어)로 바꾸어 실행 프로그램을 만들기 위해 사용된다. 원래의 문서를 소스코드 혹은 원시 코드라고 부르고, 출력된 문서를 목적 코드라고 부른다. 원시 코드에서 목적 코드로 옮기는 과정을 컴파일이라고 한다. 인터프리터(Interpreter)란? 인터프리터는 프로그래밍 언어의 소스 코드를 바로 실행하는 컴퓨터 프로그램 또는 환경을 말한다. (..
문제 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 이 문제는 다이나믹 프로그래밍을 이용해서 해결할 수 있다. Top-down 방식 혹은 Bottom-up 방식을 사용할 수 있는데, 나는 Bottom-up 방식을 사용하였다. dp 배열을 2차원 배열로 만들어서 사용하면 되는데, 그 의미는 다음과 같다. 예를 들어 dp[3][5]는 3번째 자릿수가 5일때 계단 수이다. 이걸 어떻게 구할 수 있을까? N=3일때 dp[3][5]는 dp[2][4] + dp[2][6] 이다. 즉, 두 번째 자릿수가 4이거나 6일때의 계단수를 더하면 된다. 이 때 주의해야 할 ..
문제 https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 이 문제는 간단한 정렬과 그리디 알고리즘을 적용하여 풀 수 있다. 먼저 크레인과 박스를 내림차순으로 정렬한다. 이후 크레인과 박스를 순차적으로 대조하여 옮길 수 있다면 박스 리스트에서 박스를 제거한다. 간단한 방법이지만, 자료구조를 어떤 것을 사용하냐에 따라서 시간초과가 발생할 수 있다. 나는 처음에는 box를 제거할 때 시간이 O(1)밖에 걸리지 않는 LinkedLis..
자동 push의 필요성 나는 매일 알고리즘 문제를 풀어서 GitHub에 push 하려고 노력하고 있다. 일명 1일 1커밋으로 잔디밭을 만들기 위해서이다. 따라서 매번 알고리즘 문제를 해결한 소스파일을 [그림 1]과 같이 Git 명령어를 직접 입력하여 push 했다. 이 과정이 너무 귀찮아서 클릭 한번으로 자동으로 push 해줄 수 있는 배치 파일을 만들기로 했다. .bat 파일 작성 만드는 방법은 아주 간단하다. 텍스트 파일로 아래와 같이 작성하면 된다. git add * git commit -m "auto push" git push origin master push 뒤에 자신이 remote로 등록한 이름으로 변경해주면 된다. 텍스트 파일에 위와 같이 입력한 후 해당 파일의 확장자를 .txt 에서 .ba..
문제 https://www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 풀이 N,M이 최대 4이므로 최대 2(가로,세로)^16=65536의 경우의 수가 있으므로 브루트포스 방식으로 해결가능하다. 재귀형식으로 각 원소를 가로로 택할지 세로로 택할지 선택할 수 있겠지만, 비트마스킹을 사용하면 더 간단하다. 예를 들어 아래와 같은 예제를 보자. 비트가 0이면 해당 숫자는 가로, 1이면 세로라고 판단하자. [그림 1]의 왼쪽그림은 오른쪽처럼 나타낼 수 있다. 이를 마..
문제 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net 풀이 나는 이 문제를 그리디 알고리즘을 사용해서 풀었다. 현재 점프할 수 있는 곳 중에서 그 칸에 도착했을 때 가장 멀리 갈 수 있는 곳으로 점프하면 가장 빠르게 도착할 수 있다. 현재 점프할 수 있는 곳 중에서 가장 멀리 점프한다는 뜻이 아니다! 예시를 보자. 아래와 같이 시작한다. 1 2 0 1 3 2 1 5 4 2 x 이 상황에서는 최대 한칸 밖에 못 가므로 그냥 한 칸을 뛴..
문제 https://www.acmicpc.net/problem/3273 3273번: 두 수의 합 n개의 서로 다른 양의 정수 a1, a2, ..., an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 www.acmicpc.net 풀이 이 문제는 두 가지 풀이가 가능하다. 첫번째는 Set을 이용한 방법이다. a + b = X 라는 식을 만족한다면, a = X-b 도 만족한다. 따라서 모든 원소를 Set에 넣은 다음, 첫 원소부터 탐색하며 X-i번째 원소가 Set에 존재한다면 두 수의 합이 X가 되는 것이므로 count 해준다. 이때 주의할 점은 이렇게 모든 원소를..