kth990303의 코딩 블로그

210509 그룹 Div.1 대회에 응시하였다. 제1회 숙대 경진대회 Open Contest와 시간대가 겹쳐 아쉽긴 했지만, 숙대 경진대회 문제는 대회 이후에도 풀 수 있으므로 div.1 연습에 14~16시동안 응시하였다. 아래 그룹은 건국대 학생들끼리 코딩 실력을 키우기 위해 만들어진 그룹입니다. 격주로 시간 내에 문제를 푸는 연습을 대회처럼 진행하고 있습니다. (건국대 학생분들 가입 환영입니다~) www.acmicpc.net/group/9928 소박하지만 그룹입니다 무슨 내용을 넣어야 좋을까요? www.acmicpc.net 내가 후기를 작성하는 날은 대회결과가 좋은 날 운좋게 맞은 문제들이 많아 복기 겸 풀이를 작성하려 한다. A. 미로에 갇힌 상근 www.acmicpc.net/problem/5069..

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

최근에 ucpc, koi, usaco 등 대회 문제 질이 좋음을 깨달았다. 그래서 대회 문제를 풀어보던 중 맨날 '농부 john', 'farmer john', '소가 길을 건너는 이유' 등의 주제로 농부 문제를 내는 문제가 있음을 알게 되고 풀어본 문제이다. 이 문제는 처음엔 굉장히 쉬운 dp, dijkstra, bfs문제인 줄 알았으나, dp, bfs로는 풀 수가 없다. 그 이유는 아래와 같다. bfs로 풀기에는 각각의 길에 가중치가 있다. dp로 풀기에는 각각의 풀숲을 몇 번째에 지났는지에 따라 중복돼서 이용될 수가 있다. 사실 맨처음에는 dp로 풀 수 있지 않을까 생각했다. bfs는 사실 처음엔 생각나지 않았다. (이건 bfs를 많이 풀어보면 느낄 것이다. 가중치가 있으면 dijkstra, 가중치가..

(실제 대회 응시자가 아님을 밝힙니다.) 요즘 Ucpc, icpc, KOI 등 대회 문제들의 질이 좋음을 깨닫고 대회 문제들을 여러개 풀어보고 있다. UCPC 2020 본선 문제들은 역시 괴수들을 위한 대회라 난이도가 상당히 어려웠다.. 원래 내가 ps 하는 목적이 코테 통과 및 취준을 위해서인데, 아직 취준하려면 멀기도 했고 일단 군생활동안은 재미삼아 ps하자는 주의이기 때문에 대회 본선 진출 목표(SCPC든 UCPC든)로 공부중이다. 일단 문제들이 되게 마음에 들기 때문에 문제들을 간략하게 포스팅해볼 생각이고, 후에 D번, L번, 그리고 실력이 된다면 G번, I번도 풀어보고 포스팅해볼 생각이다. A. 전단지 돌리기 사용 알고리즘: dfs (Gold IV) www.acmicpc.net/problem/1..

프로그래머스 월간 코드 챌린지 3번 문제를 풀지 못해 tree + dfs 연습을 좀 더 빡세게 해야겠다 싶어서 선정한 문제들 중 하나이다. 역시나...플레티넘 난이도 답게 굉장히 어려웠다. www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net KOI 2020 2차대회 초등부 3번, 중등부 2번 문제이기도 한데, 이거 보면서 진짜 요즘 초등학생, 중학생들은... 정말 대단하다는 생각도 들고, 똑똑한 친구들은 다르구나 생각이 많이 들었다. 개인적으로 친구들이나 ..

프로그래머스에서 월간 코드 챌린지 시즌2를 4월, 5월에 걸쳐 진행한다길래 접수해서 응시한 챌린지이다! 4월 4문제, 5월 4문제가 출제되고, 두 번의 대회 중 4문제 이상 맞출 경우에 경품 이벤트 응모가 가능하대서 한번 재미삼아 응시한 챌린지이다. 다른 시즌(시즌3 9월) 후기는 아래 포스팅에서~ https://kth990303.tistory.com/m/132 [210909] 프로그래머스 월간 코드 챌린지 시즌3 9월 후기 프로그래머스에선 1년에 두번 꼴로 코드 챌린지가 개최된다. 이번 챌린지는 평일에 실시되긴 하지만, 다행히 개인정비시간 때 실시되기 때문에 응시를 할 수 있었다. https://programmers.co.kr/competitio kth990303.tistory.com 5월 후기는 아래..

골드, 플레 열심히 풀면서 약점보완하던 중, 999문제에 도달했다는 것을 깨달았다. 드디어 나도.. 1000 solved가 되겠다는 생각에 급하게 학교 제출현황 중 아무거나 쉬워보이는 문제를 탐색했다. 1919번 문제가 딱 눈에 띄어서 재빠르게 풀고... 드디어! 1000 Solved를 달성하였다~ 800 Solved 게시글을 작성한 때가 1월 달이었던 것으로 기억한다. 그 때쯤엔 5월달 쯤 1000 Solved를 달성하지 않을까 했는데 다행히 4월 초에 1000문제를 달성했다. (21.04.08.) 백준 시작이 2020년 6월 30일이었으니, 다행히 1년 이내로 1,000 문제를 푼 것이다. 알고리즘이 좋아 백준을 꽤 많이 이용했었고, 그 결과 1000 solved를 달성했다. 개인적으로 나는 백준에 ..

심심해서 학교 제출현황, 그리고 울학교 랭커분들 제출현황 둘러보다가 발견한 재밌는 문제이다. 실제로 재밌어보여서 접근해보았다. 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 이었어..? ㅋㅋㅋㅋ) 이 아호코라식이라는 거... 정말 엄청 어렵..

좀 신기하고도 인상깊었던 문제를 기억 속에 오래 남아두게 하기 위해 포스팅한다. www.acmicpc.net/problem/2157 2157번: 여행 첫째 줄에 N(1 ≤ N ≤ 300), M(2 ≤ M ≤ N), K(1 ≤ K ≤ 100,000)가 주어진다. K는 개설된 항공로의 개수이다. 다음 K개의 줄에는 각 항공로에 대한 정보를 나타내는 세 정수 a, b, c(1 ≤ a, b ≤ N, 1 ≤ c ≤ 1 www.acmicpc.net 문제를 읽으면 그래프 이론이 먼저 생각나나, 같은 간선이 여러 개 있을 수 있다는 점, 그리고 가장 최대의 값을 골라야 한다는 점이 dp를 떠올리게 했다. 만약, 같은 간선이 여러개 있지 않고 하나만 있는 상태로 최대를 뽑아내는 문제라면 오히려 다익스트라를 역방향으로 돌..