알고리즘

[프로그래머스 Lv.3] 단어 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이BFS를 사용한 풀이이다. 풀고 나니 원래 보통 BFS라고 할 때 사용하는 while과 deque를 사용한 구조로 풀이되진 않았으나.. 어찌 됐든 한 단계씩 진행되는 BFS 구조를 사용하여 문제 풀이를 진행했다. 문제에 적힌 대로 주어진 단어의 한 글자씩 변환하며, 변환된 단어가 words 배열에 있는지 체크하고, 또 동시에 이전에 이미 변환을 진행했던 단어가 아닌지 확인하였다. 확인을 통과한 새로운 단어들을 모아 새로운 단계에서..

[프로그래머스 Lv.2] 괄호 변환 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/60058 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이DFS와 구현이 섞인 문제로 볼 수 있다. 흔히 볼 수 있는 DFS 문제와 다르긴 하나, 재귀를 사용해 한 문장 p의 끝까지 들어가며 특정 로직을 적용하기에 DFS 문제라고 생각한다.구현 부분은 어려운 알고리즘을 사용하는 게 아니다 보니, 문제에 주어진 대로 그저 한 단계씩 구현하면 된다. 한 단계씩 구현해 나가고, 재귀적으로 다시 실행해야 하는 부분은 DFS를 통해 진행하면 비교적 쉽게 풀 수 있다.  처음에는 p의 길이가 10..

[프로그래머스 Lv.3] 여행경로 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이DFS를 활용한 문제이다. dictionary를 활용하여 전체 티켓들을 사용해 마치 graph와 같은 구조를 완성하고, 이를 DFS로 순회하면 된다. DFS로 순회하며, 더 이상 이동할 수 없는 경우가 되면 그 때 위치하는 공항을 answer 배열에 저장한다.다만 주의해야할 점이 있는데, 가능한 경로가 2개 이상일 땐 알파벳 경로가 앞서는 경우를 반환하라고 했기 때문에 그래프를 완성할 때 정렬이 필요하다는 점을 고려하며 구현해야 ..

[프로그래머스 Lv.2] 타겟 넘버 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이재귀함수를 사용한 DFS를 이용한 풀이이다.재귀함수의 인자로는 숫자들을 사용하여 더하거나 빼기를 진행한 현재까지의 누적값이고, 다른 하나는 현재까지 더하기 또는 빼기에 사용한 숫자의 수이다.초기값은 누적값은 0, 사용한 숫자의 수는 0으로 하였다.종료 조건은 당연하게도 모든 숫자가 사용되었을 때, 즉 numbers 배열의 길이와 사용한 숫자의 수가 같을 때이다.또한, 종료할 때 만약 문제에서의 조건인 누적합이 타겟 넘버와 같은 경..

[프로그래머스 Lv.2] 줄 서는 방법 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12936 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이처음에 단순하게 문제를 생각했을 때, itertools의 permutation을 활용하여 순열을 모두 생성해 두고, 여기서 k번째에 해당하는 순열을 찾는 방식으로 해결하려 하였다. 하지만 n의 최댓값인 20의 경우를 생각하여 보면, 20!이라는 어마무시한 숫자이기에 이 방법으로는 해결이 불가능하였다. 그래서 약간은 수학적인 방법을 사용해보았다. n=3일 때의 간단한 예시를 들어보겠다.[1, 2, 3], [1, 3, 2], [2, ..

[프로그래머스 Lv.2] 스킬트리 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49993 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이스킬트리대로 스킬을 하나씩 배워나갈 때마다 해당 스킬이 선행 관계가 존재하는 스킬인 경우, 그 스킬이 순서에 맞게 배워졌는지 체크하고 만약 그렇지 않다면 이는 옳지 않은 스킬트리이므로 바로 배제하고, 스킬트리의 모든 스킬들을 모두 무사히 배웠다면 이는 올바른 스킬트리인 것이다. 즉, 스킬이 선행 관계가 존재하는 스킬인지 확인하는 로직과 순서에 맞게 배워졌는지 체크하는 로직을 코드로 구현하면 쉽게 풀 수 있는 문제이다. 먼저 스킬이..

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