https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제만 읽으면 아주 간단한 구현 문제로 보인다. 하지만 생각보다 정답율이 약 19%밖에 되지 않아 의문을 가졌는데 풀다보면 조금은 알게 된다. 여기서 주의해야하는 함정 포인트는 크게 2가지가 있다. 1) R, D로 뒤집고 지우라는 명령을 곧이 곧대로 받아들이면 안된다. 코드만 봅면 지우거나 뒤집는 게 쉬워보이지만, 메모리 상에서는 상당히 귀찮은 일이다. 시간복잡도가 O(N)이나 소요되는 일이다. 따라서 뒤집기(R) 처리는 하나의 변수를 지정하여 현재 배..

C++로 알고리즘을 풀 때 실행 속도를 높이기 위해 아래와 같은 구문을 추가한다. ios_base::sync_with_stdio(false); cin.tie(null); 첫 번째 코드 ios_base::sync_with_stdio는 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 한다. 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 delay가 발생한다. ios_base::sync_with_stdio(false) 코드를 작성함으로써 동기화를 비활성화해준다. 이로 인해 C++(iostream)만의 독립적인 버퍼가 생성되어 C의 버퍼와 병행하여 사용할 수 없게 된다. 그러나 동기화를 하지 않기 때문에 실행속도는 빨라진다. 알고리즘 문제를 풀 때는 대부분 싱글 스레드이기 ..

최단 경로 문제 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다. 가중치가 있는 그래프(Weighted Graph)에서는 Edge의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적이다. 최단 경로 문제에는 다음과 같은 유형이 있다. 단일 출발 최단 경로: 단일 노드 𝑣에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 단일 도착 최단 경로: 모든 노드들로부터 출발하여 그래프 내의 단일 노드 𝑣로 도착하는 가장 짧은 경로를 찾는 문제. 단일 출발 최단 경로를 거꾸로 뒤집은 것과 같다. 단일 쌍 최단 경로: 주어진 꼭짓점 𝑢와 𝑣에 대해 𝑢에서 𝑣까지의 최단 경로를 찾는 문제 전체 쌍 최단 경로: 그래프 내 모든 노드 쌍들 사이의 최단 경로를 찾는 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정말 전형적인 Greedy Algorithm 문제이다. 그러면 어떤 내용을 기준으로 잡아야하는지 고민해보아야 한다. 회의가 시작한 순으로 정렬을 하면 최대 회의의 수를 구할 수 없다. 왜냐하면 회의는 일찍 시작했으나 늦게 끝나는 경우가 있기 때문이다. 따라서 회의가 끝나는 순대로 오름차순 정렬을 하고, 최대한 앞에서부터 채운다는 느낌으로 회의의 수를 세면 된다. 정렬 기준으로 회의의 종료 시간을 설정하기 위해서 회의에 대한 정보를 저장할 때 vector에 first에 종료 시간을, second에 시작 시간을 설정..

https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 네이버 기출 문제와 유사했었던 문제라서 풀어보고, 분석해보았다. 이러한 성냥개비 문제는 이전에 많이 접했어서 한 눈에 DP 문제라는 것은 파악하기 용이했다. DP 풀이의 핵심은 인덱스의 기준을 어떤 것으로 삼을 것인지가 관건이다. 이를 파악하기 위해서는 어떤 연산이 중복, 반복되는지를 파악해야 한다. 가끔 더 편하게 문제를 풀기 위해서는 인덱스로 접근되기에 적절한 기준을 찾아도 좋다.(야매팁) 덧붙여지는..

https://www.acmicpc.net/problem/1669 1669번: 멍멍이 쓰다듬기 동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다 오늘도 어김없이 그의 영원한 라이벌 멍멍이를 만나게 되었다. 원숭이는 멍멍이를 쓰다듬고 싶었다. 하지만 원숭이는 멍 www.acmicpc.net 🥈실버이지만 그렇다고 쉽지만은 않았던 문제였다. 우선 무턱대고 푸는 것이 아니라 규칙이 있나부터 살펴봐야했다. 문제에서 처음과 마지막에는 반드시 1cm만 클 수 있다고 했고, 1cm씩만 조정가능하다고 했기 때문에 n일 간 성장할 수 있는 최대 길이가 마치 정규분포를 그리듯 대칭적으로 규칙을 가지고 있다. 날짜 수 최대 성장 가능한 패턴 3 1 2 1 4 1 2 2 1 5 1 2 3 2 1 6 1 2 ..