알고리즘 (305) 썸네일형 리스트형 [프로그래머스] 합승 택시 요금 https://school.programmers.co.kr/learn/courses/30/lessons/72413🤔 문제분석주어진 문제를 풀기위해서는 플로이드 워셜을 알고 있어야한다.임의의 노드로부터 각 임의의 노드까지 모든 최단경로를 구한다.s로 부터 임의의 노드를 들려서(a와 b가 같이 택시를 탐) 각 a, b 노드까지 가는 거리중 최소값을 고르면 된다.물론, n이 300이기 때문에 플로이드 워셜로 접근해도 되지만 만약 n이 더 커질경우 $n^3$ 시간복잡도가 크게 증가 할 수 있다. n이 충분히 커진다면 데이크스트라를 고려하는것도 하나의 방법이 될 수 있겠다.💻 코드import sysdef solution(n, s, a, b, fares): distance = [[sys.maxsize] *.. [프로그래머스] 튜플 https://school.programmers.co.kr/learn/courses/30/lessons/64065 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🤔 문제분석데이터를 전처리하고 리스트의 크기 기준으로 정렬한뒤 순회하면서 현재 존재하지 않는 값을 넣어주면 된다.💻 코드def solution(s :str): temp = s.lstrip('{').rstrip('}').split("},{") for i in range(len(temp)): temp[i] = list(map(int, temp[i].split(','))).. [프로그래머스] 호텔 방 배정 https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🤔 문제분석유니온-파인드(서로소 집합) 으로 문제를 접근하면 된다.k개의 수가 매우 크기때문에 기존 리스트를 사용한 접근 방식 대신에 딕셔너리를 활용하였습니다.만약 parent에 해당하는 숫자가 없다면 parent 를 생성하고 v+1 ( 자기자신보다 + 1 큰 노드를 가르키게 만든다)만약 parent에 해당하는 숫자가 있다면 parent의 노드를 재귀적으로 따라가서 parent에 없는 노드까지 따라.. [프로그래머스] 크레인 인형뽑기 https://school.programmers.co.kr/learn/courses/30/lessons/64061 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🤔 문제분석스택자료구조를 활용하여 해결하였습니다.주어진 보드를 문제에서 주어진 그림과 같이 스택 자료구조로 변환한다.원하는 위치에가서 뽑아서 바구니에 집어넣는다.바구니의 마지막 부분에 같은 인형이 온다면 인형을 제거시켜준다.💻 코드def solution(board, moves): bag = [] n = len(board) new_board = [[] for _ in rang.. [프로그래머스] 징검다리 건너기 https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 🤔 문제분석n명의 사람이 징검다리를 건널때, 최대 몇명이 건널 수 있는지 찾는 문제로 사람의 명수를 기준으로 이분탐색 정답을 찾아냈습니다.start = 0, end = 200000001 ( 징검다리가 버틸 수 있는 최대 크기 200000000)mid 값을 기준으로 징검다리를 건널 수 있는지 없는지 확인하는데, 연속적으로 k개의 다리를 띄어 넘을 수 없다면 건널 수 없다.건널 수 있냐 (?) 건널수 .. [프로그래머스] 빛의 경로 사이클 https://school.programmers.co.kr/learn/courses/30/lessons/86052 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🤔 문제분석그래프 탐색문제로 한 방향으로 들어갔다면 다음에 탐색을 할 필요가 없습니다. 다음 탐색시 똑같은 루트로 탐색되기 때문입니다.문제의 이미지를 보고 방문처리를 활용하여 문제를 해결해야겠다는 생각이 들었습니다. 한 노드에서 방문 처리해야할 조건은 8가지 인데 8가지는 아래와 같습니다.IN ( 상, 하, 좌, 우 ) 4개OUT ( 상, 하, 좌, 우) 4개문제에서 제시한 조건으로 깊이우선탐색 합니.. [프로그래머스] 금과 은 https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🤔 문제분석주어진 입력값이 상당히 크다면 이분탐색을 의심했어야했는데, 다른 방식으로 문제를 해결하려고 한참 해맸던 문제입니다.시간을 기준으로 이분탐색을 하는데 해당 시간에 모든 금과, 은을 가져다 놓을 수 있는지 없는지 확인합니다.금과 은을 모두 나를 수 있다면 시간을 좁혀 탐색해봅니다.금과 은을 모두 나를 수 없다면 시간을 늘려 탐색해봅니다.💻 코드# # 시간을 기준으로 이분탐색한다.import .. [프로그래머스] 트리 트리오 중간값 https://school.programmers.co.kr/learn/courses/30/lessons/68937 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr🤔 문제분석트리의 성질과 중간값의 성질을 이용하여 해결하는 문제이다.간선이 단 1개 연결되어있는 노드에서 다른 노드 까지의 거리를 구하면 반드시 최대값을 갖는다. ( 트리의 성질 )간선이 단 1개 연결되어있는 노드를 찾기위해서는 특정 아무 노드에서 다른 노드까지의 최대 거리 값을 가지고 있는 노드가 간선이 단 1개 연결되어있는 노드이다.특정 노드에서 간선이 1개인 특정노드를 구한다.간선이 1개인 노드.. 이전 1 2 3 4 5 ··· 39 다음