18.06.24 2018 SCPC(삼성프로그래밍대회) 1차 에선 후기

정신차리고 이제야 쓴다아...

어제 아침 9시부터 오후 9시까지 1차 예선이 진행되었는데 

나 자신이 24시간 코딩을 할것이라는것은 역시 큰 착각이였다 ...ㅎ.ㅎㅎㅎㅎㅎ

결과부터 말하자면 1 2 3번 세개 풀었고 4번 5번은 부분점수도 못받았다 ㅠ 

시도 횟수가 진짜 처참...

문제풀면서 느낀점 및 앞으로 공부할 방향 정리하면

우선 시도횟수 관련해서는 좀 더 신중하게 제출을 해야겠다. 워낙 백준에서 문제풀때 생각없이 제출 제출 제출 이러던 습관이 대회에서까지....

그냥 안풀린다고 화난다고 한번 더 넣어보고 ㅋㅋㅋㅋㅋ endl을 '\n'으로 바꿔서 넣어보고...뻘짓이란 뻘짓은 다했다.

그리고 시간복잡도 생각하는 습관을 조금 더 들여야겠다. 시간리밋이 나서 코드를 고쳤을 때 고친 코드가 전의 코드에비해 시간복잡도로서 얼마나 좋은지 이런거 판단하는 습관이 필요하다. 

그리고 1 2 3 번처럼 난이도 중? 중상..? 뭐라하지 암튼 평범한..? 문제는 그냥저냥 푸는데 

4 5 번처럼 난이도가 상으로 뛰어버리면 그냥 손도못댄다. 아직 엄청 부족한것 같다. 

끝나고 풀이 올라온거 읽어보니까 5번은 이진탐색 써서 푸는거라고 하던데 그부분 공부를 안해봐서 역시 아예 풀이법이 생각조차 안났던 것 같다. 

문제 수준 관련해서 얘기를 해보자면, 우선 처음 일어나서 풀때는 난이도에 놀랐다. 생각보다 어려워서..

핑계아닌 핑계를 대자면 금요일에 드디어 종강을했고, 종강하자마자 할머니댁에 다녀와서 어어어ㅓㅓㅁ청 피곤한 상태로 토요일 9시에 꾸역꾸역 일어나서 세수도 안하고 1번문제푸터 풀기시작했는데, 그래서인지 엄청 당황하고 아침부터 기운이 안났다 ㅠㅋㅋㅋ

1번은 버스타기

여러 버스에 사람을 집어 넣을 때 각 사람이 가지고 있는 점수의 차가 일정 숫자(K) 이상이여야 하는 문제다.

내가 삽질한 순서는

1. K 로 나눈 나머지대로 버스에 집어넣으면 되네! 역시 개쉽군! -> fail

2. 아 1번에서 set을 clear 안했구나! -> fail

3. 아몰랑 1번인데 걍 완전탐색돌려도 되겠지뭐 -> 약 O(N^2)로 time limit

4. std::ios::syncn_with_studio(Flale)이거 안써서그럴거야! -> time limit

-------------여기까지 풀고 다른문제 풀다가 저녁 때 다시 도전했는데 도전하자마자 내가얼마나 뻘짓을 하고있었는지 꺠닫...---------

5. 우선 입력받은 점수를 정렬하고, 작은 순서대로 버스에 집어 넣고 각 버스에 타고있는 사람의 점수중 최댓값만 저장해서 그거랑 다음 입력할 사람의 점수만 비교하자 -> time limit

6. 아 생각해보니까 최댓값을 모두 비교할 필요 없고 최댓값들 중에서도 최솟값만 가지고있으면 되겟구나! pq 사용하자 -> 드으으어이디이어어어 성공

1번 푸는사람 많던데 나만 못풀어서 엄청 시무룩...하고 던지려다가 풀었다 ㅠㅠ 

이거 풀면서 아직도 내가 엄청 초보구나...를 깨달았던 문제

2. 회문인 수의 합

내생각엔 5문제 통틀어 제일 쉬웠던 문제가 아닌가 싶다. 

3번의 횟수는 모두 같은 알고리즘에서 출력문제로 틀렸다.

첫번째는 개수만 출력하고 합에 사용된 수를 출력안해서..... 두번째는 합에 사용된 수를 내림차순안해서 ㅠㅠ

제발 꼼꼼히 풀자 좀!!!ㅠㅠ 

이건 음... 10000까지 모든 수를 회문인지 아닌지 bool형 변수로 체크 해 두고 그다음에 1개로 표현할 수 있는지 확인 -> 불가능하다면 2개로 표현할 수 있는지 확인 -> 불가능하다면 3개로 표현할 수 잇는지 확인

이렇게 풀어주면 금방 풀린다.

2개로 표현할 수 있는지 확인하는 방법만 스피디하게 써보면

n이 2개의 합으로 표현할수 있는지 탐색하려면

1부터 n까지 모든 수를 탐색하면서 i번째 수가 회문이라면 n-i도 회문인지 탐색해주면 된다.

이거랑 엄청 비슷한문제가 백준에있었던 것 같은데....꽤 최근에 풀었던 기억이난다

골드바흐의 추측이엿나? 소수의합으로 표현하는거?

암튼 그럴꺼당...

3. 우주정거장

내 또 다른 삼질의 흔적 ㅠㅠㅠㅠㅠ 진짜 이거 풀다가 화나서 키보드 샷건침

아니 처음에 내가 생각한 방법대로 풀면 내가 만든 6개~7개의 예제 모두 정답이 나오는데 자꾸 틀렸다고 하길래

뭐야 이거 테스트케이스오류아님? 이러고있었다 ㅋㅋㅋㅋ

처음부터 문제이해를 잘못해서 5번인가 기회를 날리고 

(나는 예를들어 2번 4번 을 이용해 3번을 만들꺼면 2번 4번은 지상에서 무조건 만들어서 가져가야 되는 걸로 생각했다. 알고보니 집게모양? 으로 계속 붙여나갈 수 있는 구조였다)

그림을 그리기가 매우 귀찮아서 말로설명하려니까 힘들군...

어쨌던 이건 최종 모양에서 집게모양?으로 그래프를 지워나가면 되는 구조이다. 

한 정점에 대해 그 정점이 2개의 간선을 가지고 있고 그 2개의 간선과 연결된 두 정점사이에 간선이 존재한다면 그 정점과 그 정점에 연결된 2개의 간선은 지워도 되는 것이다!

이 때 지우면서 다시 자신과 연결된 간선이 2개인 정점이 생겨나므로 게속 확인하면서 queue에 넣어서 탐색해 주어야 한다. 

이 과정에서 시간이 좀 걸려서 처음에는 77점 받았다가 queue 잘 최적화해서 짜서 겨우겨우 만접 받았따

4. 몰라...몰라 못풀어

6명풀었던데

괴물들인가....문제이해도못함

5. Lights to Stage

끝나고 풀이 읽어보니까 이진탐색? 이라고... 이진탐색 공부해야겠다 ㅠ 

L=1일경우에 부분점수 준다길래 그거라고 구현하려고 뻘짓했지만 ㅠ 2시쯤 너무졸려서 그냥 잤다....나레기

암튼 결론은 그래서 3개 풀었고...점수는 처참하지만 그래도 어느정도 만족은 한다. 앞으로 시도횟수 줄이면서 한번에 제대로된 알고리즘을 세우는 연습, 시간복잡도 계산하는 연습 해야겠다!

그리고 2차가 될지 아닐지는 모르지만...(되겠지..? ㅠㅠ) 2차 전까지 난이도 상짜리 문제들좀 열심히 풀어야겠따. 백준에서 문제수늘리려고 쉬운문제만 골라풀고있었는데..

다시 빡공!!!!