알고리즘

[프로그래머스 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풀이우선순위 큐를 활용하여 풀이한 문제이다. 현재 시간에서 처리할 수 있는 가장 소요시간이 적은 작업부터 우선적으로 우선순위 큐에서 꺼내 처리하게 하면, 최소의 평균 시간으로 전체 작업들을 처리할 수 있다. 먼저, 현재 시간까지 요청된 모든 작업들을 우선순위 큐에 넣는다. 다음으로 소요 시간이 가장 적은 작업부터 우선순위 큐에서 꺼내 처리를 진행한다. 만약 처리할 수 있는 작업이 없다면, ..

(Python) 백준 14503번 - 로봇 청소기

문제 링크: https://www.acmicpc.net/problem/14503풀이구현/시뮬레이션 문제로 풀이를 위해 딱히 복잡한 알고리즘이 필요하지 않다. 하지만 골드 문제이기에 조금 복잡한 구현을 거쳐야한다. 코드에서 가장 중요한 부분은 다음 이동 방향을 파악하는 것이다. 반시계 방향으로 청소해야할 부분이 있는지 체크해야한다고 했으므로, 북 -> 서 -> 남 -> 동 방향으로 체크해야한다. 이는 코드 상에서 0 -> 3 -> 2 -> 1인데, 여기에 +4를 더하고, 4로 나눈 나머지를 사용하여 마치 4 -> 3 -> 2 -> 1인 것처럼 체크될 수 있도록 하여서 로봇 청소기의 방향 전환을 쉽게 구현하였다.위의 방향 전환 구현이 조금 고민이 되고 어려운 파트였으나, 나머지는 단순히 어려움 없이 문제에 ..

[프로그래머스 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가 이긴 모든 사람들에게 이기게 된다.위와 같은 과정을 반복하여서 모든 선수들의 승/패 관계를 모두 그래프..