난이도: Lv.3유형: 다익스트라해결 여부: 틀림내가 생각했던 아이디어/큰 가닥gates 중 하나 택1, -> summits -> gates 에서 나오는 최댓값의 최솟값 그러면. 편도만 구해도 된다. 간선도 방향성 없다. 간선중심으로 가장 긴 intensity 에서 하나씩 빼면서해야하나 산봉우리는 한번만 큐에 값이 작은거부터 넣고 가능한지 판단하기결국 gates에서 산봉우리로 가는 여정. DP 처럼 기록하기? 그래서 최솟값으로 갱신하는걸로. - 간선은 없다고 했으니 이게 맞는듯. 딕셔너리 쓰면 될듯 오답 이유destionation 스펠링동점자 처리 sort() 안함visited를 len(path)->n으로 바꿔줌그냥 안되는 이유가 좀 명확한계 전단계의 최솟값을 보장하지 않아서 인가? 양수라고 해도 최솟값..
Algorithm/Graph,Tree
난이도: Lv.3유형: 트리 탐색해결 여부: 시간 오래걸려서 해결내가 생각했던 아이디어/큰 가닥-처음에는 문제 이해가 안되었다. 이진트리 만드는 문제인가 했는데 그건 아니었다. 문제 다 읽고 처음에는 다음과 같이 결론내렸다. 이진수 변환후에 앞에 총 길이 2^n-1 꼴로 표현되도록 0을 붙인다.그리고 홀수번째오는 수들은 모두 1이어야만 한다고 생각했다. 즉 이진트리에서 리프노드 아닌건 1이어야 하니까그런데 오답 받고 나서 생각해보니 서브트리 전체가 0이면 상관없었다.그래서 위에서부터 1이라면 아래 가지노드 둘로 쪼개져 큐로 들어가고, 0이라면 큐에 새로 넣지는 않고 조건을 만족하는지만 확인한다. 불만족하다면 즉 자식중에 1이있다면 바로 불가능으로 추가한다.저 제곱 계산식 하는게 빡셌다. 현재 몇층이어서 ..
난이도: Lv.3유형: 트리해결 여부: 정답내가 생각했던 아이디어/큰 가닥그냥 트리로 재귀적으로 하면 될거 같았다.객체지향 쓰기 귀찮았는데 그냥 OOP로 푸는게 깔끔하고 덜꼬일것 같아서 객체지향으로 구했다.오답 이유해답맞았다. 그런데 dict(zip(enrol,referral)) 같은 식으로 하나씩 풀면서 하면 편하게 할 수 있다.#기억할 문법 #내 오답코드#정답코드profiles={}class profile: def __init__(self,referral): self.referral=referral self.money=0 def getmoney(self,pay): notmine=int(pay*0.1) self.money+= (pay-notm..
난이도: Lv.3유형: 그래프 , 다익스트라, bfs해결 여부: 정답내가 생각했던 아이디어/큰 가닥bfs로 풀어야 겠다고 생각했고, 계산을 편하게 하기 위해서 따로 total이라는 딕셔너리 만들었다.오답 이유처음에 변수명이랑, -1 관리 헷갈려서 몇번 디버깅떄 틀리긴했는데 이후 정답 받았다. 해답뭐 해답코드에서 언급한 개선점은 굳이 inf 말고 -1 써도 된다는 점for a,b in x 이런식으로 바로 풀어서 for문 처리할 수도 있다는 점그냥 인덱스 오류 막기 위해 n+1 로 배열 잡는게 좀더 좋다는 점 변수명으로 graph랑 queue 는 예약어 아니어서 그냥 써도 될듯이경우는 bfs 이지만 만약에 노드마다 거리가중치가 있다면 다익스트라 써야한다#기억할 문법 #2차원 배열 빨리좀 만들자total=..
난이도: Lv.3유형: 그래프, 최단경로해결 여부: 틀림내가 생각했던 아이디어/큰 가닥으악 내가 약한 그래프 문제다. 어려워 보인다.그런데 가만 보니 일단 그래프 최단경로 for문 3번 돌아서 구해놓고, 그 걸로 특정 경로 최단으로 구하면 되지 않을까? 싶었다알고리즘 이름은 생각 안나는데 일단 했다. 오답 이유나중에 이를 알고보니 워셜-플로이드 알고리즘이라고 한다.거의 근접했다.틀린 이유는 단 하나, 워셜 플로이드에서는 경유지가 for문에 가장 바깥쪽에 있어야 한다. 그것만 고치니 맞았다.해답경유지를 가장 바깥으로 빼기 #기억할 문법 sum()은 인자가 최대 2개다.#내 오답코드# 일단 각 출발지-> 도착지 까지의 최소값 2차원 배열을 만들어야 하나?def shortestpath(n,fares): ..
난이도: Lv.3유형: 그래프해결 여부: 틀림내가 생각했던 아이디어/큰 가닥문제는 간단한다. 승-패 나와있을때 몇명의 순위나 알 수 있는가?이차원 배열 그래프로 푸는 방식이다.푸는 방법 자체는 어느정도 가닥을 잡았다. 중요한건, 모든 경기를 뛴 놈도 순위가 정해지지만 타율에 의해서도 정해진다는 것 (가령, 전승한놈한테 이기면 걔는 무조건 1등, 반대도 성립)그래서 이차원 배열 만들고 승-패 표에 기록해가면서 AvsB에서 A승, B패로 주어졌을때 A한테 이긴놈은 B한테도 이긴다고 기록하기. B한테 진놈은 A에게도 진다고 기록하기 라는 가닥은 잡았다.오답 이유근데 문제는 두번이상 타고들어갈떄였다. 가령 A한테 이긴놈 한테 이긴놈은 이겼다고 기록해놓아야 했다.그래서 재귀돌리니까 timeout error났다.해..
