분류 전체보기

간만에 다시 푸는 하노이의 탑.다시 풀어도 드는 생각, 왜 이게 lv2? 알고리즘을 생각하기 어렵기도 하고, 맞게 동작해도 제대로 이해된게 맞나 싶다.무튼 문제를 풀어보자.일단 하노이의 탑은 워낙 유명하니 간략하게 설명하면,1번 기둥의 모든 고리를 3번 기둥으로 옮기면 된다. 단, 크기순 배열을 곁들인...그림을 보면 이해는 쉽다.n=2(고리 2개)는 보기가 너무 적어 설명이 어려우니 n=3으로 가정하자.n=3(고리 3개)인 상황 1번 기둥의 가장 큰 고리는 3번 기둥으로 옮기려면 그전까지의 고리를 모두 2번 기둥으로 옮겨야한다.즉, 우리는 n번째의 고리를 옮기기 위해 n-1개의 고리를 2번 기둥으로 옮겨야 한다.이후 1번에 남은 n번 고리를 3번 기둥으로 옮긴다.다시 2번기둥에 있는 n-1개의 고리를 ..

탐색인데 조건이 있으니 백트래킹.타겟으로 주어진 좌표를 순서대로 지나치며 마지막 도착지까지 가는 가짓수를 구하면 된다.방문한 곳은 재방문 불가니까 visit 생성.재귀로 풀었다.가장 기본적인 문제. 생각한다고 좀 골아팠다.import sysinput = sys.stdin.readlinen, m = map(int, input().split())ground = [list(map(int, input().split())) for _ in range(n)]visit = [[False]*n for _ in range(n)]target = []for _ in range(m): y, x = map(int, input().split()) target.append([y-1,x-1])dy, dx = [0, -1,..

성적 데이터를 토대로 각 대회마다 등수를 출력하고, 모든 대회 점수를 합산한 최종 등수를 출력하면된다.이 문제에서 enumerate를 활용하였다.우선 각 대회 점수를 입력 받음과 동시에 enumerate와 lambda를 사용하여 리스트안의 각 요소의 1번 인덱스 기준으로 내림차순 정렬을 했다.그리곤 반복문을 통해 등수를 매겨 출력했다.생각의 정리가 된다면 쉬운 문제다.import sysinput = sys.stdin.readlineN = int(input())all_score = [0] * N# 각 대회별 점수 매기기for _ in range(3): score = list(map(int, input().split())) for i in range(N): all_score[i] +=..

상남자의 수를 구하는 문제.이건 쉽다. lv3 아닌 느낌.친분있는 사람들 중 가장 무거운 무게를 들면 된다. 그럼  상남자 등극.친분있는 사람들을 인덱스에 맞춰 리스트화 시키고, 1번부터 친분있는 사람들과 비교하며 모두를 무게로 이기면 상남자 카운트 +1단 한명이라도 더 무거운 무게를 든다면 상남자에서 탈락. 그러니 for문을 모두 돌 필요는 없는거다.아 물론 친분이 있단건 양방향이란거다. 그러니 양방향으로 리스트화 해주자.import sysinput = sys.stdin.readlinen, m = map(int, input().split())weight = [0] + list(map(int, input().split()))friend = [[] for _ in range(n+1)]for _ in ran..

이 문제는 정말 까다로웠다. 정확히는 지금 내 수준으로 시간내에 풀기에는 무리가 있었다.그래서 제공되는 해설을 한번 보고 풀이를 진행했다.문제는 간단하다. 마을 수 n(정점 수)이 주어지고, 갈수있는 길 m(간선 수)이 주어진다.그리고 쭉 간선이 m개 만큼 주어지고 마지막에 시작과 끝이 주어진다.구해야할건 시작점에서 끝점, 그리고 끝점에서 다시 시작점으로 돌아올 때 출근길에 방문하고 퇴근길에 다시 방문할 수 있는 마을의 수를 구하는 것이다. 말로는 이해가 어렵다. 그림을 보면 쉽다.그림에서 1번 마을에서 3번 마을로 출근한다. 그리고 다시 3번 마을에서 1번 마을로 퇴근한다.길은 많다. 여기서 dfs를 생각하긴 했다. (정점과 간선이 나오면 dfs라고 생각하는 편)그런데 길의 갯수를 구하는게 아닌 경유하..

H-index는 음... 연구자의 역량을 나타내는 지표..? 라는데일단 문제 해설을 하면 예시로 보는것이 편하다.ex) citations = [3, 0, 6, 1, 5] , return = 3citations의 길이는 논문 수,각 요소는 각 논문의 인용횟수이다. 즉, 0번 인덱스의 논문을 3회 인용했다는 것이다.여기서 H-index는 n개의 논문 중, h번 인용된 논문의 갯수가 h개와 같거나 보다 커야한다.물론 h는 h번 인용되거나 그보다 적게 인용된 논문의 갯수를 disused라 했을때,h >= disused 여야한다. 이를 토대로 깊은 생각없이 바로 코드를 작성했다.def solution(citations): answer = 0 n = len(citations) # 논문 수 use..

이번 문제는 줄 서는 방법.3명이 줄을 서는 방법은 3!, 총 6가지이다. 물론 배치는 사전순.이 문제 lv2라 얕보고 고생했다.우선 손으로 풀어보면 3명이 줄서는 방법은 아래와 같다.[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1]여기서, 5번째 순서를 도출해야한다.보면 앞자리에 특정숫자는 (n-1)!의 갯수를 가진다. 무슨 소리냐면1이 앞에 오는 배열은 2개 즉 (3-1)! 개 이다. 처음엔 이게 맞는가 했는데 직접 해보니 맞다.그렇다면 우리가 구해야하는건 5번째, (k-1)/(n-1)! 해주면 해당 index가 나온다.index에 맞는 숫자를 꺼내 answer에 추가한다.그 뒤 숫자배열은 또 (n-1)!이 된다. 즉 n이 0이 될때까지 반복.k는 매번..

이번 문제는 각 노드의 관계가 주어지고, 1번 마을로부터 각 마을까지의 최소거리를 구하여 원하는 결과를 도출한다는 점에서 다익스트라 또는 플로이드 워셜을 생각했다.다익스트라와 힙구조를 사용하였다.거리를 담을 dist 리스트를 생성해주고, 값은 inf로 초기화 했다.(최소거리를 구하기 때문)관계를 담을 graph 리스트를 생성하였다. graph에 담기는 순서는 [ 노드, 배달시간 ] 순서이다.다익스트라 알고리즘을 작성하는데,heap 을 생성하고 그 안에 시작 값을 담았다. [ 1, 0 ] 이후 반복문을 통해 heap이 빌때까지, 각 노드의 관계와 시간을 꺼내면서 시간을 비교하여 작은것을 담는 동시에 경유할때 발생하는 시간 또한 포함하였다. dist에 값을 계속해서 변경하였고, 이후 다시 heap에 담고 이..