koucop의 개발탐방기 koucop의 개발탐방기

이번에는 백준알고리즘의 5355번 문제 화성수학을 풀어보도록 하자 문제에 나와있는 부분은 살짝 이해하기 어렵게 되어있으므로, 예제를 보면서 문제를 설명하도록 하겠다. 일단, 입력으로 테스트케이스의 개수 T가 주어지고 그 다음 줄부터 하나의 숫자와 연산자(@, %, #)가 띄어쓰기로 주어진다. @는 3을 곱하는 연산자 %는 5를 더하는 연산자 #은 7을 빼는 연산자이고, 출력으로 각 테스트 케이스에 대해서 결과를 소수점 둘째자리까지 구하면 된다. 예제로 주어진, 3 @ % 는 (3 * 3) + 5 이고, 이것은 14가 되는데, 소수점 둘째자리까지 구하라고 하였으므로, 14.00을 출력값으로 넣어주면 된다. 성공한 코드는 아래와 같다. import java.io.*; import java.util.*; pu..

이번에는 백준 알고리즘의 1107번 문제 "리모컨"을 풀어보도록 하자 문제가 살짝 복잡한데, 수빈친구가 가지고 있는 리모컨의 일부 숫자 버튼이 고장났다. 수빈이가 현재 보고 있는 채널은 100번이고, 입력으로 수빈이가 이동하려고 하는 채널 N, 고장난 버튼의 개수 M, 그리고 고장난 버튼이 있는 경우에 셋째줄에 고장난 버튼이 주어지고, 출력으로 채널 N 으로 이동하기 위해 버튼을 최소 몇번 눌러야 하는지를 출력하는 문제인데, 입력으로 주어지는 채널이 500,000이므로 반복문으로 여러번 판별해주다 보면 시간초과가 뜰 위험이 있다. 이것을 주의하면서 문제를 풀면 된다. 일단 부르트포스(완전탐색)으로 문제를 풀었다. 총 이동가능한 채널의 개수는 입력의 상한이 500,000 이었으므로, 1,000,000(백만..

이번에는 백준 알고리즘의 1806번 문제, "부분합"을 풀어보도록 하자 일단 이번 문제에서 입력은 수열의 길이 N 과 연속된 수들의 합의 판단기준이 될 S 가 주어지고, 두번째 줄에는 해당 수열이 주어진다. 출력으로는 부분합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 출력하면 된다. 문제 설명 자체는 간단하지만, 과정이 살짝 복잡해 보인다. 이번 문제에서 사용되는 알고리즘은 투포인터이다. 투포인터 알고리즘이란, 두개의 포인터를 두고 그 포인터들을 이동 시키면서 답을 구해나가는 과정이다. 밑에 그림을 보면서 이해해 보도록 하자. 일단, 예제에서 주어진 것과 같이 N = 10 S = 15 수열 : 5 1 3 5 10 7 4 9 2 8 이 있을때, 처음위치(0)인 부분에 두개의 포인터를 놔둔다.(sum..

이번에는 백준 알고리즘의 2869번 문제 "달팽이는 올라가고 싶다" 를 풀어보도록 하자 일단 문제는 매우 간단하다. 입력으로 낮에 올라가는 거리 A 미터, 밤에 자는 동안 미끄러지는 거리 B 미터, 총 나무막대의 길이 V 미터가 주어진다. 그리고 출력으로 나무막대를 모두 올라가는 데 며칠이 걸리는지 구하면 되는 문제이다. 이 문제를 푸는 데, 유의해야 될 점은 두 가지, 첫째는 입력의 상한값이 1,000,000,000 으로 long으로 받아야 된다는 점과 , 시간제한이다. 0.15초로 엄청 짧은 것을 알 수 있다. 정답 비율을 보니 30%대로 쉽지 않을 것만 같다. Java로 쉽게 풀 수 있을런지 도킷도킷 하다. 일단 문제를 풀어봤다. import java.io.*; import java.util.*; ..

오늘은 삼청동에 있는 블루보틀에 다녀왔다. 일본에 있을 때, 블루보틀이 힙하다고 해서 몇번 가본적은 있는데, 한국에 생겼다니 한번은 가봐줘야지 라고 생각 하고 실행에 옮기는데, 일주일이나 걸렸다.... 블루보틀은 현재 우리나라에 2개 뿐이없다. 성수점에 먼저 생기고, 두번째가 삼청동에 생겼는데, 일단 성수점은 성수역보다는 뚝섬역에 더 가까우니 가게를 찾아갈 때 헷갈릴 수도 있다ㅏ. 일단, 성수점은 사람이 엄청 몰린다는 소식을 듣고 깔끔하게 포기했다. 그리고 곧 삼청동에 생긴다고 했으니,,, 한국적인 분위기에 잘 어울리는 블루보틀의 갬성을 기대하며 먼저 인사동에서 여기저기 둘러봤다. 쌈지길도 휘적휘적 걸어보고 똥빵도 잘있나 봐주고, 그렇게 삼청동까지 천천히 둘러보면서 가보니, 블루보틀이 뽝!!!! 하늘색과..

이번에는 백준알고리즘 1946번 신입사원 문제를 풀어보도록 하자 먼저 테스트 케이스 T가 주어지고 각 테스트 케이스마다 면접을 본 지원자의 수 N이 주어진다. 그 다음줄 부터 지원자들의 서류심사와 면접시험의 결과가 등수로 나오게 되는데, 그 등수를 이용해서 뽑힐 수 있는 신입사원의 최대 인원 수를 구하는 프로그램을 작성하면 된다. 이 문제를 풀 때 주의해야 될 점은, 테스트 케이스의 개수가 20 까지이고, 지원자의 숫자가 N이므로 반복문 만으로 풀면 시간초과가 뜰 것이 자명하다. 하여, 이번 문제를 풀때에, 쉽게 key값과 value 값을 지정할 수 있는 HashMap을 이용해서 문제를 풀었다. 먼저, HashMap을 두개 사용하여, 서류심사 등수를 key 값으로하는 HashMap, 면접시험 등수를 ke..

이번에는 백준 알고리즘의 1699번 문제 "제곱수의 합을" 풀어보도록 하자 이번문제에서 사용할 알고리즘은 다이나믹 프로그래밍이다. 또한, 어느정도의 수학적으로 접근법만 알고 있으면 쉬운 문제이다. 일단, 이 문제를 처음보고 아래 첨부한 것과 같이 반복문 안에다가 입력값 N을 루트를 때려버리고 그 값을 빼가면서 반복문을 돌린 횟수로 답을 구하는 알고리즘을 작성한 후 제출한 결과 틀렸다는 걸 알았는데, import java.io.*; import java.util.*; public class sample { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamR..

이번에는 백준알고리즘의 1049번 "기타줄"문제이다. 다 같이 기타리스트 강토를 도와서 기타줄을 가장 저렴하게 살 수 있게 도와줘 보자 문제 자체는 매우 간단하다. 일단, 입력으로 기타리스트 강토씨 기타의 끊어진 기타줄 개수 N과 기타줄을 살 수 있는 브랜드 M이 주어진다. 먼저 각각의 브랜드에서는 기타줄 6개가 같이 들어있는 패키지 가격이있고, 낱개로 살 때의 가격 2가지의 가격이 있고, 끊어진 기타줄 N개를 사기위해 필요한 최소의 돈을 출력해주는 프로그램을 만들어 주면된다. 먼저 패키지 가격을 집어넣을 Int행렬인 pack과, 낱개 가격을 집어넣을 Int행령인 one을 지정하고, 오름차순으로 정렬해준다. int[] pack = new int[M]; int[] one = new int[M]; for (..