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://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141J8KAIcCFAYD SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 위 트리는 식 (9/(6-4))*3을 이진트리로 표현한 것이고 이를 계산한 값을 출력하면 된다. 사람들은 사칙 연산을 할 때(9/(6-4))*3식과 같은 중위 표기식으로 계산을 한다. 하지만 컴퓨터를 통해 각 연산자의 우선순위대로 계산을 하려면 후위 표기식으로 변환해 계산해야 한다. 즉 (9/(64))*3 → 964-/3*으로 변환되고 이를 계산한다. 따라서 해당 문제에서는 트리를 입력받고 후위 순..
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..
https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 핵심 이 문제는 DFS로 풀면 시간초과가 나게 된다. 따라서 DP를 함께 사용한다. 이미 탐색한 부분은 다시 탐색하지 않는 방법을 이용한다. 정답 코드 import java.util.Scanner; public class Main { static int M; static int N; static int[][] map; static int[] dy = {1, 0, -1, 0}; static int[] d..
https://school.programmers.co.kr/learn/courses/30/lessons/136798 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제의 핵심은 약수의 개수를 찾는 것이다. 하지만 단순하게 시간복잡도 때문에 단순하게 약수를 찾으면 시간초과가 떠버린다. 1. 단순하게 모든 수를 나눠서 약수 구하기 List getDivisor(int N){ List divisors = new ArrayList(); for (int i = 1; i
