코딩/여름학교 (12) 썸네일형 리스트형 국제정보올림피아드 여름학교 후기 10일간의 2022 국제정보올림피아드 여름학교가 끝이 났습니다. 매일 오전 9시부터 오후 10시까지 강의 듣고 코딩했고 거기다가 복습하고 업솔빙한 시간까지 생각하면 거의 하루에 15시간씩 코딩만 한 것 같네요 힘들긴 했지만 그만큼 배운점이 많아서 후기 겸 기록으로 작성해보고자 합니다. 1. 10일간 배운 내용 여름학교인 만큼 주제자체는 그렇게 어렵지 않았습니다. 부분적으로 아는 내용이 꽤 있었고 모르는 내용이더라도 교수님 설명이나 자료가 워낙 깔끔하고 요약이 잘 되어있어 이해까지는 문제가 없었습니다. 다만 뒤로 갈수록 확실히 어려워지는 것도 느낄 수 있었습니다. 특히 자료구조 수업에서 레드-블랙 트리, 234 트리는 아직까지도 무슨 내용인지 하나도 모르겠습니다 ㅋㅋ; 쉬운 주제였지만 얻어간 부분도 많았고.. (8/3) 9일차 - 분할정복과 귀납적 알고리즘설계 문제 모의고사를 제외한다면 수업으로는 마지막 날이었습니다. 총 10문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 쿼드 트리 O 예전 백준에서 같은 문제를 풀어본 적이 있습니다. 재귀적으로 왼쪽 위, 오른쪽 아래 좌표를 가지고 4조각으로 나누면서 주어진 좌표 안의 모든 점이 0 또는 1로 통일된다면 출력하고 return 해줍니다. 2. 곱셈 O 곱하는 값들의 범위가 10^18이기 때문에 단순 곱셈은 오버플로우가 발생합니다. 이를 해결해주기 위해 곱셈을 재귀적으로 더 .. (8/2) 8일차 - 자료구조(2) 문제 총 9문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 순회 O 트리를 구현하고 전위순위, 중위순위, 후위순위법에 따라 한줄에 하나씩 출력해주면 됩니다. 전위순위 : cur -> left -> right 중위순위 : left -> cur -> right 후위순위 : left -> right -> cur 2. 아는 사람 O 유니온 파인드를 이용하는 문제입니다. 서로 부모가 같다면 1, 다르다면 0을 출력하면 되고 서로 알게되었다 라는 것은 union 함수를 구현하여.. (8/1) 7일차 - 그래프 알고리즘 기초 문제 어제와 같이 문제를 풀었습니다. 총 13문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 인접 리스트 O 말그대로 vector를 이용하는 인접리스트를 구현해주고 각각을 오름차순으로 정렬하여 출력해주면 되는 기초문제입니다. 2. 너비 우선 탐색 O queue를 이용하여 그래프에서의 너비 우선 탐색을 진행하면서 이전까지 방문하지 않은 정점을 방문하게 된다면 queue에 push해주는 동시에 값을 출력해주면 너비 우선 탐색의 정점 방문 순서와 동일한 순서로 값들이 출력.. (7/31) 6일차 - IOI 출제동향(동적계획법 최적화) 문제 IOI 출제동향이라고 템플릿에 적혀있었지만 코치장님께서 LIS, LCS 등 대표적인 동적계획법의 활용과 최적화 방법에 대해 가르쳐 주셨습니다. 문제는 총 13문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 최대 부분 합 O 간단히 DP[i] = max(DP[i-1]+a[i], a[i])라는 식으로 DP식을 세워줄 수 있습니다. 2. 계단 오르기 O 가장 유명하고 기본적인 DP문제 중 하나입니다. 탑다운과 바텀업 방식 둘다 가능하지만 저는 바텀업 방식을 사용했습니.. (7/29) 4일차 - STL 문제 어제와 같이 문제를 풀었습니다. 총 8문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 순열 O vector 두 개를 만들어 현재 순열의 값들을 넣은 후 각각에 대해 prev_permutation() 과 next_permutation() 을 사용한 후 출력해주면 됩니다. 2. 바구니 O set을 사용하면 시간초과가 발생합니다. (multiset과 unordered_set, unordered_multiset을 써도 동일) 따라서 set이 아닌 map을 활용해야 하는.. (7/28) 3일차 - 자료구조(1) 문제 어제와 같이 문제를 풀었습니다. 총 7문제였습니다. https://bas.ioikorea.cc/problems/list 2022 여름학교 처음반 로그인이 안 되는 경우 브라우저를 구글 크롬으로 바꿔주세요. 불편을 드려 죄송합니다. 문제가 발생할 시 [email protected]로 연락해 주세요. bas.ioikorea.cc 1. 메모장 X 방법자체는 간단합니다. push, pop과 비슷한 명령을 수행하는 메모장을 만드는 것이고 이중연결리스트를 응용하면 됩니다. 다만 아직 오류가 나는 부분을 찾지 못해 해결중입니다. 2. 스택 O 스택을 STL을 사용하지 않고 구현하는 문제입니다. 연결리스트를 이용해도 괜찮지만 그냥 배열하나 잡아서 top값 변화시켜주면서 top값을 이동시키면서 push, pop을 해주는.. (7/28) 3일차 - 자료구조(1) 이론 흔히 알고리즘하면 배우게 되는 기초적인 자료구조들을 배웠습니다. 연결리스트(Linked List) 자기 참조 구조체 : 자신과 같은 구조체를 참조하는 포인터가 삽입되어 있음 노드의 초기화 : typedef struct node { int data; struct node *next; } Node; Node *front; front = (Node *)malloc(sizeof(Node)); front->data = 1; front->next = NULL; 연결리스트의 경우 임의의 위치에서 삽입&삭제가 효율적이며 동적할당을 통해 메모리를 낭비하지 않는다는 장점이 있음 front와 rear를 이어주는 형태의 원형 연결 리스트(Circular Linked List)도 존재함 next값만 가지고 있다면 연결리스트, .. 이전 1 2 다음