알고리즘/백준 (263) 썸네일형 리스트형 [백준] 2473번 : 세 용액 🤔 문제분석📝 문제요약3개이상의 용액이 주어졌을때 3개를 뽑아서 합이 0에 가장 가까운 용액을 찾는 문제이다.🎯 필요한 개념투포인터✅ 알고리즘용액을 오름차순으로 정렬한다.2중 for문으로 2가지의 용액을 뽑는다.남은 하나의 용액을 투포인터를 활용하여 찾는다.합이 0보다 작은경우 Left를 증가 시킨다.합이 0보다 큰경우 Right를 증가 시킨다.모든 경우를 탐색하면서 가장 0에 가까운 용액을 찾아서 오름차순 정렬하여 리턴한다.💻 코드#include #include #include #include using namespace std;int main() { int N; cin >> N; vector A(N); for (int i = 0; i > A[i]; } sort(.. [백준] 1208번 : 부분수열의 합2 🤔 문제분석📝 문제요약N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하시오.🎯 필요한 개념이분탐색해시맵✅ 알고리즘N의 범위가 40이하라서 완전탐색을 할경우 2^40 의 경우의 수를 모두 탐색해야한다. 왼쪽, 오른쪽을 반으로 나누어서 각각 탐색을 수행한다면 주어진 시간안에 문제를 해결 할 수 있다.해시맵을 사용하여 right, left를 각각 나누어서 자기자신을 포함한경우 포함하지 않은 경우 모두를 탐색한다.오른쪽을 완전탐색한다.종료조건에는 그동안 누적한 cnt에 대해서 경우의 수를 추가한다.자기자신을 포함한경우와 포함하지않은경우 두가지에 대해서 탐색한다.왼쪽을 완전탐색한다.종료조건에는 오른쪽에서 갱신한 해시맵을 현재 .. [백준] 1561번 : 놀이공원 🤔 문제분석📝 문제요약아이들(N)과 놀이기구(M)가 주어지고, 각 놀이기구는 한명만 탈 수 있고 운행시간이 주어졌을때 아이들이 순차로 놀이기구를 탄다고 한다면 마지막 아이가 탄 놀이기구의 번호를 구하는 문제이다.🎯 필요한 개념이분탐색✅ 알고리즘아이들을 태울 수 있는 최소 시간을 구한다. ( 이분탐색 )놀이기구를 순회하면서 아이들을 태울 수 있는 카운트를 한다.시간 / 놀이기구[i]아이들을 태울 수 없다면 시간을 줄여본다.아이들을 태울 수 있다면 시간을 늘려본다.해당 시간에 모두 태일 수 있는 아이들을 뺀다.N -= child_cnt다음시간에 놀이기구를 탈 수 있는 경우라면 태우고 그렇지 않으면 태우지 않는다.다음시간 % 놀이기구[i] == 0 인경우 태울 수 있다.그렇지 않은 경우는 태울 수 없는 .. [백준] 2352번 : 반도체 설계 🤔 문제분석📝 문제요약n개의 포트를 연결 할때 겹치지 않는 상태로 연결해야한다.겹치지 않는 상태로 연결을 하기 위해서는 오른쪽의 포트가 오름차순으로 정렬 되어있어야한다. 따라서 증가하는 가장 긴 부분수열을 찾으면 문제는 해결 된다.🎯 필요한 개념이분탐색증가하는 가장 긴 부분수열✅ 알고리즘하나씩 입력받는다.입력받은 데이터에 현재 수열중 가장 작은 인덱스를 찾아낸다.만약 인덱스가 없다면 수열에 추가한다.인덱스가 존재한다면 해당 인덱스의 값을 입력받은 데이터로 치환한다.부분수열의 길이를 출력한다.💻 코드#include #include #include using namespace std;int n;vector ls;int bisect(const int v){ int start = 0; int .. [백준] 9370번 : 미확인 도착지 9370번: 미확인 도착지 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 🤔 문제분석 s에서 e로 갈때 g, h를 방문했는지 여부를 확인하는 문제로 데이크스트라를 s에서 시작, g에서 시작, h에서 시작하여 각각의 거리를 측정한뒤 아래의 조건을 만족하면 s 에서 e로 갈때 g, h를 방문했는지 확인 할 수 있다. d_s[g] + d_g[h] + d_h[e] == d_s[e] 일때 d_s[h] + d_h[g] + d_g[e] == d_s[e] 일때 💻 코드 import sys import heapq in.. [백준] 14442번 : 벽 부수고 이동하기 2 14442번: 벽 부수고 이동하기 2 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 🤔 문제분석 너비우선탐색으로 해결 할 수 있는데 벽을 부순 횟수를 방문배열에 따로 추가하여 해결하였습니다. 벽을 부수고 먼저 이동한 것들이 끝까지 도달하지 못하고 미리 방문배열을 초기화 하였다면 벽을 부수지 않고 온 것이 끝까지 도달하지 못하는 상황이 발생하여 벽을 부순 횟수를 3차원에 추가를하여 벽을 부순횟수도 체크를 해주어야한다. 💻 코드 import sys from collections.. [백준] 14938번 : 서강 그라운드 14938번: 서강그라운드 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 🤔 문제분석 플로이드 워셜, 데이크스트라를 떠올리면 된다. 플로이드워셜 플로이드 워셜로 모든 노드까지의 모든 최단경로를 구한뒤, i번노드에서 다른노드까지 거리가 m이하인 경우만 아이템을 획득하게 만들면 된다. 데이크스트라 i번 노드에서 다른노드까지의 최단 거리를 구한뒤 ( 데이크스트라 ) 모든 거리가 m 이하인 경우만 아이템을 획득 할 수 있으므로 m이하인 거리만 item을 획득하게 하면된다. 💻 코드 플로이드워셜 import sys inpu.. [백준] 2668번 : 숫자고르기 2668번: 숫자고르기 2668번: 숫자고르기 세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절 www.acmicpc.net 🤔 문제분석 깊이 우선탐색으로 아래 숫자를 뽑아서 그 숫자로 이동하면서, 위쪽 집합과 아래쪽 집합이 동일할 경우 정답 리스트에 값을 추가시켜줍니다. 위쪽 집합과 아래쪽 집합이 같다는건 결국 집합을 만들 수 있다는 조건을 만족시키기 때문입니다. 💻 코드 import sys input = sys.stdin.readline N = int(input()) nums = [int(input()) for _ in range(N)] def .. 이전 1 2 3 4 ··· 33 다음