알고리즘

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.2] 2개 이하로 다른 비트 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/77885 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수를 구하는 함수를 구현하는 문제이다.구현 문제이기에 우선 간단한 예시를 통해 규칙을 찾아야한다. 2부터 시작하여 규칙을 찾아보겠다.2는 이진수로 10이고 2보다 크고 2와 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 11으로 3이다.3은 이진수로 11이고 3보다 크고 3과 비트가 1~2개 다른 수들 중 제일 작은 수는 이진수로 101으로 5이다.4는 이진수..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 섬 연결하기 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이전에 최소 신장 트리를 그리는 문제에서 사용하였던 Union-find을 통해 구현한 크루스칼 알고리즘을 사용하여 풀이하였다. 우선 Union-find를 사용하기 위해 관련 함수들을 구현한다. 이후 크루스칼 알고리즘을 사용하여 최소 신장 트리를 그리는 작업을 수행하면 된다.먼저 각 섬 간의 건설 비용이 낮은 순서대로 정렬하여, 결과적으로 가장 최저의 비용이 나올 수 있도록 한다.다음으로..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 보석 쇼핑 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이투포인터를 사용한 풀이이다. 시작 포인터와 끝 포인터를 두고, 그 포인터 사이에 위치한 보석들의 종류가 주어진 조건을 만족하는지 확인하며 두 개의 포인터를 조절해가며 최소 길이의 범위를 찾으면 되는 문제이다. 두 개의 포인터 모두 인덱스 0에서 시작한다. 만약 두 포인터 사이에 위치한 보석의 종류가 모든 보석의 종류보다 적다면, 끝 포인터를 1 증가시켜 사이에 위치한 보석의 수를 증가시..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 디스크 컨트롤러 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선순위 큐를 활용하여 풀이한 문제이다. 현재 시간에서 처리할 수 있는 가장 소요시간이 적은 작업부터 우선적으로 우선순위 큐에서 꺼내 처리하게 하면, 최소의 평균 시간으로 전체 작업들을 처리할 수 있다. 먼저, 현재 시간까지 요청된 모든 작업들을 우선순위 큐에 넣는다. 다음으로 소요 시간이 가장 적은 작업부터 우선순위 큐에서 꺼내 처리를 진행한다. 만약 처리할 수 있는 작업이 없다면, ..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.2] 할인 행사 (Python)

    문제 풀이: https://school.programmers.co.kr/learn/courses/30/lessons/131127 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이파이썬의 dictionary를 사용해서 쉽게 풀 수 있는 문제이다.먼저 required라는 딕셔너리에 구매해야 할 상품들을 key로, 구매해야 할 개수를 value로 해서 저장을 한다. 다음으로 첫날부터 마지막날 - 10일까지 시작 날짜로 잡아두고, 다음 10일간의 상품들을 required와 마찬가지로 상품들을 key로 구매할 수 있는 개수를 value로 저장한다.각 날짜별로 requ..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.2] 피로도 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제는 순열을 사용하여 모든 가능한 던전의 조합을 구하고, 각 조합들을 주어진 피로도 이내에 모두 탐험할 수 있는지 체크함으로써 해결할 수 있다. 즉, 일반적인 완전 탐색 방식으로 풀 수 있는 것이다.from itertools import permutationsdef check(k, permutation): # permutation에 들어있는 던전의 순열을 k의 피로도로 모두 통과할..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 길 찾기 게임 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이진트리, 전위 순회, 후위 순회를 사용한 문제로 알고리즘 문제 풀이를 하다 보면 종종 나타나기에 구현을 해본 경험이 있어 레벨 3 문제치고는 쉽게 풀 수 있었다. 그렇지만 좌표를 사용해서 트리를 그려야 한다는 점, 좌표뿐만 아니라 nodeinfo 내에서 위치한 번호도 알고 있어야 한다는 점이 기존의 이진트리를 사용한 문제가 달랐다고 할 수 있겠다. 우선, 트리의 레벨은 y좌표에 의해 ..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 순위 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이우선 경기 결과 results를 토대로 승리한 사람들과 패배한 사람들을 파악하여 그래프를 그린다.모순이 없고 실력이 뛰어난 선수가 항상 이긴다는 보장이 있으므로 만약 B가 A에게 졌다면, A가 진 모든 사람들에게 B도 모두 지게 된다. 같은 맥락으로 A가 B에게 이겼으므로, A는 B가 이긴 모든 사람들에게 이기게 된다.위와 같은 과정을 반복하여서 모든 선수들의 승/패 관계를 모두 그래프..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.3] 가장 먼 노드 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이3단계 치고 BFS를 사용하는 문제이기 때문에, 풀이 방법이 익숙해 쉽게 풀 수 있었던 것 같다. BFS처럼 큐를 사용해 그래프를 순회하면서 시작 정점(1번 정점)에서부터의 거리를 계산하고, 이 중 거리가 가장 먼 정점들의 수를 세는 방식으로 간단하게 풀이할 수 있다.from collections import defaultdict, dequedef solution(n, edges): ..

    알고리즘/알고리즘 문제 풀이

    [프로그래머스 Lv.2] 기능개발 (Python)

    문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제 유형이 스택/큐 문제라고 지정되어 있긴 하지만, 스택이나 큐를 사용하지 않고 풀이하였다. 문제 풀이 아이디어는 아래와 같다.우선 ceil 내장 함수를 사용해 완료되기까지 걸리는 날짜를 새로운 배열 rests에 저장한다.rests 배열을 순회하며, 현재 인덱스의 이전까지의 최대값(max_time)보다 큰 값이 나타날 때까지의 누적값(cnt)를 키워간다.max_time은 아직까지 ..

티스토리툴바