전체 글 (21) 썸네일형 리스트형 BOJ 4013 : ATM 문제 링크 : https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net SCC 응용 문제입니다. 간단해 보이지만 처리해줄게 많고 구현량이 많아 생각보다 어려웠습니다. 문제를 간략하게 정리하면, 그래프가 주어지며 각 정점은 현금을 가지고 있습니다. 이때, 시작 정점과 도착가능한 정점이 주어질 때 인출할 수 있는 현금의 최댓값을 출력해야 합니다. 현금의 액수는 0이상의 정수이기 때문에 하나의 SCC에서는 모든 정점의 현금을 인출하는 것이 이득.. 국제정보올림피아드 여름학교 후기 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을 해주는.. 이전 1 2 3 다음