알고리즘

[프로그래머스 Lv.2] 전화번호 목록 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제의 유형은 해시로 되어있으나, 사실 해시를 사용하지 않고 정렬 후 다음 인덱스의 값이 현재 인덱스의 값으로 시작하는지 확인하는 방식으로 공간 복잡도도 낮추고, 시간 복잡도도 낮출 수 있는 방식이다.하지만 이 문제의 유형이 해시이기에 해시를 사용하여 풀이하였다.코드를 읽는 입장에서는 해시 방식이 더 간결하고 명확하게 보이는 것 같다.def solution(phone_book): ..

(JAVA) 거스름돈

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에 이 문제를 딱 보았을 때는 DFS로 풀면 되지 않나라는 생각을 가지고 코드를 빠르게 작성했다. 작성 후에 테스트 케이스들도 무난하게 통과하고, 나름대로 엣지 케이스들도 추가하여 테스트를 진행했는데 모두 잘 통과해서 기분 좋게 제출을 하였지만 역시나 한번에 통과할 수 없었다. 필자가 푼 방법으로는 money 배열에 중복된 값이 들어오는 경우에는 실패하는 코드였고, 만약 올바..

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다. 코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다. "(", 열린 괄호로 시작하여 나올 수 있는 괄호 조합들을 하나씩 탐색하는 것을 DFS 알고리즘을 사용하여 풀이하였다. 열린 괄호의 수를 open, 닫힌 괄호의 수를 close라고 하고, 아래와 같은 종료 조건들을 ..

(JAVA) 올바른 괄호의 갯수

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12929 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 난이도가 4인 문제임을 생각하면 코드가 매우 단순함을 확인할 수 있다. 코드 자체는 단순한데 문제 풀이를 위한 방법을 생각하는 것이 어려운 문제라고 생각할 수 있다. n개 이전의 괄호쌍으로 만들 수 있는 개수를 활용하는 Dynamic Programming을 사용하여 풀이하였다. 예를 들어 괄호쌍 2개와 3개를 사용해 만들 수 있는 전체 올바른 괄호쌍의 개수를 계산해 보겠다. 우선..

(JAVA) 양과 늑대

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 class Solution { int[] gInfo; // DFS에서 사용할 노드의 정보 int[][] gEdges; // DFS에서 사용할 간선의 정보 int maxValue = 0; public int solution(int[] info, int[][] edges) { gInfo = info; gEdges = edges; boolean[] isVisited = new bool..

(JAVA) 합승 택시 요금

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 최소거리비용 알고리즘으로 유명한 다익스트라 알고리즘을 사용한 풀이이다. 전체적인 문제 해결 방법은 아래와 같다. mat이라는 이름의 인접 행렬을 각 지점 간의 금액을 담고 있는 fares 배열을 사용하여 생성한다. mat을 바탕으로 두 사람이 합승하여 출발 지점부터 다른 모든 정점까지 가는 최소 비용을 다익스트라 알고리즘을 사용하여 알아내고 이를 both라는 배열에 저장한다. 시..

(JAVA) 길 찾기 게임

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42892 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이진트리를 사용한 기본적인 문제이다. 아래와 같은 순서로 구현해나가며 문제를 풀 수 있었다. 트리에 사용할 Node 클래스 구현 nodes라는 node들을 담을 리스트에 node를 삽입 nodes를 y의 내림차순으로, y가 동일하다면 x의 오름차순으로 정렬 (트리에 올바른 순서대로 담기 위함) 정렬된 리스트에서 node를 하나씩 꺼내면서 트리 만들기 완성된 트리를 전위 순회한 값..

(JAVA) 금과 은 운반하기

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/86053 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분 탐색과 Parametric Search를 사용한 풀이이다. Parametric Search는 특정 상황을 만족하는 특정값의 최대 혹은 최댓값을 구하는 최적화 문제에 적용할 수 있음을 생각하고, 이 알고리즘을 이번 문제에 적용할 생각을 하는 것이 중요하다. Parametric Search는 최적화 문제를 결정 문제로 바꾸는 것이다. 이번에 풀이한 '금과 은 운반하기' 문제를 ..

(JAVA) 백준 2805번 - 나무 자르기

문제 링크: https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 풀이 처음에는 브루트 포스를 사용하여 아래와 같이 풀이해 보았다. import java.io.*; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class Main { public static void main(String[] a..

(C++) 백준 9372번 - 상근이의 여행

문제 링크 : https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 풀이 상근이가 최소한의 수의 비행기로 모든 나라를 돌아다니는 것은 최소 신장 트리를 순회하는 것과 동일하다. (정점 - 1) 개의 간선이 최소 신장 트리에 존재하므로, 비행기도 (정점 - 1) 개를 타게 된다. #include int t, n, m, a, b; using namespace std; int main(){ cin >> t; while..