CodeReview (21) 썸네일형 리스트형 BOJ 문제풀이 (W21) 원래 AC를 받은 문제만 쓰려고 했는데, 그냥 일지처럼 쭉 적어 기록이라도 남겨야겠다는 생각이 들어 앞으로는 못푼 문제도 쓰려고 합니다. 18248 제야의 종 가까운 사람일수록 더 많은 종소리를 들을 수 있다는 관찰을 직접 하지는 못했고 도움을 받았습니다. 이후 종소리 들은 횟수가 감소하는 순으로 사람을 정렬시키고 i번째 사람(가까운)은 못 들었는데 i+1번째(먼) 사람이 들은 case가 있으면 false 이렇게 구현하면 해결 할 수 있습니다. 7569 토마토 아직 AC받지 못했습니다. 토마토 상자를 입력 받을때 kappa를 줘서 그래프를 쌓고 bfs를 돌려 그래프의 최장 거리를 구해줬는데 틀렸습니다. 이미 방문했지만 더 짧은 거리로 갈 수 있다면 이를 que에 넣어줘야 합니다. 이 부분을 추가하고 AC.. BOJ 문제풀이 4(W20) dp로 상태를 정의하며 문제를 풀 때, 같은 패턴으로 항상 틀린다는 점을 발견했습니다. 서울에서 경산까지 문제의 경우(boj 14863) 1. me: k분 이하로 이동 가능하면 그때의 최대를 배열에 저장 아니라면 -INF를 리턴해주면 풀겠네! dp배열을 서울부터 i까지 j를 이용하여 이동했을때 최대로 모금한 금액이라 정의한다면 아래와 같은 식을 쉽게 얻을 수 있구나! $ \overset{\underset{\mathrm{}}{}}{dp\left ( i, j \right )=max\left ( dp\left ( i-1, j \right ), dp\left ( i-1, {j}' \right ) \right )}$ 2. 손풀이 다 하고 컴퓨터로 옮기는중... 뭔가 갖고있는 정보가 부족한걸 알아챔(이 문제의 경우.. BOJ 문제풀이 3 15975 화살표 그리기 N이 최대 10만입니다. 따라서 각각의 좌표마다 가장 가까운 좌표를 찾아주면 $O\left ( N^2 \right )$으로 TLE입니다. 주어진 좌표를 색상별로 정렬을 하고 각각의 색상 안에서 가장 가까운 좌표를 찾아줘야합니다. 저는 그냥 색을 기준으로 정렬시키고 그 이후 좌우에 있는 좌표를 보면서 더 가까운 좌표까지의 거리를 모두 더해주니 AC를 받았습니다. 색상별로 정렬이후 같은색끼리는 좌표기준으로 정렬을 한번 더 해줘야 할 것 같은데 *왜 맞았는지 모르겠습니다. *pair를 sort해주면 first다음 second가 정렬되어 한번만 해주면 됩니다! 2042 구간 합 구하기 답이 long long인 것에 유의해야합니다. 전형적인 세그 트리 문제입니다. 쿼리당 $O\left (.. BOJ 문제풀이2 1920 수찾기 주어진 배열 A를 정렬해두고 M개의 숫자가 그 안에 있으면 1 없으면 0을 출력해주면 됩니다 다만 N이 10만이라 $O\left ( N^2 \right )$이 아니라 $O\left ( NlogN \right )$안에 해결하기 위해 이분탐색을 이용해 수를 찾아줘야 합니다 if (binary_search(all(A), tmp)) cout BOJ 문제풀이 1 1182 부분수열의 합 N이 최대 20입니다 비트마스킹을 이용하여 가능한 모든 부분수열의 합을 본다 하더라도 $O\left ( N2^N \right )$입니다 20502 Gum색 게시글을 우선순위 순서대로 방문하면서 해당 게시글에 키워드가 있는지 확인하면 $O\left ( QNM \right )$해결 할 수 있습니다 1012 유기농 배추 Board[i][j]가 1이면서 아직 방문하지 않은곳을 시작으로 DFS를 돌면서 총 몇번 DFS가 호출되었는지 카운팅하면 됩니다 1463 1로 만들기 3가지 연산에 대해 dp를 돌려주면 해결 할 수 있습니다 다만 N이 100만이라 $O\left ( N \right )$안에 해결하기 위해 저는 bottom-up으로 풀었습니다 1915 가장 큰 정사각형 dp문제입니다 dp[.. BOJ 1202 보석도둑 매트로이드(matroid) 구조를 가진 그리디 문제입니다 보석은 비싼순서대로 가방은 가벼운 순서대로 정렬해두고, 가장 비싼 보석부터 담을 수 있는 가능한 작은 가방에 담아주면 해결 할 수 있습니다 다만 이때 $N$의 크기가 30만이라 $O\left ( N^2 \right )$으로는 TLE를 받습니다 따라서 N한개에 뒤에는 로그가 따라오는 정도로 문제를 풀어야합니다 저는 $O\left ( Nlog N \right )$안에 해결했습니다 하지만 이 부분에서 가방을 그냥 벡터에 넣고 lower_bound를 쓰면 TLE를 맞습니다(벡터을 이용한 구현) 가방을 multi_set에 넣고 bag.lower_bound를 사용해야 시간안에 동작합니다(set을 통한 구현) set이 random-access iterator를.. 개코 전쟁 (승리!) MLE의 원인에 대해 다시 싹 찾아봤다 원인은 3가지로 요약된다 1. 정말 할당된 자료의 크기가 너무 크다 2. 재귀의 깊이가 깊다 3. 무한 루프 나의 경우 3번이 원인으로 MLE를 맞았다 다익스트라 알고리즘에서 최단경로의 갱신은 이미 구해놓은 거리보다 작으면 갱신을 해야하는데 나의 경우 작거나 같으면 갱신을 하게 만들어 두었다 하지만 이 부분을 갱신할값 dist[nxt]) continue 이렇게 구현을 해서 두 값이 같은 경우에 대해 미묘한 차이가 발생했고 해결에 어려움이 있었다 다음부터는 표준에 맞게, 잘 구현해야겠다는 생각이 들었다 그래도 이렇게 삽질한번 해서 다양한 과정을 거치면서 이것저것 배웠는데 다음 후기글에서는 이에 대해 기록해야겠다 백준 개코전쟁(진짜 전쟁중, 치열함) 저번 글에서는 거의 뭐 하소연을 쭉 썼는데 오늘은 말하자면 내가 뭘 가지고 있고, 더 필요한건 뭔지 어떻게 챙길지 정도 생각해보는 글이다 일단 나는 catch2라는 테스팅툴이 있고, 코포에서 투어리스트 디버그 코드에 관한 블로그 글이 하나 있다 MLE 맞은 코드라 디버깅 시작부터 막막하긴 한데, 뭐 해봐야지 다른 방도가 없다 그러니 지금부터는 디버그 관련해서 여러 글을 참고하여 개코전쟁을 뜯어보려 한다 미래의 실력 좋은 나는 이렇게 만들어 가는거라 믿는다...😭 p.s. 커피도 쟁여놨다ㅋㅋ 백준 2325 개코전쟁 (진짜 전쟁중) 먼저 이 문제에 대해 AC를 못받았다 하지만 풀이를 생각해 냈고, 그게 올바른 풀이라는 것도 2주에 거쳐 확인했다(기간만 1달...) 심지어 나와 같은 풀이방법으로 구현해낸 다른 사람의 코드로 AC를 받았는데 내 코드만은 MLE가 나오는 상황이다 그러니까 정리하자면 1. 올바르게 문제를 푼 줄 알았는데 틀렸다 2. 잘 못 푼줄알고 2주가까이 검증했다 3. 그런데 다른사람의 풀이를 결국 봤는데 나랑 같았다 4. 그래서 그 분도 잘못풀었겠지 싶어 복붙해서 서밋했는데 AC가 나왔다 5. 멘붕와서 어제부터 잠못자고 유령상태다.... 왜 맞은걸까? 나는 왜 틀린걸까? 무한 반복.... 무한 반복중인 상황을 나름 정리해보자면 1. 메모리 초과를 받았으니 배열 선언부분을 확인해보자! -> 올바르네ㅎㅎ, 똑같음을 확인.. templates for cp cp를 할 때 있는 그대로의 쌩코드*를 갖다 박는 사람은 없다 나도 처음 시작 할 때는 매크로같은거 하나도 안쓰고 했는데, 결국 자료형 크기나 여러 제약때문에 이것 저것 갖다 쓰게되고, 이렇게 코드가 길어지다 보면 매크로나 온갖 잡기술을 쓸 수 밖에 없다. 솔직히 풀만한 문제인데 이런 잡기술 몰라서 레이팅 낮아지면 억한 심정 생겨서 금방금방 배우게 된다.(내가 그랬다😂) 그러니 이 글은 그냥 참고만하고, 실제 대회에 참가해서 배우는 것을 강추한다. *적당히 i/o관련 코드만 쓰는 분들도 있습니다. 수정 예정 9/1 수정본 앞으로 이 글은 항상 술마시고 수정할 예정이다 항상 술먹고 문제를 풀었는데, 술만 마시면 멀쩡한곳을 최적화 한답시고 때려부수고 있기를 매번 반복중이라 그만 하기로 했다 아무튼 본격적으로.. 이전 1 2 3 다음
