난이도: Lv.3유형: 이분 탐색해결 여부: 아예 못품내가 생각했던 아이디어/큰 가닥주사위는 1대1 에서 5대5설마 다해보기인가. 그럼 최대 5개라 할때 일단 주사위 분배 정하는 과정 10C5, 각 계산합할때 나오는 경우의 수 다 쓰면 6^5+6^5, 비교하는 과정 하면 (6^5)^2... 엄청크다.하지만 기댓값으로는 승률 예외 있어서 다하는게 맞는거 같은데.. 뭐지 전혀 모르겠다.오답 이유해답A가 가져갈 주사위와 B가 가져갈 주사위를 일일히 고르는 것은 맞다그리고 그 합의 경우의 수도 일일히 구하는 것이 맞다.하지만 달라지는 건 A와 B 합 간의 비교이다. 정렬 후 bisect()를 활용해 그 개수로만 승패를 판별해 빠르다. 즉 이분탐색이 마지막에 들어간다.규모에 압도당해서 마지막에만 이분탐색 쓰면 되..
Algorithm
난이도: Lv.3유형: 다익스트라해결 여부: 틀림내가 생각했던 아이디어/큰 가닥gates 중 하나 택1, -> summits -> gates 에서 나오는 최댓값의 최솟값 그러면. 편도만 구해도 된다. 간선도 방향성 없다. 간선중심으로 가장 긴 intensity 에서 하나씩 빼면서해야하나 산봉우리는 한번만 큐에 값이 작은거부터 넣고 가능한지 판단하기결국 gates에서 산봉우리로 가는 여정. DP 처럼 기록하기? 그래서 최솟값으로 갱신하는걸로. - 간선은 없다고 했으니 이게 맞는듯. 딕셔너리 쓰면 될듯 오답 이유destionation 스펠링동점자 처리 sort() 안함visited를 len(path)->n으로 바꿔줌그냥 안되는 이유가 좀 명확한계 전단계의 최솟값을 보장하지 않아서 인가? 양수라고 해도 최솟값..
난이도: Lv.3유형: 트리 탐색해결 여부: 시간 오래걸려서 해결내가 생각했던 아이디어/큰 가닥-처음에는 문제 이해가 안되었다. 이진트리 만드는 문제인가 했는데 그건 아니었다. 문제 다 읽고 처음에는 다음과 같이 결론내렸다. 이진수 변환후에 앞에 총 길이 2^n-1 꼴로 표현되도록 0을 붙인다.그리고 홀수번째오는 수들은 모두 1이어야만 한다고 생각했다. 즉 이진트리에서 리프노드 아닌건 1이어야 하니까그런데 오답 받고 나서 생각해보니 서브트리 전체가 0이면 상관없었다.그래서 위에서부터 1이라면 아래 가지노드 둘로 쪼개져 큐로 들어가고, 0이라면 큐에 새로 넣지는 않고 조건을 만족하는지만 확인한다. 불만족하다면 즉 자식중에 1이있다면 바로 불가능으로 추가한다.저 제곱 계산식 하는게 빡셌다. 현재 몇층이어서 ..
난이도: Lv.3유형: BFS해결 여부: 정답내가 생각했던 아이디어/큰 가닥가능한 이동 경우 나누자. 각각 가로인경우와 세로인 경우.. 그래서 좌표로 표현하기. 근데 이건 나중에 알고보니 상관 없었다.근데 쌩으로 좌표에다가 기록은 안됨. 차가 2칸짜리여서 경우의수가 여러가지임... 해싱을 해야할듯 -> 딕셔너리에 추가하기? (x1,y1,x2,y2) : result 회전:가로인 경우 [(i,j),(i,j+1)] -> [(i-1,j),(i,j),] or [(i,j),(i+1,j)] or [(i,j+1),(i+1,j+1)] or [(i-1,j+1),(i,j+1)]회전:세로인 경우 [(i,j),(i+1,j)] -> [(i,j),(i,j-1)] or [(i,j),(i,j+1)] or [(i+1,j-1),(i+1..
난이도: Lv.3유형: 정렬해결 여부: 틀림 내가 생각했던 아이디어/큰 가닥-둘다 작으면 무조건 후순위다. 동순위도 아님. 무조건 합이 큰 앞등수랑만 비교하면 됨. 그러니 합으로 정렬하자.문제는 완호 앞에서 과락으로 나가리 되는 애들..일단 완호 뒤에는 상관이 없음 걍 절삭하고 시작하자.그냥 process_list의 길이 +1이 완호 등수임. 근데 완호가 과락하는 경우도 고려는 해야함이제 완호 앞에서 몰락하는 경우 빼면 완호 등수 나옴.for문 2번 돌려야 하나... 근데 나가리 된건 바로 재껴서 이후 부담을 줄일 수는 있을듯연결 리스트쓰거나 이러면 복잡하니까 통과한거는 딕셔너리에 넘기고, 그 딕셔너리만 보는식으로앞에서부터 재앙이 가는게 좀더 효과적이지 않을까. 큰수가 직접 작은 수에 강림오답 이유시간초..
난이도: Lv.3유형: DFS/BFS해결 여부: 틀림내가 생각했던 아이디어/큰 가닥칸수기반이니 일단 큰것부터 그리디인접한 칸 비어있으면 안된다. = 걍 game_board에서도 table의 블럭처럼 어떤 형태 들어가는지 똑같이 처리해라. 칸수 같은 것끼리만 넣을 수 있다.그러면 조각의 분류가 먼저인거 같은데? 어떻게 조각의 분류를 나타낼 수 있지?최소크기의 모든걸 포함하는 직사각형 하나 만들고 들어가는지?아니면 좌표로 정하기? 이게 더 낫겠다. 그리고 숫자 범위에 따라 최소값으로 한번 가공하는 식으로 객체지향으로 푸는게 낫겠군.. 오답 이유일단 시간도 다 되었고, 어차피 이 속도면 실전에서는 틀렸다 생각해 문제풀이 중단하였다. 결국 큰 흐름은 알겠는데 뭔가 공간구현이 내가 약한것 같다.해답리스트 좌표 ..
난이도: Lv.3유형: DP, 문자열 처리, 누적합, sliding window해결 여부: 틀림내가 생각했던 아이디어/큰 가닥대충 어케하는지는 알았는데 하다가 코드 비효율적이고 문제 풀이 시간도 다 되어서 관두었다.아이디어 자체는 계속 시작하는 초로 비교하는 것일 것이다.오답 이유/는 float 반환해서 망가짐불필요한 문자열 초 반복최대 로그 길이상 배열 순회하면 시간복잡도 늘어남.무엇보다 가장 효율적인 시간이 시작시간이 아닐때가 존재한다. 그래서 이 방법은 아예 틀렸다. 해답-누적합을 2개 만든다. 36만개 짜리 배열 만들어서 시작시간에 +1, 종료시간에 -1 해준다,여기서 1차 누적합을 만든다. 배열 한번 순회하면서 이전값 다 더해주면 현재 시청자 수가 나온다.2차 누적합으로 한번더 같은 방식을 쓰면..
난이도: Lv.3유형: brute force해결 여부: 틀림 내가 생각했던 아이디어/큰 가닥처음에 생각을 잘못함. 각 거리별 간격 구하고 무조건 1곳의 간격 빼고 방문해야 하는줄. 근데 예시 1에서 바로 깨짐원형이니까 제일 끝부분만 처리해서 2가지 경우의 수로 나누고 접근해야 하나?어떤 점 기준으로 왼쪽이나 오른쪽을 최소 한번은 방문해야함.근데 꼭 점 2개씩 할필요는 없긴해. 3개도 되고 1개도 된다.dist의 길이가 8밖에 안된다는 점을 이용해 dist 기준으로 brute force를?1명이서 돌면 가장 긴 곳 하나를 제낀다. 2명이서 돌면 가장 긴곳 2곳을 제낀다..결론: n명이서 돌면 가장 긴곳 n곳을 제낀다.가령 dist 가 7,5면 difference의 합이 12이하여야 하고, 각각 7이하 5이..
