https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제 유형 다이나믹 프로그래밍 DFS 문제 풀이 이 문제는 DFS(깊이 우선 탐색) 과 다이나믹 프로그래밍 으로 각각 해결할 수 있다. DFS DFS 를 이용한 풀이 방법은 매우 간단하다. 별도의 방문처리 배열을 사용하지 않고, 조건에 맞게 재귀를 수행하면 된다. 이런 점에서 재귀를 이용한 구현 문제에 더 가깝다고 할 수도 있다. 소스 코드 import java.util...

https://school.programmers.co.kr/learn/courses/30/lessons/42895 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 다이나믹 프로그래밍 문제 풀이 이 문제는 동적계획법, 즉 다이나믹 프로그래밍 을 이용하여 해결할 수 있다. 처음에는 문제에서 주어진 number 와 관련된 점화식을 세워 접근하려 했으나 쉽지 않았다. 그래서 N 의 사용횟수에 따라 가능한 값을 구하는 방식을 사용했다. 이해를 돕기위해 한가지 예를 들어보자. N 이 5일 때, N 의 사용횟수에 따라 가능한 값들은 아래와 같다. N의 사용횟..

https://school.programmers.co.kr/learn/courses/30/lessons/42860 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 유형 그리디 문제 풀이 이 문제는 항상 최선의 경우를 선택하는 그리디 알고리즘을 이용하여 해결할 수 있다. 문제를 해결하기 위해, 조이스틱을 상하로 움직이는 부분과 좌우로 움직이는 부분으로 나눠 구현해야 한다. 상하로 움직이는 부분의 경우 쉽게 구현할 수 있다. name 을 알파벳 별로 차례로 탐색하면서 조작 횟수가 더 작은 방법을 선택하면 된다. 만약 알파벳 Z를 만든다면, A부터 Z까지 ..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 유형 다이나믹 프로그래밍 비트마스킹 문제 풀이 이 문제를 완전 탐색으로 접근한다면, 시간초과 판정을 받게 된다. 왜냐하면 모든 도시를 탐색하는데 드는 비용은 순열의 비용과 동일하기 때문에 (N-1)! 의 시간복잡도를 가진다. 다이나믹 프로그래밍을 이용하면 반복되는 부분을 제거하여 시간복잡도를 줄일 수 있는데, 이해를 돕기 위해 한 가지 예를 살펴보자. N..

안녕하세요! 오늘은 알고리즘 문제에서 자주 볼 수 있는 순열과 조합을 구현하는 방법에 대해 간단히 소개시켜 드리고자 합니다🤗 순열(Permutation) 순열이란? n개의 숫자 중에서 r개의 숫자를 순서대로 뽑는 경우를 의미합니다. 예를 들어, [1, 2, 3] 배열 중 2개의 숫자를 순서대로 뽑은 결과는 아래와 같습니다. [1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2] 위와 같은 순열은 각각 Swap과 백트래킹을 이용하여 구현할 수 있습니다! Swap // Swap class Permutation { private int n; private int r; private int[] now; // 현재 순열 private ArrayList result; // 모든 순열 public..

자바 컬렉션 중 하나인 Map을 순회하는 방법 3가지를 간단히 알아보겠습니다. 1. Iterator Map map = new HashMap(); Iterator it = map.keySet().iterator(); whlie(it.hasNest()) { String key = it.next(); int value = map.get(key); } 2. Entry Map map = new HashMap(); for(Map.Entry entry : map.entrySet()) { String key = entry.getKey(); int value = entry.getValue(); } 3. keySet() Map map = new HashMap(); for(String key : map.keySet()) {..

String형 문자열을 char[]형 배열로 변경 배열 정렬 char[]형 배열을 다시 문자열로 변경 StringBuilder를 이용해 문자열 역순 String s = "1245830"; char[] cArr = s.toCharArray(); Arrays.sort(cArr); String s2 = new String(cArr); String result = new StringBuilder(s2).reverse().toString(); 추가로 char[]형 배열을 String으로 바꾸는 방법에 대해 소개하도록 하겠습니다. 크게 4가지 방법이 있으며, 아래와 같습니다. String 생성자 String.valueOf() StringBuilder Stream 1) String 생성자 char[] cArr = {..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제상황 처음 이 문제를 접했을때, 저는 강의의 시작(start) 및 끝나는 시간(end)을 담은 Lecture 클래스를 만든 뒤에 입력 값에 따라 LinkedList 리스트에 담았습니다. 그리고 해당 리스트를 강의실 시작시간 기준 오름차순으로 정렬한 뒤, 리스트 내 첫번째 아이템을 기준 값을 정하고 순회하였습니다. 순회 값을 poll 한 뒤 기준 값의 끝나는 시간보다 순회 값의 시작 시간이 크거나 같으면 기준 값을 순회 값으로 바꿔주고, 그렇..

문제출처: https://programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 해당 문제를 풀기 위해 많은 시간을 잡아먹었고, 특히나 단순 조합만을 이용하는 것이 아닌 여러 까다로운 조건들이 있어서 쉽지 않았던 문제였습니다. 처음에 접근할때는 손님기준으로 조합을 사용했었지만, 이는 여러 테스트 케이스에서 통과 되지않는 오류가 있어 손님별 메뉴 기준으로 조합을 사용했습니다. 아무래도 전자 방법을 이용하면 여러조건에서 탈락되는 부분이..

문제출처: https://programmers.co.kr/learn/courses/30/lessons/12899 코딩테스트 연습 - 124 나라의 숫자 programmers.co.kr 해당 문제를 해결하기 위해 많은 시간을 투자했지만, 쉽사리 문제해결 및 효율적인 코드를 작성하는데 있어서 어려움을 겪었습니다. 결국 다른 분의 코드를 참고해서 매우 쉽게 해결할 수 있었던 문제였습니다.. 124나라의 진법? 규칙은 3진법과 매우 흡사하지만 3으로 나누어떨어질때 즉 3진법에서 0이 포함될 경우에만 값이 다르게됩니다. 그 이유는 무엇일까요? 3진법은 0의 표현이 있지만 124나라는 0의 표현이 없기 때문에 발생하는 아주 간단한 문제였습니다. 따라서 코드를 효율적으로 작성하기위해 3진법을 이용하면서 3으로 나누어..