devlog

이분 탐색 문제 해결 전략

이분 탐색 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 전발씩 좁혀가며 데이터를 탐색하는 방법이다.시간 복잡도는 NlongN이다.def binary_search(left, right, array, target): while left target: right = mid - 1 else: left = mid + 1이분 탐색 알고리즘이다. 보통 PS에서 이분 탐색을 적용하는 방법은 완전 탐색을 해야 하는 문제 O(N^2)를 NlogN으로 해결하는 과정에서 많이 쓰인다.아래의 두 문제 예시를 보자 https://www.acmicpc.net/problem/1939백준 중량 제한 문제에서도 완전 탐색의 풀이 즉 최대 중량을 1부터 최대 까지 하나씩..

출처 : https://www.acmicpc.net/problem/1939 1939번: 중량제한 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 www.acmicpc.net 풀이 방법 카카오 기출문제인 등산코스 정하기 문제랑 유사하여 알고리즘을 조금 수정해서 제출했다. https://salmon16.tistory.com/142 다른 분들은 이분 탐색으로 풀이하던데 좋은 방법인 거 같다. 문제를 해결하기 위해 다익스트라 알고리즘을 변형해서 사용했다. 원래 다익스트라 알고리즘에선 다음 노드를 갱실 할 때..

출처 : https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 방법 문제에서 핵심은 정렬과 그리디이다. 가방을 넣을 수 있는 가능한 무게로 오름차순으로 정렬한 후 수용가능한 무게가 낮은 가방부터 채워주어야 한다. 왜냐하면 만약 가능한 가방이 10, 5(무게) 이렇게 2개 있고 보석이 (5, 100), (7, 7) (무게, 가격) 이렇게 2개가 있다고 가정을 했을 때 10인 가방부터 채..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 완전 탐색 + 그래프 탐색 방법으로 방문하지 않은 노드일 때 그 점부터 그래프 탐색을 하며 연결된 지점을 같은 네트워크로 묶고 answer를 +1 해주고 다시 완전 탐색으로 방문하지 않은 노드를 찾아 그래프 탐색을 하는 방식으로 해결했다. import java.io.*; import java.util.*; class Solution { static int N; static in..

출처 : https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 방법 그리디로 풀어야 한다. 가장 큰 수를 만들기 위해 각 알파벳 자릿수를 계산해서 큰 거부터 9를 할당해 주면 된다. 알바벳을 계산할 때 제일 왼쪽부터 10을 곱하면서 계산하면 된다. import java.io.*; import java.util.*; public class Main { static int N; static int[] alphabet = new int[26];..

출처 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 방법 dp로 풀어야 하는 문제이다. dp를 설정할 때 문제를 잘 나누어야 한다. dp를 나눌 때 이전 상황에 영향을 받지 않고 앞으로의 상황에만 영향을 받도록 문제를 나누었다. dp[y][x]를 y, x에서 최대로 이동할 수 있는지로 설정했다. dfs함수 안에서 이동 가능한 부분으로 이동할 때 ret의 값과 1 + dfs(ny, nx) 값 중 더 큰 값을 ret에 업데이트..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368?language=java 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 처음으로 할일율을 조절하는 그리디 방법을 생각했으나 할인율이 너무 높아도 안되고 너무 낮아도 안된다고 생각해서 dp 방식을 생각해 봤다. 하지만 dp방식도 이모티콘 개수에 따라, dp 배열이 너무 달려져 완전탐색 방식으로 풀어야겠다고 생각했다. 먼저 완전 탐색 방법의 시간 복잡도를 계산해 봤는데 할인이 4가지 경우 밖에 없고 이모티콘도 최대 7개 까지..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 단순 string을 잘 처리할 수 있느냐의 문제이다. terms를 빠르게 처리해 주기 위해 파이썬의 딕셔너리를 사용해서 각 term에 따른 개월수를 저장했다. 그 후 cal함수를 통해 term을 더해 주었다 여기서 term의 범위는 100 이하 이므로 month가 12 이하가 될 때까지 year을 더해주는 작업이 필요하다. 그 후 보관기간이 지났는지를 판단하기 위해 strin..

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 방법 풀지 못하여 다른 분들의 풀이를 참고했다. 다익스트라를 변형한 문제였다. 이 문제의 핵심은 편도만 경로만 구하면 되는 것이다. 또 다익스트라를 적용하여 값들을 업데이트할 때 max(이전 노드의 값, 이전 노드와 현재 노드의 가중치)를 사용해야 한다. import heapq def solution(n, paths, gates, summits): graph = [[] for _ ..

출처 : https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 풀이 방법 투 포인터 문제를 연습할 겸 문제를 풀어 보았다. 이중 for문으로 풀면 시간초과가 난다. 투 포인터란 배열을 순회하는 하나의 방법으로 포인터를 2개를 사용해서 순회하는 방법이다. 왼쪽 포인터와 오른쪽 포인터를 두고 풀어보자 왼쪽 포인터부터 오른쪽 포인터까지 합을 리턴하는 함수를 작성한다. 이때 배열의 합에 따라 케이스를 분리하자 배열의..