일간임무
-
[일간임무] - 가장 긴 증가하는 부분 수열일간임무 2021. 10. 10. 20:06
정렬을 해서 값이 변화할 때마다 체크해선 풀 수 없습니다. { 5, 3 } 은 가장 긴 증가하는 부분 수열이 { 5 }, { 3 } 뿐인데 정렬을 하면 { 3, 5 } 가 되고 가장 긴 증가하는 부분 수열의 크기가 2가 되어 오답이 됩니다. 입력으로 받은 전체 수열을 Iterate하는 것은 같습니다. { 9, 10, 11, 1, 2, 3, 4, 5 }가 있다면 iter = 9부터 iter = 5까지 검증을 할 것입니다. Elapsed time : 12min 백준은 대체로 기본을 다지는데 유용한 것 같습니다. dp을 어디에 활용하면 좋을지 고민을 많이 한 문제인데 정답을 찾는 것 조차 dp을 활용합니다.
-
[일간임무] - 단체사진찍기일간임무 2021. 10. 10. 16:08
Permutation으로 금방 풀긴 했는데 또 시간 초과에서 걸려버렸습니다. 어차피 8명을 모두 세워야 하기 때문에 8명을 서로 다른 방법으로 세우고 나서 조건을 검사했습니다. 8!이라는 워낙 많은 케이스를 검증해야 하기 때문에 시간을 많이 잡아 먹는 것은 감안했지만 추측하기를 Satisfy함수에서 귀여운 Friends의 Index을 찾는 과정이 문제일 거라 생각했습니다. 그런데 그게 아니고 offset을 integer로 변환하는 과정이 문제였습니다. 그냥 char을 int로 cast해서 풀면 시간 초과를 해결할 수는 있었습니다. 아래의 코드 몇 줄이 시간 초과의 원인이라는 게 참 웃깁니다. figure 1a의 코드를 다음과 같이 바꾸니 성공은 합니다. 무려 6초나 걸려서 다른 사람들도 그런가 확인을 좀..
-
[일간임무] - 문자열 압축일간임무 2021. 10. 6. 19:50
사용한 기술 1. 문자열 나누기 string::substr - C++ Reference (cplusplus.com) parameter로 일반적으로 두 개를 받습니다. std::string::substr ( begin , count ) 어떤 string의 begin index부터 count개의 문자를 std::string의 형태로 반환합니다. 2. for loop을 적당히 돌려서 원하는 Index에 접근하기 3. std::stringstream integer을 string으로 만들어서 새로운 string을 만들기 위해 사용했습니다. Elapsed time : 58min 문제점 for loop을 돌 때, 현재 검증하는 값을 iter로 두고 다음 index의 값과 비교하고 나서 새로운 string new_st..