프로그래머스

(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는 최적화 문제를 결정 문제로 바꾸는 것이다. 이번에 풀이한 '금과 은 운반하기' 문제를 ..