⭐ IUPC 출전 후기
2023년 5월 20일에 개최된 IUPC에 참가한 후기입니다.
이 대회가 저의 첫 알고리즘 대회라 경험 삼아 도전하였고, 상향으로 잡은 목표는 TOP10에 들어 경인 지역 프로그래밍 대회 출전 기회를 얻는 것이었습니다. 알고리즘 풀이를 공부한 기간은, 잘못된 방법으로 공부하며 시간을 날린 기간을 제외하고 사실상 한 달 반 남짓이고 출전 당시에 백준 골드2 레벨이었습니다.
출전하기 전에는 몰랐는데, AC를 받으면 그 개수만큼 풍선을 달아주는 게 관례라는 것을 나중에 알게 되었습니다. 굉장히 귀엽다고 생각했다는 ..
그리고 제공된 장소가 깔끔하고 넓다는 점, 간식이 다양하고 많았다는 점 등 운영진분들께서 신경을 많이 써주신 게 느껴져서 만족도가 높았던 경험이었습니다.
😎 문제 리뷰
시도하였던 문제를 리뷰해보겠습니다.
A - 모비스
문자열을 다룰 줄 아는가? 를 묻는 문제였고, 반복문을 이용해 find함수를 사용하여 간단하게 구현할 수 있었습니다.
문제 해결 과정 👉 2023.05.23 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28074 - 모비스
B - 스파이
브루트 포스 알고리즘으로 해결하였으며, 재귀호출을 사용해 장소가 달라 진척도가 그대로인 경우와 , 장소가 같아 진척도가 절반인 경우를 따로 분리해서 6의 n승 알고리즘을 구현하였습니다.
문제 해결 과정 👉 2023.05.23 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28075 - 스파이
D - 사탕팔찌
ABC, BCA, CAD 등과 같이 n개의 알파벳 중 k개를 선택해 순열로 만든 뒤, 앞 뒤 k-1개의 문자를 비교해 단어를 연결해주는 문제였습니다. 저는 위와 같은 예시에서 AB, BC, CA, AD와 같이 k-1길이의 문자열을 따로 배열에 저장하고, 길이가 K인 모든 문자열의 앞, 뒤의 K-1개의 문자열을 이 배열을 참조하여 숫자로 저장해주는 방안을 고안했습니다.
그래서 연쇄적으로 ABC부터 시작하여 다음 문자열을 결정해주는 방법이었는데, 과정이 너무 복잡하고 필요한 자료구조가 많았던 나머지 구현하지 못하였습니다.
이후에 해설을 확인해보니, 사탕 묶음을 정점으로 표현하고 두 개의 정점과 겹치는 정점을 간선으로 연결해 사탕 묶음을연결하여 푸는 그래프 문제였습니다. 역량이 부족해서 마저 풀지는 못하였습니다.
E - 중력큐
대회가 끝나기 마지막에 시도한 문제인데, 예제 입력을 모두 통과하였지만 WA를 받아 결국 풀지 못하였습니다.
끝나고 검토하며 알았는데, POP을 하는 경우에도 가림막을 꺼내게 되면 위에 있는 공들이 모두 쏟아지는 것을 고려하지 않았습니다. POP은 큐의 가장 앞에 있는 공이나 가림막을 꺼내는 동작입니다. 따라서 큐가 처음 세팅에서 시계방향 회전한 모양일 때, 앞에 있는 가림막을 꺼내면 공이 모두 쏟아지는 경우를 추가하여 해결하였습니다.
문제 해결 과정 👉 2023.05.23 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28078 - 중력 큐
F - 배 옮기기
이 문제는 알고리즘을 떠올리지 못하여, 문제를 해결하는 규칙을 찾아 재귀함수로 해결하려고 하였습니다. 인자에 vector<int> left, vector<int> right를 받고, 종료조건을 left가 모두 빈 경우로 두었습니다. 그러나 어느 배가 오갈지 일정한 규칙을 찾을 수 없어 문제를 해결하지 못하였습니다.
이후 해설을 참고하여, 다익스트라 알고리즘을 사용하여 구현하였습니다.
문제 해결 과정 👉 2023.05.25 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28079 - 배 옮기기
H - 직사각형 피자
이 문제는 자칫 브루트 포스로 풀기 쉽지만, 이분탐색으로 푸는 문제였습니다. 저도 upper_bound를 사용하며 문제 풀이를 시도하다가 이분 탐색 알고리즘을 생각해내었으나, 문제를 푸는 알고리즘에 적합하지 않다고 판단하여 구현하지 않았습니다.
각 피자 조각의 크기가 K이하여야 하므로, 모든 조각의 세로 크기들에 대해서 가로 크기 후보들 중에서 가능한 것들을 추려 개수를 세 주면 되는 문제였습니다.
문제 해결 과정 👉 2023.05.26 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28081 - 직사각형 피자
I - 기계오리 연구
제한된 배터리의 개수 내에서 전력량을 계산하는 것이 KnapSack 문제와 유사한 문제였습니다. 당시에는 이 점을 눈치채지 못하여 브루트 포스로 해결하고자 시도하였고, 시간 초과로 해결하지 못하였습니다.
문제 해결 과정 👉 2023.05.26 - [Algorithm/Baekjoon] - [BOJ/C++] 백준 28082 - 기계오리 연구
느낀 점
세상은 넓고 PS 잘 하는 사람은 많다 .. 라는 걸 다시 느낀 경험이었습니다. 더욱 겸손하게 탐구하는 자세로 공부해야겠다고 느꼈고, 느슨해진 저의 의지력에 자극을 불어넣을 수 있었습니다.
이번 대회에서 문제를 틀린 이유는 다양하지만, 크게 분류하자면 다음 세 가지가 있습니다.
첫 번째로, 알고리즘을 몰라서입니다. 문제에 사용된 다익스트라 알고리즘, 분리 집합 등의 알고리즘은 사용해본 적이 없어 만약 어떤 알고리즘인지 알았어도 문제를 풀지 못했을 겁니다. 따라서 다양한 분류를 많이 풀어보고, 체화하는 것이 중요하다!는 것을 느꼈습니다.
두 번째로, 예외 상황을 찾아내지 못하여서입니다. '중력 큐'와 같은 문제는 사소한 예외 상황을 처리하지 못하여 AC를 받지 못하였습니다. 이 점을 보완하기 위해서는 자주 문제를 풀어보고 고민하는 것 밖에 방법이 없어서 더 열심히 치밀하게 풀어보아야겠다고 느꼈습니다.
세 번째로, 떠오른 해결 방법을 의심하고 구현하지 않아서입니다. '직사각형 피자'와 같은 문제에서 이분 탐색 알고리즘이 떠올랐지만 평소에 풀었던 이분탐색 문제의 클리셰와 문제 형태가 다른 것 같아 스스로 판단하고 넘겨 짚었습니다. 이는 경험의 부족 탓이라고 생각하고, 역시 여러 문제를 많이 풀어봐야겠다고 느꼈습니다.
또, 평소에 한 문제를 풀더라도 제대로 풀어야하는 이유에 대해서 절실히 깨달을 수 있었습니다. 소설에 기승전결이 있듯이 PS에서도 문제를 이해하고 알고리즘을 설계하고, 구현하고, 오류를 점검하는 과정이 필요합니다. 이 모든 과정에서 부족한 점이 있다면 아무리 알고리즘을 잘 안다고 해도 실제 대회에서 AC를 받을 수 없다는 것을 몸소 느꼈고, 시간이 많이 걸리더라도 평소에 많이 고민해보고 처음부터 끝까지 혼자 풀어봐야겠다고 생각하였습니다.
마지막으로, 알고리즘 분류를 모른 상태에서 문제를 푸는 경험을 많이 해야겠다고 느꼈습니다. 저는 평소에 알고리즘 분류를 지정하고 그에 맞는 문제를 풀기 때문에 문제를 풀 때 알고리즘을 무엇을 선택할 지 고민을 하지 않았습니다. 이렇게 아무것도 모른 채로 문제를 맞이할 때 머리가 새하얘지고, 자주 쓰는 브루트 포스를 냅다 써버렸기 때문에 시간초과를 많이 받은 것 같습니다.
꾸준히 계속 공부해서 다음 해에 또 도전하겠습니다 👊👊
'Other > 기록' 카테고리의 다른 글
[회고] 봄날은 온다, 2023년 하반기 회고 😎 (1) | 2023.12.30 |
---|---|
[세미나] 프로젝트 관리 방법론 및 포스트 모템 (1) | 2023.07.11 |
[후기] DND 9기 백엔드 개발자 합격 후기 (0) | 2023.07.03 |
[회고] 2023년 상반기 회고 👶 그리고 하반기 목표 (8) | 2023.06.30 |
[회고] 라즈베리파이 기반 얼굴 인식 도어락 프로젝트를 마무리하며 (4) | 2021.08.28 |