python

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

    [프로그래머스 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..

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

    (Python) 백준 2578번 - 빙고

    문제 링크: https://www.acmicpc.net/problem/2578 풀이단순 구현 문제로, 우리가 빙고 게임을 실제하는 방법을 코드로 구현하면 되는 간단한 문제이다. 먼저 입력받은 숫자들을 board라는 배열에 담아, 빙고판을 완성한다. 다음으로 사회자가 부르는 수들을 called_nums라는 배열에 저장한다.사회자가 수를 하나씩 부를 때마다 숫자를 board에서 지우고(-1로 변경), 현재 board의 상태에서 몇 개의 빙고가 존재하는지 카운트한다. 그리고 카운트한 값이 3 이상이면 그 때의 수가 몇번째로 부른 숫자인지 출력하면 된다. 주의해야할 점은 반드시 3 이상인지 체크해야한다는 것이다. 빙고의 수가 정확히 3인지 체크를 하다보니, 하나의 수에 의해 빙고가 한 번에 2개 이상 완성되는 ..

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

    [프로그래머스 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): ..

티스토리툴바