분류 전체보기

문제https://www.acmicpc.net/problem/1517 1517번: 버블 소트첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.www.acmicpc.net 접근법원래 세그먼트 트리 연습을 하려고 세그먼트 트리 문제를 고른거였는데 세그먼트 트리로 푸는 것보다 분할 정복으로 푸는게 훨씬 쉽다.. 세그먼트 트리는 다른 문제로 연습을 하는 것이 좋은 것 같다. 따라서 이번 글에서는 합병 정렬(분할 정복의 대표적인 예)을 사용해 푸는 것을 설명해보겠다. 과정{9, 1, 7, 4} 데이터 셋이 있을 때, 합병 정렬 과정은 아래와 같다.분..

문제https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$  둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽www.acmicpc.net 접근법쉬운 구현 문제이다. 동서남북~ 에서 BFS를 사용하라는 것을 대놓고 보여준다. 문제에서 주는 작동 방식을 정말 그.대.로 구현하면 된다. 주의할 점은 방향을 다루는 것인데 문제에서 제시한 방향은 0북 1동 2남 3서 이지만 반시계 방향으로 회전하는 것은 북->서->남->동 이기 때문에 잘 처리해주어야 한다. 나 같은 경우 dir 배열을 0..

분할 정복 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 해결하는 방법 대표적인 예: Quick Sort, Merge Sort 재귀함수를 사용해 구현 분할 정복의 단점 재귀함수를 사용하기 때문에 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게된다. Merge Sort 정렬해야 할 리스트가 주어지면 해당 리스트를 최대한 작게 쪼갠 후, 인접한 원소들끼리 비교하며 정렬해 합치는 방법이다. 위 gif는 merge sort 과정에서 업데이트 되는 정렬 리스트를 보여주는 것이기 때문에 정렬 과정을 이해하기엔 어려우니 아래 그림을 통해 이해해보자. 이해가 쉽도록 리스트 원소의 개수를 8개로 하였다. 더이상 쪼갤 수 없을 때까지 쪼갠 후..

문제https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000)www.acmicpc.net https://st-lab.tistory.com/285 해당 게시물을 참고하였습니다.  [백준] 12015번 : 가장 긴 증가하는 부분 수열 2 - JAVA [자바]https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가..

문제https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net 접근법이런 문제를 최장 증가 부분 수열(LIS)라고 한다. 그냥.. 나중에 아는척 하면 간지나는 상식!ㅎ.ㅎ 문제에 있는 예시를 그대로 따라해보다 보면 어떠한 방식으로 풀어야 될지 감이 온다. A[0]부터 A[5]까지 자기 자신까지의 최장 길이를 구해보자. 일단, 모두 적어도 가장 긴 증가하는 부분 수열의 길이는 1이다..

문제https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호www.acmicpc.net문제에서 자리 배정하는 과정을 그림으로 보여주고 있으니 보고오자 접근법N이 최대 20이기 때문에 이중 for문을 써도 괜찮다. 따라서 학생마다 모든 자리를 돌아보며 비어있는 자리를 우선순위 큐에 넣었고, 마지막에 하나만 꺼내서 자리를 배정했다. 자리를 나타내는 class를 만들고, compareTo() 함수를 오버라이딩해서 문제에서 제시하는 우선순위를 그대로 나타내주었다.   시간을 조금..

문제https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱www.acmicpc.net 접근법전형적인 완전 탐색 + 백트래킹 문제의 유형이었다. 연산자의 우선 순위를 무시하고, 연산자의 개수가 N-1개로 주어진다는 점에서 출제자가 오히려 배려를 해준 것이 아닌가.. 싶었다. 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream..

문제https://www.acmicpc.net/problem/14501 14501번: 퇴사첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.www.acmicpc.net 접근법DP를 사용해 풀었다. 점화식점화식을 만드는게 어려웠다. 처음엔 dp[i] = i일까지의 누적 최대 이익 이라고 세우고 풀어봤지만 잘 풀리지 않아서 아래와 같이 고쳐서 풀었다.dp[i] = i일부터 퇴사일까지의 최대 이익즉, 구하고자 하는 것은 dp[1]인 것이다. 따라서 dp 값을 마지막부터 1까지 구해야된다.  1일에 시작한 상담은 4일에 끝나기 때문에 1일부터 퇴사일까지 얻을 수 있는 최대 이익은 P[1] + dp[4]이다. 이 내용을 토대로 점화식을 좀 더 자세히 세워보자.dp[i] = P[i] + dp[i + T[i]]..