kth990303의 코딩 블로그

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다. https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 의식의 흐름 및 해설 하나의 주차장에는 하나의 차만 들어갈 수 있고, 그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.) 주차장과 차끼리 연결되는 모습이 이분그래프를 ..

개인적으로 가장 어려워하면서도, 가장 흥미가 있는 주제인 LCA 문제이다. 사실 처음부터 lca 문제를 해결하려던 건 아니고, 트리 문제를 구경하던 중 lca가 떠오르는 문제를 발견하여 lca 연습 겸 풀어본 문제이다. https://www.acmicpc.net/problem/13511 13511번: 트리와 쿼리 2 N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 아래의 두 쿼리를 수행하 www.acmicpc.net 상한 시간복잡도: O(NlgN) 사용 알고리즘: LCA LCA 코드 살펴보기 LCA를 O(lgN)의 속도로 찾아내야 상한 시간복잡도를 넘기지 않는다. 루트노드의 번호가 ..

아이디어에서 배울 점이 있었던 문제이다. https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net Small을 해결하기 위한 상한 시간복잡도는 O(N^2) Large를 해결하기 위한 상한 시간복잡도는 O(NlgN)임을 알 수 있다. 의식의 흐름 및 해설 될 수 있는 모든 조합의 [최댓값과 최솟값의 차]의 합을 구하는 문제이다. 처음에 이걸 O(N^2) 이상의 알고리즘으로 해결하는 방법밖에 떠오르지 않아 꽤 고민을 했다. 그런데 생각해보니 결국 모든 조합의 [최댓값과 최솟값의 차]의 합이면 모든 경우의 최댓값 - 모든 경우의 최솟값을..

그룹연습 시간과 대회 시간이 겹쳐서 응시할 생각이 없었는데, aru0504님이 응시한다고 하셔서 1~2문제만 풀어보고 넘기려다가 중간에 문제가 안풀려 오기가 생겨 도전해본 대회이다. https://www.acmicpc.net/contest/view/644 가희와 함께 하는 1회 코딩 테스트 www.acmicpc.net +) 2회 코딩테스트도 존재하며, 후기는 여기에 존재한다. https://kth990303.tistory.com/98 [210718] 가희와 함께 하는 2회 코딩테스트 후기 푹 쉴까 아니면 코테를 응시할까 고민하다가 au0504님이 3시쯤에 코테를 응시한다길래 나도 한 번 응시해본 대회이다. https://www.acmicpc.net/contest/view/658 가희와 함께 하는 2회 코..

그래프 탐색 유형을 연습하기 위해 찾던 중 발견한 문제이다. KOI 2019 2차대회 초등부 3번 문제이다. 진짜 초등학생들 대단한 것 같다.. https://www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어 www.acmicpc.net 처음에는 위상정렬 + 유니온파인드로 접근하다가, 연결된 컴포넌트들 중 X가 포함이 안된 컴포넌트쪽과 등수비교가 불가능함을 깨닫고 dfs로 바꿔 생각하여 해결한 문제이다. 시행착오 처음에는 위..

5월에 카카오 월간 코드 챌린지를 치고 나서, 내 약점 중 하나인 스택을 보완해야겠다고 느끼고 풀어본 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2800 2800번: 괄호 제거 첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개 www.acmicpc.net 의식의 흐름 및 해설 우선 올바른 괄호쌍끼리만 제거할 수 있다는 점을 파악한다. 따라서 "문자열 폭발" 과 비슷한 원리를 이용할 수 있으며, 이 괄호쌍들을 넣을지 안넣을지 고려하는 알고리즘을 짜봐야 하는데, 괄호쌍은 적어도 1, 많아..

지난 포스팅에서 언급한 그룹연습을 진행하느라 SMUPC Open Contest에는 참가하지 못했다. kth990303.tistory.com/48 [그룹연습] 제목을 뭘로 할지 모르겠는 Div.1 후기 210509 그룹 Div.1 대회에 응시하였다. 제1회 숙대 경진대회 Open Contest와 시간대가 겹쳐 아쉽긴 했지만, 숙대 경진대회 문제는 대회 이후에도 풀 수 있으므로 div.1 연습에 14~16시동안 응시하였다. 아 kth990303.tistory.com 그래서 위 연습이 끝나고 밤에 한 번 숙명여대 SMUPC 문제들을 풀어보았다. A~E번은 어제 밤에, F~G번은 오늘 업무 끝나고 개인정비시간에 해결해보았다. www.acmicpc.net/category/detail/2539 제1회 숙명여자대학교..

2021.04.22(목) 시험기간이 거의 끝나갈 무렵, UCPC 2021 부담없이 경험삼아 나가볼 팀원 모집을 우리 백준 그룹 스터디톡에서 모집하였다. 6월 중에 참가신청을 받으므로 지금 모집하기 딱 적절한 시기라 판단했기 때문이다. 다행히 그룹톡방에서 팀원을 구할 수 있었다. 이렇게 팀원 셋이 모였다. 모두 건대 백준 그룹 스터디방 멤버들이다. 만약 여기서 안 모였으면 에브리타임에, 에타에서도 구하지 못했으면 백준 slack에서 구해볼 생각이었다. 2021.04.23(금) 팀원 모두 ucpc 경험이 처음이었으며, 백준 푼 문제수, solvedac 랭킹이 그렇게 높지 않은, 말 그대로 ucpc 부담없이 경험하기 위한 팀이므로 ucpc 난이도와 전략에 대한 간단한 브리핑이 필요하다고 판단. 오후 6시부터 ..

심심해서 학교 제출현황, 그리고 울학교 랭커분들 제출현황 둘러보다가 발견한 재밌는 문제이다. 실제로 재밌어보여서 접근해보았다. www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 사이클이라 하니까 생각나는게 두가지였다. DFS/BFS로 사이클 판별, 오일러 경로. 오일러 경로는 아래 문구 때문에 생각났다. C에 속한 임의의 선분의 한 끝점에서 출발하여 모든 선분을 한 번씩만 지나서 출발점으로 되돌아올 수 있다. 얼마 전에 오일러 경로를 공부해서 그런지 몰라..

스코페에서 아호코라식 알고리즘이 출제가 돼서 언젠가 공부를 해야겠다 해야겠다 하고 미루다가 오늘에서야 공부하고 풀게 된 문제이다. www.acmicpc.net/problem/10256 10256번: 돌연변이 인간의 DNA 구조는 A, C, G, T로 이루어진 하나의 긴 문자열로 표현할 수 있다. 이때, 몇 몇 질병은 DNA 구조를 나타낸 문자열의 어떤 연속된 부분 문자열과 관련이 있다는 것이 밝혀져 있다. 만일 DNA www.acmicpc.net 아호코라식 말고 간단한 풀이가 더 있는 듯 한데, 일단 난 9250번 문제(아호코라식의 정석 개념예제 문제)보다 어려운 듯 하여 P2에 투표하였다. (아호코라 식이 아니고 aho-corasick 이었어..? ㅋㅋㅋㅋ) 이 아호코라식이라는 거... 정말 엄청 어렵..