forDevLife

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 1. 주어진 직사각형 범위를 모두 1로 채운다. 2. 주어진 직사각형보다 1씩 작은 범위를 모두 0으로 채워 속을 비워낸다. 3. 테두리를 따라서 아이템에 도달할 때까지 BFS를 진행한다. 고민 만약 좌표 사이즈를 1로 하게되면, BFS시 명확하게 테두리를 구분할 수 없다. 아래 예시는 문제에서 주어진 예시 2번의 테두리를 매핑(위에서 언급한 접근 1번까지 수행)한 것이다. 이제 테두리보다 1만큼 작은 위치의 테두리를 모두 비우면 다음과 같다. (접근 2를 통해 0으로 변경) 이 상태에서 BF..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 1. combination으로 경우의 수를 만들고 교점을 추출한다. 2. 해당 교점이 정수라면 result에 넣는다. 3. result에서 x_min, x_max, y_min, y_max를 뽑고, 해당 사이즈 만큼 배열을 만들어 '.'로 초기화 한다. 4. result를 하나씩 반복하며 일치하는 좌표에 '*'를 넣는다. 코드 def solution(line): result = [] for i in range(0, len(line) - 1): A, B, E = line[i] for j in ra..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근 1) 플로이드 워셜 - 실패 처음엔 모든 노드 간 최단 거리를 알아야 한다고 생각되어 플로이드 워셜로 접근하고, costs를 다시 탐색하면서 갱신된 테이블과 값이 일치할 경우에 result에 더하는 방식으로 접근했다. 하지만 이럴 경우 사이클이 있을 때 중복되어 값이 더해지는 경우가 발생한다. 아래와 같은 그래프가 있을 때 모든 노드를 연결하기 위한 경로는 빨간색 동그라미인 1, 2만 있으면 된다. 하지만 위와 같이 접근하면 3으로 접근하는 경로도 3으로 주어져있기 때문에 더해지게 되므로 오..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 현 index에서 가장 가까운 위치를 양쪽에서 찾고 그 위치로 이동하는 방식으로 접근하였으나, 수많은 테스트케이스에서 실패했다. 무조건 가까운 쪽을 선택하는게 최선이 아닌 케이스들이 존재하기 때문이다. 예를 들어, ABABAAAAABA를 살펴보자. 위 알고리즘으로 접근하면 최초 [0]에서 [1]위치의 'B'가 제일 가깝기 때문에 여기 먼저 접근하게 된다. 하지만 실제로는 왼쪽으로 먼저 가서 'B'를 바꾼 후에 다시 오른쪽으로 와야 최소 경로가 된다. 즉, 매 순간 왼쪽 혹은 오른쪽으로..

문제 링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 import heapq def solution(food_times, k): # 전체 음식 시간 보다 k가 크다면 더이상 먹을게 없는 것이기 때문에 -1을 반환한다. if sum(food_times) k보다 작거나 같을 때만 수행한다. cur_sum = 0 before_food_count = 0 all_food_count = len(q) # 지금까지 소모된 시간 + (이제 소모될 시간)이 k보다 작을 때만 해당음식을 여기 반복문에서 한꺼번에 Pass시킬 수 있다. while cur_sum + (..

문제 N개의 동전을 이용하여 만들 수 없는 양의 정수 금액 중 최솟값을 구하는 프로그램을 작성하시오 입력 조건 첫째 줄에는 동전의 개수를 나타내는 양의 정수 N이 주어진다. (1

자세한 설명은 위키 참고 : https://ko.wikipedia.org/wiki/%ED%80%B5_%EC%A0%95%EB%A0%AC 간단히 그림과 수식을 통해 계산해보자. 그림 설명 1. 최초 N개를 대상으로 pivot과 비교를 수행한다.(N-1이지만 근사) 2. 쪼개며 1이 될 때까지 동일하게 비교를 수행한다. 쪼개지더라도 전체로 보면 결국 N번 비교가 된다. 3. 2의 횟수는 logN이 될 것이다. 결국, T(N) = N + (logN * N) = N*logN으로 계산된다. 수식 증명 : 위의 그림과 결국 같다. T(N) = N + 2T(N/2) = 2T(N/2) + N = 2(2T(N/4) + N/2) + N = 4T(N/4) + N + N = 4T(N/4) + 2N = 4(2T(N/8) + N/..

플로이드 워셜로 풀었다. i -> j를 먼저 입력 받았고, k를 거쳐서 갈 경우를 반영하여 최소 거리를 계산할 수 있다. 1->1은 다시 돌아오는 경우이므로, i->j && j->k 경로가 둘 다 1일 경우 i->j는 있는 경로가 되게 된다. 플로이드 워셜 참고 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221234427842&proxyReferer=https:%2F%2Fwww.google.com%2F import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { pu..

island의 DFS와 매우 유사하다. 다만 DFS안에서 value를 0으로 바꾸는 과정에서 바꾼 횟수를 세어 arraylist에 넣는게 추가되었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int[] dx = {-1, 0, 1, 0}; static int[] dy = {0, 1, 0, -1}; static int[][] arr; static int N; static ArrayList arrayList = new ArrayList(); static int temp = 1; public static ..

전형적인 BFS 문제이다. 표의 입력이 일반적인 1 0 1 1이 아닌 1011로 들어오는데, String.split("")을 이용해 분리하고 Integer.parstInt로 하는 것보단, String.charAt() - '0'을 통해 바로 int로 넣어버리는게 훨씬 빠르다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; class Point { int x; int y; public Point(int x, int y) { this.x = x; this.y = y; } } public class Main { static int[] dx = {-1, 0, ..