솧로그

스택 스택은 가장 나중에 들어간 원소가 가장 먼저 나오는 구조이다. (LIFO) 사용 사례 스택 메모리 예를 들어 StackOverFlowError는 스택 메모리 공간을 다 썼을 때 발생하는 에러로, 주로 재귀 함수에서 탈출하지 못하면 발생한다. 자바에서의 스택 구현 자바는 Stack 클래스를 제공한다. Stack 클래스 외에도 LinkedList와 ArrayList를 통해 구현할 수 있다. 데이터 조회: Top에 있는 원소를 조회할 때는 O(1)의 시간 복잡도를 갖는다. 하지만 Top이 아닌 원소를 조회할 때는 해당 데이터를 찾을 때까지 수행해야 하므로 O(N)의 시간 복잡도를 갖는다. 데이터 삽입: LinkedList를 통한 구현에서는, 단순히 새로운 원소가 Top에 있는 원소를 가리키도록 참조를 변..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 그리디 문제로, 어떻게 하면 제일 큰 결과 값을 구할 수 있을지 아이디어만 잘 생각하면 된다. 음수의 경우 음수끼리 묶어서 곱해주어야 양수가 되어 결과 값이 커진다. 그리고 이때 절댓값이 큰 음수끼리 우선적으로 묶어주어야 결과가 더 크다. 따라서 음수를 minus 리스트에 모아서 minus 리스트를 오름차순하고 순차적으로 묶어준다. 만약 두개의 음수를 묶고 묶이지 않은 음수가 1개 남는다면, 이..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 처음에는 입력 값을 배열에 넣은 뒤 배열의 앞에서부터 순차적으로 순회하니 조금 복잡해졌다. 그런데 배열의 뒤에서부터 순회하면 훨씬 깔끔하다. 배열의 뒤에서부터 순회해서 max와 arr[j]를 비교한다. max = arr[j]인 경우, answer에 max-arr[j] 값을 더해준다. (arr[j]를 max 값에 팔..

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 우선 날짜를 다루는 방법은 3월 1일은 301, 11월 30일은 1130로 표현하면 된다. 처음에는 어떤 달은 30일까지 있고, 어떤 달은 31일, 28일까지 있으므로 앞서 언급한 방식으로 처리하면 안되는 게 아닌가? 생각했는데, 어차피 입력으로 주어진 날짜들로 합 계산을 하는 게 아니라 그저 대소 비교만 하기 때문에 상관없다. 주의할 점은 다음과 같다. 이전 꽃이 지는 날짜를..

ArrayList와 LinkedList 둘 다 자바에서 제공하는 List 인터페이스의 구현체이다. ArrayList 내부적으로 배열을 사용하며 메모리 상에 연속적으로 위치한다. 배열(Array)과의 차이점은 다음과 같다. 자바를 기준으로, 기본 타입만 저장할 수 있는 Array와 달리 ArrayLists는 Object도 저장할 수 있다. ArrayList에 add를 통해 기본 타입의 데이터를 추가하면 오토 박싱이 사용된다. Array는 초기 사이즈가 고정되어 있고 변경이 불가하다. 반면 ArrayList는 이 또한 배열이기 때문에 초기 사이즈가 변경 불가한 것은 Array와 같지만, 사이즈가 가득 차면 내부적으로 새로운 메모리 공간을 할당받아(기존 용량의 1.5배) 새로운 배열로 데이터를 옮긴다. 배열의..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 이번 문제는 그리디 문제로, 회의 종료 시간이 빠른 순서대로 정렬한 뒤 차례대로 회의를 진행하면 된다. 그런데 주의할 점은, 만약 회의 종료 시간이 같다면 회의 시작 시간이 빠른 순으로 정렬해야 한다. 예를 들어, 다음과 같이 회의가 있다고 가정하자. 1 ~ 3 4 ~ 8 8 ~ 8 만약 회의 시작 시간이 빠른 순으로 정렬하는 것을 고려하지 않고 다음 순서로 진행한다면, 1 ~ 3 8 ~ 8 4 ~ 8 8 ~ 8 회의를 진행한 후 preMeetingEndTime 변수의 값은 8이 되어 4 ~8 회의를 진행할 수 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 유형을 모르고 이 문제를 접했다면 그냥 완전탐색으로 풀었을 거 같다. 그러나 dp를 공부하다가 접한 문제이기 때문에 dp로 풀기 위한 방법을 고민했다. 그런데 아무리 생각해도 점화식이 생각나지 않았다.. 결국 다른 사람의 풀이를 살짝 참고했다. 포인트는 dp 배열을 뒤에서부터 채워주는 것이다! 앞에서부터 채우는 경우만 생각해서 적당한 풀이가 생각나지 않았는데, 뒤에서부터 채운다고 생각하니 금방 점화식을 생각할 수 있었다. (특정 날짜에 일을 시작하면, 그 일이 끝나는 날짜까지는 다른 일을 하지 못한다. 즉, 일이 끝나는 날짜가 중요하..

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가하는 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가하는 www.acmicpc.net 중복되는 연산(합)이 있기 때문에 dp를 떠올릴 수 있다. dp를 하는 과정에서 메모이제이션하는 배열을 dp 배열이라 하고, 사용자에게 입력받은 값을 input 배열이라고 한다면, input[i]가 input[i - 1]보다 작다면, 인덱스 i보다 작은 인덱스를 내림차순으로 접근하며 input[i]보다 작은 input[j]의 인덱스 j를..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net n을 1로 만드는 가장 적은 연산 횟수를 구해서 출력하고, 이때 연산 과정까지 출력해야 한다. dp[i]: i를 1로 만드는 최소한의 연산 갯수 record[i]: i를 1로 만드는 최소한의 연산 갯수의 과정에서, i가 되기 이전의 값 주의할 점은 dp[i]로 오는 경우가 여러개가 있을 수 있는데 (ex, dp[4] : 1 -> 2 -> 4, 1 -> 2 -> 3 -> 4), 기존 dp[i]의 값보다 새로운 dp[i]의 값이 작을 때만 갱신해주어야 한다. import java.io.BufferedRea..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 잘못 생각하면 그리디 알고리즘을 떠올릴 수 있다. 1번째 집부터 접근하여 3가지 색 중 가장 비용이 적은 색으로 칠하고, 2번째 집에 접근하여 1번째 집이 사용한 색을 제외하고 비용이 적은 색으로 칠하는 방식이다. 그러나 이는 잘못된 방법이다. 반례는 다음과 같다. 각 집이 빨간색, 초록색, 파란색으로 집을 칠하는 비용이 아래와 같다. 1번 집 1 100 103 2번 집 1 ..