https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 핵심 이 문제는 DP를 사용하여 쉽게 풀 수 있다. 테이블 정의 - DP [i] = 카드가 i개일 때 지불해야 하는 최대 금액 점화식 찾기 카드가 1개 들어있는 카드팩을 구매하고 카드 i-1개를 구입한다. 카드가 2개 들어있는 카드팩을 구매하고 카드 i-2개를 구입한다. 카드가 3개 들어있는 카드팩을 구매하고 카드 i-3개를 구입한다. 정답 코드 import java.util.Scanner; class ..
https://www.acmicpc.net/problem/16948 16948번: 데스 나이트 게임을 좋아하는 큐브러버는 체스에서 사용할 새로운 말 "데스 나이트"를 만들었다. 데스 나이트가 있는 곳이 (r, c)라면, (r-2, c-1), (r-2, c+1), (r, c-2), (r, c+2), (r+2, c-1), (r+2, c+1)로 이동할 수 있다. 크 www.acmicpc.net 핵심 bfs를 안다면 매우 쉽게 풀 수 있는 문제이다. 기존에 다루었던 네 방향에서 조금 응용된 느낌이다. 하지만 똑같은 방식으로 풀 수 있다. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main { ..
https://school.programmers.co.kr/learn/courses/30/lessons/42628 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 문자열 배열이 들어오는데, 문자열의 첫 시작이 (I 숫자) 라면 큐에 숫자를 삽입하고, (D 1)이 들어오면 제일 큰 수를 삭제한다. (D -1) 일 경우 가장 작은 수를 삭제해야 한다. 핵심 큐에서 삭제순서를 정할 수 있지만, 중간에 바꿀 수는 없다. 따라서 우선순위 큐를 2개를 선언하여 사용하면 쉽게 풀 수 있다. 정답 코드 import java.util.Collections; im..
https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 문자열이 들어오고 그 문자열을 가지고 만들 수 있는 소수의 수를 찾는 것이다. 예를 들어 "17" 이 들어오면 만들 수 있는 수는 1, 7, 17, 71이 되고 소수는 7, 17, 71이므로 3개이다. 핵심 우선 완전탐색(bfs)을 사용하여 가능한 모든 경우를 찾는다. 이후 소수를 판별해야 하는데 에라스토테네스의 체를 사용하면 된다. 에라스토테네스의 체를 예전에도 설명한 적이 있는데, ..
https://school.programmers.co.kr/learn/courses/30/lessons/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 정렬 문제이다. 입력으로 int 배열이 들어오는데, 이때 이 배열을 조합해서 가장 큰 수를 만들면 되는 간단한 문제이다. 핵심 정렬 조건을 재정의하여 우리가 원하는 조건으로 정렬시키는 것이 중요하다. 정답 코드 import java.util.Arrays; import java.util.Comparator; class Solution { public String solution(int[]..
https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 이 문제를 해석해 보면, 육지에서 갈 수 있는 끝지점과 끝지점사이의 거리를 구하는 것이다. 단 이동할 때, 가장 빠른 방법으로 간다 즉 BFS를 사용하라는 것이다. 바로 풀어보자. 정답 코드 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main{ static int[][] result; stat..
https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 핵심 백트래킹을 사용하여 풀면 시간초과가 뜨게 된다. 따라서 이 문제는 DP를 사용해야 한다. 우선 물건 1개를 넣을 때 각 무게당 최대 가치는 어떻게 구할 수 있을까? 당연하게도 위와 같다. 1~5에는 6의 무게를 넣을 수 없기 때문이다. 저 자리에 0이 들어가는 것이 맞을까? 당연하게도 6이 들어가는 게 맞다. 3의 가치를 넣을..
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 핵심 이 문제는 LCS와 dp를 이용하여 풀 수 있다. 문자열 2개를 비교해 가며, 아래 테이블을 채워나간다. 만약 첫 줄에서 해당 문자가 다르면 0 같으면 1을 넣어준다. 이후 값은 이전의 값을 이어서 갖게 된다. 이후 다시 값을 비교하면 첫 번째에 1이 들어가고 두 번째도 1이 들어갈 것이다. 이후에 A와 A가 다시 겹치게 되는데, 무작정 1을 ..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 핵심 이 문제는 DFS를 이용하면 쉽게 풀 수 있다. 또한 알파벳을 이미 방문했는지 판단해야 한다. 정답 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int..
방학 동안 알고리즘 학습에 대해 고민하던 중 좋은 기회가 있어 신청하였다. 그동안 까먹고 있었는데, 오늘 메일이 와서 블로깅을 하게 되었다. 사전 문제는 2문제를 기간내에 푸는 것이었다. 생각보다 쉽지 않아서 놀랐던 기억이 있다. 그래도 집념으로 계속 도전하여 2 솔을 하였다. 게시판을 보니까 2솔을 해도 떨어진 사람들이 있었다. 참여인원이 많아서 내부 기준을 적용했다고 한다. 다행히도 운이 좋아 참여할 수 있게 되었다. 평소 알고리즘을 좋아해서 이번 특강도 재미있게 참여할 수 있을 것 같다.
