지금 나는 엘리스 코드 챌린지에 참여중이다.
각 일차별 후기를 써보려고 한다.
Day1 목표량
문자열 정렬 같은 문제였다
숫자가 주어졋을때 그 숫자를 가지고 더 큰 숫자를 만드는 그런 느낌 체감상 백준 실버345 정도? 1시간 정도 걸린거 같다.
메모리나 시간도 적게 써야할거 같아서 최대한 까불면서 했는데 나중에 보니 그냥 정답만 맞으면 되는거 같다.
Day2 정리정돈을 좋아하는 k씨
그냥 범위 정해진 슬라이딩 윈도우 문제였다.
한 실버 23 정도 15분도 안 걸린거같다.
Day3 문자열 압축 해제
급 난이도 상승 백준에 같은 문제가 있다고 한다. 골드 4
https://www.acmicpc.net/problem/1662
이 문제니 풀어보면 될거 같다.
스택 문제여서 잘 열어주고 잘 닫아주고만 해주면된다. 근데 그게 어렵다. 1시간정도 걸린거 같다.
Day4 트리 위의 게임
난이도가 갑자기 미친놈이 되어버렸다. 한 5시간 걸린거 같다.
트리에서의 DP문제인데
- 현재 말이 놓여 있는 정점의 번호만큼 자신의 점수에 더한다.
- 현재 말이 놓여 있는 정점의 자식 정점이 없다면 그대로 게임을 종료한다.
자식 정점이 존재한다면 자식 정점 중 원하는 자식 정점으로 말을 옮긴다.
의 문제이다. 그래서 선공이 이길지 후공이 이길지 찾는것이다.
나는 DP와 bfs를 사용하였다.
정답지는 dfs와 dp인데 코드가 기가막히게 짧다.
난이도는 한 골1에서 플4 되지 않을까 싶다.
Day5 수열 복원
5시간 정도
이 문제는 수열 문제인데. 수열로 나오는 모든 합들을 적어두고 그걸로 만들 수 있는 수열을 구하는 문제이다.
이것도 유사문제가 있다고 한다.
https://www.acmicpc.net/problem/19073
이거랑 비슷한데 한 번 풀어봤으면 좋겠다.
나는 리스트에 맨 앞 숫자들은 무조건 필요하기 (자기자신을 만드는 작은 수) 때문에 그 값으로 만드는 다른 값들도 저장하는 식으로 했다.
정답은dfs 로 죽여버렸다.. ㄷ ㄷ
플레2~3
Day6 빨간선과 파란선
못 푼 문제이다 24점 맞았다.
연결 되지 않은 2개의 점을 골라 빨간선, 파란선으로 잇는데
번째 차례에 사용할 색깔이 주어질 때, 정점을 골라서 얻을 수 있는 빨간 간선 개수의 최솟값을 구하는 문제였다.
처음 보는 문제였기에 잘 몰랐고, N이 30 이하여
나는 union-find, PQ, 플로이드-워셜중에 중에 union-find로 접근하려고 했다.
union-find는 부모가 다를때 선이 이어지면 같은 부모를 갖게 되기 때문에 그 갯수만 세면 된다고 생각했다.
칼같이 틀리고 포기. 시간도 난 5시간 썻다.
정답이 말이 안되는게 Queue랑 tuple이랑 dp가 한 코드에 다 들어가있다 난 모른다. 아시는 분 무슨 알고리즘인지좀 알려주세요
느낌상 이번 본선 털이용 문제가 아닐까 싶다.
Day7 계기판 조작하기
진심 어지럽고 억울한 문제
한 6시간 썼다 이런 허수 문제에 시간초과를 잡지 못해서 오래걸렸다.
문제는 단순하다. N, k를 줬을때
N보다 큰 수 중에 가장 작은수를 고르는건데 그 수의 조합의 갯수가 k개이다
예를들어 3 6 이면 102345 이다 102345는 6개의 숫자조합이니깐
80점까지는 1시간 컷이였다
하지만 100점까지는 6시간 걸렸다.
3 6 같은 숫자일때 시작값을 높이고 시작하는것을 생각을 못했다.
https://www.acmicpc.net/problem/1040
여러 카페를 찾아본 결과 이 문제랑 유사하다고 한다
Day8 강림제
엘리스는 문제랑 문제와 연관된(?) 인강을 하나 준다. 근데 얼마전에 나온 dp영상 그대로 줬다.
이번 엘리스 욕을 좀 많이 먹는거 같다.
이 문제는 글이 좀 길었고, 입력값이 백준에 있는 상담원 같은 문제인줄 알았다. (우선순위 큐)
문제는 일정 인원이 기도를 해야지 엘리스 라는 신이 내려온다. 근데 일정인원이 좀 적어서 내 친구들을 불렀는데
내 친구들을 어떻게 활용하면 최대한 오랫동안 엘리스 라는 신을 지상에 머물게 구하는것이다.
변수가 있다
- 하지만 체셔의 친구들은 부끄러움이 많아서 체셔의 친구들을 제외한 신도가 명 이상이 되는 순간 다 같이 강림제에서 나가 버리고 돌아오지 않는다고 합니다.
- 또한 기도 중인 인원이 명 이상이면 체셔의 친구들은 강림제에 들어가지 않습니다.
단, 아직 들어가지 않은 체셔의 친구들은 이후 기도 인원이 명 미만이 되면 강림제에 들어갈 수 있습니다.
나는 이문제를 80점 밖에 못 맞췄다.
그 이유는 일단 인원이 부족하면 친구를 불러왔는데, 좀 참았다가 뒤에서 쓸 수 있는 경우를 생각을 못했다.
정배는 dp 인거 같은데 절대 모른다. 모르는게 맞다. 유사문제 감도 안 온다.
친구는 https://www.acmicpc.net/problem/7579
이 문제 같다고 하는데 나는 잘 모르겠다. dp면 골1 은 되지 않을까 싶다
DAY9 격자 위의 ELICE
오늘의 강의 영상은 Union-Find라는 트리 구조에서 사용되며 크루스칼 알고리즘의 기본인 알고리즘의 대한 설명이였다.
영상을 보면서 좀 긴장을 했지만.
문제를 봤을때 이것을 유니온파인드로 풀어야한다고 ??? 나는 다른 알고리즘을 사용해서 풀었고. 1시간 정도 걸렸던거 같다.
당일이라서 더이상을 말 하지 않겠고 엘리스에 추후 문제에 대한 풀이영상을 올려주는지 물었지만, 풀이영상은 없다고 했다.
그리고 내 풀이를 올려도 되냐고 물어봤을때 그건 가능하다고 했다.
아마 주말부터 한 개씩 쓸 거 같다. 하루 남았고 지금은 124등이다. 100등까지 보이는데 100등까지 이미 다 만점이기 때문에
50등안에는 들기 글렀다. 그래도 화이팅
DAY10 계단 카드 뽑기
연속된 개의 카드 주머니를 고르고, 각 카드 주머니에서 카드를 한 장씩 고른다.
고른 장의 카드들에 이 적힌 카드, 가 적힌 카드, ..., 가 적힌 카드가 모두 하나씩 순서 상관없이 포함되어 있어야 한다.
가장 큰 K의 값을 구하는 문제이다.
예를들면51 1 2 4 5 면
1245 를 선택하면 4개가 나온다.1124를 하면 1을 선택하면 다음 선택 카드는 2 인데 1인 주머니에 2가 없기 때문에 불가능
n 이 50000
k 이 50000 이다.
투포인터로 길이를 찾고 슬라이딩 윈도우로 유효성 검사를 할 생각으로 코드를 짰는데
40/100 이 나왔다..
한 4시간 했는데 실패하였고 약속이 있어서 포기하였다.
2주간 열심히 달렸고 그 결과 154/2050 등수를 달성했다. 아직 실력이 부족한걸 많이 느꼈고 대단한 사람이 많다. 다시 달려야겠다.
댓글