두부의 코딩일기

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 풀이 문제 설명이 매우 길어서 어렵게 느껴지지만 생각보다 쉬운 문제이다. N개의 도시와 N-1개의 도로가 있다. 그리고 도시에는 리터당 가격이 적혀있고 1리터당 1km를 갈 수 있다. 최소한의 비용으로 도시 A부터 D까지 가려면 어떻게 해야 될까? 바로 리터당 가격이 저렴한 기름을 넣는 것이다. 예제를 한 번 풀어보겠다. 첫 번째 도시에서 두 번째 도시로 가려면 5원짜리 기름을 2L..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 회의가 겹치지않도록 최대한 많은 회의를 배정하는 게 이 문제의 목표이다. 쉽게 말해서 이전 회의 종료 시간과 이후 회의 시작 시간이 겹치지 않으면 된다. 그리고 최대한 많은 회의를 하려면 종료 시간이 짧은 회의를 선택해야한다. 우선 문제를 쉽게 해결하기 위해서 종료 시간을 오름차순으로 정렬해야한다. Arrays.sort(times, new Comparator() { @Override public int compare(int[] o1, int[] o2) { // 종료 시간이 같다면 시작 시간이 빠른순으로 정렬..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 이번 문제는 잘 이해한다면 쉽게 풀 수 있다고 생각한다. 55-50+40 어떻게 하면 최솟값을 만들 수 있을까? 최솟값을 만들려면 최대한 큰 값을 빼주면 된다. 즉, 덧셈을 먼저 진행한 후에 뺄셈을 진행하면 된다. 1. 공식에서 -로 분리한다. String[] str = br.readLine().split("-"); 2. 이후에 +를 분리해서 값을 더해준다. for (int i=0; i

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 풀이 이번 문제는 그냥 수학적 사고 테스트 문제이다. 3kg과 5kg 두 가지의 설탕 봉지를 이용해서 배달하려는 무게를 정확하게 맞추어 봉지의 개수를 최소한으로 하는 게 목표이다. 처음엔 문제를 너무 어렵게 생각했었다. 간단하게 생각해서 5kg의 설탕 봉지를 많이 사용하면 그만큼 봉지의 개수를 최소한으로 할 수 있다는 걸 생각하지 못 했다. 이걸 알게 된 후에는 문제가 엄청 쉬워졌다. 그냥 배달하려는 무게가..

https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 풀이 카운팅 정렬 형식으로 문제를 해결할 수 있지만 이분 탐색으로 분류되어 있기 때문에 이분 탐색을 이용해서 풀어보려고한다. 이분 탐색은 중간 위치 값과 목표 위치 값을 비교하면서 반으로 줄여나가는 방식인데 자바에서는 메서드 하나로 귀찮은 이분 탐색 코드를 안할 수 있다. 바로 Arrays.binarySearch() 메서드인데 이분 탐색의 기본 조건과 같이 배열을 오..

알고리즘 문제를 풀다보면 이분 탐색을 이용한 문제를 많이 접할 수 있습니다. 이분 탐색이란 오름차순으로 정렬된 배열에서 반으로 쪼개면서 특정한 값을 찾아내는 알고리즘입니다. 이분 탐색 과정 목표값은 42로 설정하고 아래와 같은 배열이 있다고 가정해보겠습니다. 1. 배열의 중간 '25'을 기준으로 목표값 '42'의 크기를 비교한다. 2. 목표값 '42'가 중간값 '25'보다 크기 때문에 mid+1을 low로 변경 후 다시 중간값을 찾는다. 3. 목표값 '42'가 중간값 '59'보다 작기 때문에 mid-1을 high로 변경 후 다시 중간값을 찾는다. 4. 목표값인 '42'가 중간값이랑 일치. ※ 위와 같이 계속 중간값(mid)을 기준으로 크기를 비교해서 low값과 high값을 ±1을 시키면서 일치하게 만든다..

https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 풀이 브루트 포스 기법을 이용해서 해결하는 알고리즘 문제라고 한다. 사실 브루트 포스 기법이 뭔지 잘 모르는 상태에서 풀었다... 문제를 푸는 순서는 아래와 같다. 1. 9명의 난쟁이 키를 더한다. 2. 난쟁이 키를 오름차순으로 정렬한다. 3. 9명의 난쟁이 키를 합한 값에서 100을 뺀 후, 가짜 난쟁이 두 명을 더한 값과 비교한다. import java.io.*; import java.util.*; p..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 풀이 동적 계획법 (dp) = 다이나믹 프로그래밍으로 접근하면 되는 문제이다. dp 관련 알고리즘은 해당 문제가 제시하는 조건에 맞는 점화식만 찾으면 쉽게 해결할 수 있다. 찾기가 어려울뿐... 1. 포도주 잔을 선택하면 무조건 다 마신 후에 제자리에 놓아야 한다. 2. 인접한 포도주를 3잔 연속으로 마실 수 없다. 위 조건에 맞는 점화식을 발견하려면 최소 4번째 포도주까지 진행해봐야한다. 우선 포..

https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 풀이 Map을 이용해서 풀었더니 처음엔 출력 초과가 발생했다. 이유는 동명이인이였다. 동명이인 문제를 해결하기 위해서 참가 선수 이름을 입력해줄 때 Map에 이미 들어있는 이름이라면 value 값을 1 추가해줬다. for (int i=0; i

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 주어진 숫자들로 덧셈과 뺄셈만을 이용해서 목표값을 만드는 문제이다. 모든 경우의 수를 거쳐야하므로 깊이 우선 탐색 (dfs)가 바로 생각이 났다. dfs 함수를 생성하고 마지막 노드까지 탐색했을 때 목표값과 일치한다면 answer++를 해주는 방식으로 코드를 설계했다. 여기서 중요한 건 목표값을 도달했을 때 answer++를 해주는 것이 아닌 마지막 노드까지 탐색을 완료해야한다는 점이다. 깊..