https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이 문제는 그리디 카테고리에 있는 문제이다. 핵심 이 문제의 핵심은 어떻게 배정을 해야 많은 사람이 이용할 수 있을까?이다. 끝나는 시간이 빠른 순서대로 정렬을 하고 그에 맞게 회의실에 넣어주면 된다. 코드를 보면 쉽게 이해할 수 있다. 정답 코드 import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.Scanner; public class Main { public static void main(..
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AX8BB5d6T7gDFARO&categoryId=AX8BB5d6T7gDFARO&categoryType=CODE&problemTitle=%EC%82%AC%ED%83%95&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 나연이는 A개의 사탕을, 다현이는 B개의 사탕을 갖고 있다. 두 사람은 아래와 같은 작업을 정확히 K번 반복하려고 한다..
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://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/42746 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이 문제는 정렬 문제이다. 입력으로 int 배열이 들어오는데, 이때 이 배열을 조합해서 가장 큰 수를 만들면 되는 간단한 문제이다. 핵심 정렬 조건을 재정의하여 우리가 원하는 조건으로 정렬시키는 것이 중요하다. 정답 코드 import java.util.Arrays; import java.util.Comparator; class Solution { public String solution(int[]..
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://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 해당 문제는 DFS를 활용하여 풀 수 있었다. 처음에는 HashMap을 사용하여 풀려고 하였다. HashMap 의 맵을 만들고, 키 값에 시작점을 넣고 value값은 도착점을 넣으려고 하였다. (키값이 중복이 있을 수 있기 때문에 value의 값을 List 으로 하려 함) 하지만 이러한 풀이는 value의 순서에 따라 전부 방문하지 못하는 경우가 생기기도 하였다. 따라서 전부다 탐색을 시도해야 한..
그래프를 활용하여 최단 경로를 구할 수는 없을까? 최단경로 알고리즘은 크게 3가지가 존재한다. 이번 시간에는 다익스트라만 다루도록 하겠다. 다익스트라란? 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘이다. 정점 사이에는 가중치가 존재한다. 최단경로의 특징 정점 x까지 최단거리로 가기 위해서는 그 직전까지도 최단거리로 가야 한다. 위의 그림을 보면 1 - 6 - 2 - 3 - 8 - 7 순으로 이동한다. 최단경로의 특징을 이용하면 1~8까지 이동할 때에도 최단 경로로 이동한다. 그래서 최단경로 트리를 어떻게 만들 것인가? T(i) = i까지 도달하는 최단거리 -> 파란색 숫자 순서를 그림을 이용하여 천천히 설명하겠다. 보라 색원은 이미 탐색을 완료했다는 의미이다...
스택과 큐는 선형 자료구조이다. (Linear) 스택 스택은 말 그대로 쌓다는 의미를 가지고 있다. 스택은 Last In First Out이다. 즉 마지막에 들어간 값이 제일 처음 나온다. 1,2,3,4를 순서대로 넣는다고 생각해보자. 위와 같이 1,2,3,4 순서대로 담기게 된다. 뺄 때는 위에서부터 한 개씩 빼게 된다. 스택을 구현할 때 우리가 생각할 부분은 스택 오버플로우와 스택 언더플로우이다. 오버플로우는 스택이 가득 찼는데, 우리가 원소를 더 넣으려 할 때 발생한다. 언더플로우는 스택이 비었을 때, 우리가 원소를 더 빼려고 할 때 발생한다. 스택 구현 구현하기에 앞서 우리가 어떤 기능을 구현할지 생각해보자. S를 스택이라 하자 S.create(x) : S의 크기를 x로 지정한다. S.push(x..
재귀 함수 문제입니다. 핵심 최댓값과 최솟값을 출력해야 하는데, 여러 가지 방법이 있겠지만 List를 사용하면 쉽게 출력할 수 있다. 정답 코드 import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { static int n; static char[] arr; static boolean[] check; static int[] result; static List list; public static void main(String[] args) { Scanner sc= new Scanner(System.in); n =sc.nextInt(); arr = new char[n]; for (int i=..
