컴공과컴맹효묘의블로그

https://www.acmicpc.net/problem/11066 이 문제를 봤을 때 Priorty Queue로 풀 수 있을 줄 알았다. 하지만 제약 조건에서 "연속이 되도록 파일을 합쳐나가고, ..."라는 인접 제약조건이 있기 때문에 인접 조건을 무시하는 Priorty Queue로 풀 수 없었다. DP문제라는 사실을 알아도 풀지 못해 정답을 찾아봐도 처음엔 이해하기 어려웠다... 풀이DP[i][j]를 파일 i번부터 j번까지 합쳤을때 최소비용 이라고 정의하자. 이러면 DP[1][N]이 정답이다.그리고 SUM[i][j]는 파일 i번부터 j번까지 파일을 합친 크기라 정의하자. 그러면 다음과 같은 수식을 구할 수 있다.DP[i][j] = min(DP[i][m] + DP[m+1][j] + SUM[i][m] +..

2025년 2월 B형 역량테스트 시험을 보라고 연락이 왔다. 원래 A형을 취득한 사람만 볼 수 있었는데, 나는 A형은 없었지만 SSAFY 입과 코딩 테스트에서 좋은 결과가 있으면 바로 B형 응시가 가능하다고 했던 것 같다. 입과 테스트를 잘 봤나보다. 당시에 나는 허리디스크 통증이 너무 심해져서 앉기는 커녕 걷기도 힘들어했다. 하지만 B형 시험이 얼마 남지 않았고, SSAFY를 그만두더라도 이 시험은 보고 나오고 싶었다. 그래서 25년 1차 테스트를 신청했고, 평소에 알고리즘 풀이에 익숙한 언어는 cpp로 응시했다. 시험을 본지 5일 뒤인 목요일에 합격 연락이 왔다.개인적으로 B형 테스트는 꼭 통과하고 싶어서 2주동안 열심히 준비했는데, 다행이 합격통보를 받았다. 합격 통보 메일 1시간 뒤, 합격 수기를..

https://www.acmicpc.net/problem/1725 입력이 10만이라, O(N^2)은 시간 내 풀이가 불가능합니다. "이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야한다." 에서 아래쪽 밑변은 히스토그램의 아랫변과 겹치게 그리는 것이 항상 최대이고, 위쪽 밑변은 직사각형이 포함하는 막대들의 높이 중 최소인 막대의 윗변과 겹쳐야합니다. O(NlogN)가 걸리는 분할정복으로 풀어봤습니다.하나의 히스토그램을 절반으로 잘라서 왼쪽의 최대와 오른쪽의 최대, 그리고 중간을 포함하는 큰 히스토그램의 최대를 구하여 비교합니다.중간을 포함하는 큰 히스토그램은 투 포인터로 O(N)이 걸립니다. left와 right를 각각 mid, mid+1로 초기화 하고 left-1, right+1의 높이..

https://www.acmicpc.net/problem/1241 첫 아이디어는 각 학생들의 머리위 숫자에 배수를 한 지점에 1씩 더하는 아이디어다.2 1 2 3 4를 예를 들면, 2는 2, 4에 1을 더하고 1은 1, 2, 3, 4, 3은 3, 4는 4 이렇게 하면 결과는 다음과 같다. arr[1] = 1, arr[2] = 3, arr[3] = 1, arr[4] = 3 결론부터 말하지만 이 코드는 시간초과가 난다.#include #include #include #include #include #include #include #include #define INF 987654321#define lld long long#define MAX_N 1000001using namespace std;int arr[M..

https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 순서는 상관 없고 두 수를 골라서 서로 차이가 M상의 최소값을 구하면 되니까 일단 서로 인접한 차이를 배열에 저장해두고, 어떻게든 하면 답을 구할 수 있을것이라고 생각했다. 하지만 이 생각은 아주 틀렸다. 그냥 단순히 두 개의 포인터 left와 right를 이용하면 답을 쉽게 구할 수 있었다. 입력받은 배열을 정렬하고 두 포인터의 값의 차이를 이용해서 right와 left를 적..

https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 쉬운 BFS문제이다. 그러므로 여기서는 내가 이 문제를 풀면서 공부한 내용을 적어볼까 한다. #include #include #include using namespace std; int N, K; queue q; bool visited[100001]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie..

https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net . 준석이는 주어진 시간 안에 최대한의 점수를 주는 과목들을 공부해야한다. 각 과목은 cost와 그에대한 가치 value가 있다. 주어진 cost 안에 과목들의 가치의 총 합이 최대가 되게하는 과목집합을 구해야한다. 이 문제를 어떻게 풀어야할까? 쉬운 방법으로는 모든 경우의 수를 구할 수 있다. 하지만 단순 계산해보아도 경우의 수가 2^100이나 된다...

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 방법 첫 번째: linked list로 구현. 두 번째: stack로 구현 세 번째: list로 구현 효율성은 stack > list > linked list 순으로 좋다. 1. stack의 풀이는 두 개의 stack을 만들어서 커서 기준으로 좌측은 s1, 우측은 s2로 저장한다. 2. list는 풀이가 조금 어렵다. dat, pre, nxt라는 배열을 만들고 nxt에 따라 값을 출력한다. d..

dp 문제를 풀 때는 항상 메모제이션이 적용될 수 있는지 생각해보자. dp와 메모제이션은 말로 풀어서 설명해보면 쉽게 구현할 수 있다. 예를 들어 아래 문제 배낭의 메모제이션은 가방에 index를 넣을 수 있는 차례고 (index는 순차적으로 연산됨. 중복될 수 없음.) weight만큼 들어갈 수 있을 때 최대 가치는? 라는 뜻으로 이용하면 된다. 그리고 메모제이션은 초기값이 아니면 항상 같은 값을 반환하는 함수처럼 작동한다. https://www.acmicpc.net/problem/12865 // 다른 사람이 푼 깔끔한 코드 #include #include using namespace std; int N = 0, K = 0; int V[101] = {0,}; int W[101] = {0,}; int d..

문제 및 참고 사이트 https://www.acmicpc.net/problem/1019 https://mygumi.tistory.com/180 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019 풀이 처음 봤을 때 이 문제를 어떻게 풀어야할지 brute force 이외에는 전혀 생각나지 않았다. 이 문제를 쉽게 풀 수 있는 핵심은 문제를 작은 단위로 나누는 것이다. 핵심 아이디어는 각 자릿수를 따로 계산하자라는 것이다. 즉, 1의 자릿수, 10의 자릿수... 를 따로 따로 세서 합치는 아이디어가 이 문제를 최적화 할 수 있는 핵심이다. 정확한 문제 풀이 이해는 백준님의 자료를 참고하자. 코드 #include #include using names..