QQ의 다이어리

문제 https://www.acmicpc.net/problem/10826 10826번: 피보나치 수 4 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 풀이 n이 최대 10000의 값을 가지므로 연산 결과가 매우 큰 수가 될 수 있다. 일반적인 DP로 피보나치 수를 계산하는 방법을 사용하되, 결과값이 매우 큰 값이 될 수 있으므로 문자열로 연산해야한다. 코드 #include #include #include #include using namespace std; string arr[10002]; vecto..

문제 : https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 LCS는 최장 공통 부분 수열로 dp로 구현할 수 있다. 관련 포스팅은 --> https://qqs-diary.tistory.com/132 코드 #include #include #include using namespace std; int dp[1001][1001]; char s1[1001],s2[1001]; int main() { scan..

문제 https://www.acmicpc.net/problem/14490 14490번: 백대열 n과 m이 :을 사이에 두고 주어진다. (1 ≤ n, m ≤ 100,000,000) www.acmicpc.net 풀이 주어진 숫자 2개를 최대한 약분하여 출력하는 문제이다. 입력이 n:m의 형태로 주어지기 때문에 문자열로 입력받아서 : 를 기준으로 자른 후, 최대공약수를 구해야 한다. sstream 헤더만 입력하면 문자열 파싱과 문자열을 int로 바꾸는 것까지 가능하다. 두 수를 최대한 약분하려면 두 수의 최대공약수로 나눠주면 된다. 최대공약수는 유클리드 호제법으로 구할 수 있다. 두 숫자가 나누어 떨어지거나, 0이 될 때까지 나머지 연산을 반복하다 보면 최대공약수를 구할 수 있다. 코드 #include #in..

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 입력된 문자열들을 중복 제거, 길이 짧은 순 정렬, 길이 같다면 사전순 정렬하는 문제이다. 처음에는 문제 대충 읽고 중복 제거 + 사전순 정렬로 생각해서 set으로 구현했는데 당연히 틀려서 삽질을 좀 했었다.. 그리고 이 문제가 시간 제한이 있어서 cin/cout을 쓰면 pass를 못한다. 그래서 scanf/printf를 사용해야 하는데, 또 문자열을 다루기 때문에 string..

문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 n개의 숫자 중에서 자신보다 작은 수의 개수를 하나씩 출력하는 문제이다. 처음에는 set을 사용하여 풀이하려고 시도했다. set에 입력받은 수를 insert 하면 정렬이 되고, 중복이 제거되므로 for문을 돌면서 작은 수들의 개수를 세려고 했지만 시간 초과가 발생했다. set이나 map은 정렬과 중복 제거가 수행되지만 인덱스로 접근할 수..

문제 https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 풀이 map 사용하는 문제에 재미 들렸다 ㅎ 먼저 map에 입력되는 차량 번호와 순서(0~n의 값을 갖는 각 차량의 번호표)를 저장한다. 추월하지 않았다면 들어와야 했을 번호를 idx에 저장한다. 배열을 생성해서 차가 터널에서 나가면 앞서 저장한 번호표에 해당하는 인덱스로 가서 1을 입력한다. (3번 번호표를 갖는 차가 나가면 arr[3]의 값을 1로 변경. 이 과정이 없으면..

문제 https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 풀이 온갖 STL을 떡칠한지라 ;; 당연히 시간 초과가 날 줄 알았으나 그렇지 않았다. map과 set에 대해서는 꽤 안다고 생각했는데 이 문제를 풀면서 배운 것이 많아서 정리한다. set을 사용하자니 입력값인 학번들이 입력 순서대로가 아니라 학번 순서로 정렬될 테니 적합하지 않았고, vector를 사용하자니 탐색이 너무 느릴 것 같았다. 그래서 unordered set을 사용하..

문제 https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV-Tj7ya3jYDFAXr&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 힙을 구현한 후, 1과 함께 어떤 숫자가 입력되면 그 수를 힙에 추가하고, 2가 입력되면 루트 노드를 출력하고 삭제한다. 풀이 처음에 10^5를 바보같이 10000로 생각해서 계속 런타임 에러가 났다..ㅋ 배열 크기는 여유있게 100005 정도로 잡아두고, 배열을 ..

문제 https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 트리는 구조체로 구현하고, 공통 조상을 찾은 후, 서브트리의 크기는 BFS로 알아낸다. 공통조상을 알아내는 것은 그냥 단순하게 정점들을 방문하고 비교해보면서 찾아냈는데 더 좋은 방법이 있을 것 같다.. 트리를 구현하는 것은 구조체의 배열을 이용해서 인덱스로 접..

비트를 잘 이용하면 연산을 빠르고, 메모리를 조금 사용하면서 수행할 수 있다. 1) N개의 비트를 1로 설정하고 싶다면, (1