ICPC (8) 썸네일형 리스트형 2020 icpc 후기 대학생활 중 나는 운이 좋았다고 생각이 들때가 많았는데 그 중 하나였던 icpc 서울지역 본선 진출기! icpc는 1학년때 한 번 나가보고 그 후에는 학교 시험날짜와 겹쳐서 휴학하느라 나가지 못하다가 3년이 지나고 다시 나가보게 되었다 팀은 예전부터 알던 18학번 후배 오빠와 오빠가 데려온 19학번 동생과 나가게 되었다 다들 학점도 챙겨야하고 대회 준비를 진지하게 해본적이 없어 가벼운 마음으로 시작했다 일주일에 한번정도 모여 스터디를 하고 스터디 전에 icpc 기출문제를 풀어왔다 애초에 백준 티어 플래티넘 정도는 잘 못풀어서 골드까지만 정확히 빨리 푸는것을 목표로했다 학년은 내가 젤 높았는데 제일 못풀어서 팀원들한테 좀 미안했다ㅠㅠ 예선과 본선 모두 스터디카페 스터디룸에서 진행을 했는데 인쇄가 오래걸려서.. [ICPC] Cosmetic Survey 백준 16358번으로 풀어본 Icpc 예선 문제 문제가 너무 길어서 읽기 싫었지만 문제 해석만 꼼꼼히 하면 의외로 쉬운 문제 input 크기가 작아서 3중 for문 까지 가능ㅎㅎ 문제가 복잡하니 조건을 정리해보자면 - 각 평가자들은 양의 정수로 rank를 주고 수가 적을수록 선호도가 높은 것이다 - rank는 유일하거나 연속하지 않다 - rank를 매기지 않았다면 선호도 우선순위에서 제외된다 각 사용자별 선호도를 입력 받은 후 d(X,Y)라는 notation에 맞추어 d 배열을 만들었다 이 배열은 X보다 Y를 확실히 선호하는 사람의 수이다 input 배열을 돌면서 각 사용자의 확실한 선호도가 존재하는 경우 d배열의 적절한 index를 증가시켜주었다 그다음 플로이드 와샬 알고리즘과 비슷하게 경유지를 정해서.. [ICPC] Rectilinear Regions 백준 14957번으로 풀어본 icpc 문제 u계단이 위에 있을 때 계단 사이의 공간 크기를 전부 구하는 문제였다 뭔가,,,이런 상황을 푸는 알고리즘이 있을 것 같은데 이론 공부가 부족해서 그냥 대충 해봐야지 하고 시작했다 생각은 되게 금방했는데 index 다루는데 실수가 많아서 오래 걸렸던 문제 바로 코딩 들어가지 말고 앞으로는 노트에 인덱스 정리하고 코딩 시작해야겠다ㅠㅠ 이런 순서로 움직이면서 rectilinear region의 개수와 넓이를 세었다 이 때 시작점과 끝점 처리하는곳에서 실수가 있었는데 시작점과 끝점은 음의 무한대, 양의 무한대로 생각하면 된다 그래서 두 계단이 교차 되고 나서야 왼쪽,오른쪽이 닫혀서 넓이로 셀 수 있다 계단의 시작점 말고 rectliner region이 만들어질 수 있는.. [ICPC] Philosopher’s Walk 백준 14956번을 통해 풀어본 icpc 예선 문제! input크기만 봐도 절대 다 채우는걸로는 안되겠다 싶었다 $ 2^{15}*2^{15} =2^{30} $ 까지 채워야하는 것에 그 전것도 저장해야하고.. 암튼 재귀로 나누어서 풀어보기로 했다 어떻게 풀기는 했지만 너무 노가다로 풀어서 시간도 꽤 많이 들었고 아쉽다 처음에 사분면으로 나누는 것은 쉽게 재귀로 구현했다 m 값을 그대로 쓰면 나머지 0일때 처리해주기가 까다로워서 -1을 해주고 시작했다 그렇게 사분면을 나누고 나눈 사분면에 따라 중심값을 이동시켜 주면서 좌표를 찾아내었다 처음에는 주어진 n값의 절반인 (n/2,n/2)가 중점이 되고 그 다음부터는 사분면에 따라 중점 결정! 여기서부터 노가다가 시작됐다ㅋㅋㅋ 이렇게 사분면 값을 0~3으로 나타내.. [ICPC] Parentheses 백준 16362번으로 풀어본 icpc 예선 문제 예전에 인턴 프로젝트 할 때 코드 tokenizer 만들면서 lex,yacc 쓰기 전에 아무것도 모르고 손수 코드를 작성한 적이 있었는데 그 생각하면서 코드 그냥 노가다로 작성해보았다 분명 재귀로 예쁘게 짤 수 있을 것 같은데 막상 짜려니까 코드가 잘 안나왔다ㅠㅠ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 7.. [ICPC] Working Plan 백준 16368번으로 풀어본 icpc 문제 해결해야 할 일과 일들을 할 사람들이 존재하는 상황에서 일을 끝내기 위해 며칠에 몇시간의 일을 해야하는 지와 각 사람들이 총 몇시간 일할수 있는지가 주어진다 또한 사람들은 한번에 며칠을 연속으로 일해야하고 일한 후에는 며칠을 쉬어주어야한다 이 때 가능한 방법이 있으면 1과 어떻게 사람을 배치해야 하는지 없다면 -1을 출력해야한다 가능한 방법이 있는 경우 원래 일보다 추가로 일해도 되는지가 문제 해석 중 헷갈렸지만 고려하지 않아도 정답인정이 되었다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44.. [ICPC] What’s Mine is Mine 백준 17979번으로 풀어본 icpc 지역 예선 문제 마지막 번호였던 L번 역시 문제 순서랑 난이도는 다르다 이 문제는 여러 종류의 광석이 있고 그 광석들을 채굴할 때 가장 돈을 많이 벌 수 있는 경우를 찾는 문제이다 이 때 광석을 캐서 벌 수 있는 돈은 광석이 나오는 (end time - start time) * price이다 DP로 풀면 될 것 같아서 먼저 DP 식을 세워보았다 DP[i] = i시간까지 채굴해서 얻을 수 있는 최대 금액 그리고 여기에 이전 값을 어떻게 활용할지에 대해 생각해보았다 현재 시간이 특정 광물의 end time일 때 그 광물의 start time의 DP값에서 이 광물을 더 한 것이 DP[i-1]보다 큰 지 확인해보았다 이 부분에서 실수를 해서 처음 풀이가 틀렸는데 특정 시간에.. [ICPC] Fire on Field 백준 17968번으로 풀어본 ICPC 지역 예선 문제 Let A[0] = 1, A[1] = 1. For a positive integer i ≥ 2, A[i] is the smallest positive integer under the condition that no three terms A[i − 2k], A[i − k], and A[i] form an arithmetic progression for any integer k > 0 such that i − 2k ≥ 0, that is, A[i] − A[i − k] ≠ A[i − k] − A[i − 2k]. 이러한 조건을 만족하는 배열에서 n번째 값을 찾는 문제이다 다 찾으면 이런식으로 분포가 된다고 한다 n의 범위가 1000까지밖에 안되길래 웬만한 풀.. 이전 1 다음
