https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net #문제 간단 정리 일단 배낭문제이다. 기존의 가방문제는 최소 무게를써서 최대 가치를 찾고 최대 가치를 가진 마지막 dp 배열이 정답이였다면 이 문제는 최소 비용으로 최대메모리를 찾고 그중에서 그 메모리이상의 첫번쨰 dp 배열을 찾는다는게 차이점 #문제 해결 방법 DP 배열을 dp[i][j]로 정의하고, 이를 "처음부터 i번째 앱까지 고려했을 때, 비활성화의 총 비용이 j일 때 확보할 수 있는 메모리의 최..
https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net #문제 간단 정리 dfs 혹은 bfs를 사용하자 #문제 해결 방법 dfs를 사용해서 depth를 반환하도록 해줬다. 근데 만들고 나니 result = min(result, curResult); 로 최소 거리를 확인해 줘야 되서 bfs 로 풀면 더 쉽게 풀거라는 생각이 들었따. #전체 코드 dfs 코드 #include #include #include #include using n..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net #문제 간단 정리 이전의 두 용액 문제와 같이 두 포인터를 사용한 문제 #문제 해결 방법 이전의 두 용액에서와는 달리 첫번째 용액을 고르고 두번째와 세번째를 두 포인터로 좌 우를 조절하며 가장 0과 가까운 용액을 찾는다. 그리고.. 그냥 첫번째와 두번째 용액을 브루트 포스로 전부 탐색하고 세번 째 용액을 이진탐색으로 고르는 방법이 있다. 이게 좀 더 복잡하다. #전체 코드 1..
https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net #문제 간단 정리 투 포인터를 활용하는 문제 많이 볼 수 있는 유형이라 많이 접근해봤다면 쉽게 풀 수 있다 #문제 해결 방법 우선 브루트 포스를 사용하면 시간 초과가 날 것이 자명하기 때문에 값보다 작다면 end포인터를 ++ 하면서 길이를 늘리고 값보다 크다면 start 포인터를 -- 하면서 최소 길이를 확인합니다. 이는 가장 '짧은' 연속 부분합 길이를 찾는다고 문제에 나와있기 때..
https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net #문제 간단 정리 사이클이 언제 생성되는지 출력하는 문제 즉 사이클을 확인할 수 있는 유니온 파인드 (Union-Find)를 알고 있는지 물어보는 문제다 그렇기 때문에 유니온 파인드를 구현하자 #문제 해결 방법 유니온 파인드 동작 방식 유니온 파인드에서는 각 노드가 하나의 그룹을 나타내고, 각 그룹은 트리 구조로 구성됩니다. 트리의 루트 노드는 그 그룹을 대표합니다. 초기 상태에서는 각 노드..
https://www.acmicpc.net/problem/2550 2550번: 전구 N개의 스위치와 N개의 전구를 가진 하나의 스위칭 박스가 있다. 이 박스의 왼편에는 스위치가 있고, 오른편에는 전구가 달려있다. 모든 스위치와 전구들은 1에서부터 N까지의 번호를 가지며 같은 www.acmicpc.net #문제 간단 정리 #문제 해결 방법 1. 문제 이해하기 스위치와 전구가 있고, 각 스위치는 특정 전구를 켭니다. 스위치들을 함께 누르면, 그들의 연결선이 교차하지 않는 경우에만 전구들이 켜집니다. 우리의 목표는 최대한 많은 전구를 켜는 것입니다. 여기서 우리는 스위치의 순서대로 전구를 순서대로 나열했을때 가장 긴 증가는 부분수열을 구하면 가장 많이 킬 수 있는 전구의 개수를 알 수 있다는걸 파악 할 수 있..
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net #문제 간단 정리 최소 스패닝 트리를 구현하는되는 문제 즉 크루스칼 알고리즘이랑 프림 알고리즘을 구현하면 되는 문제이다 https://yabmoons.tistory.com/191 [ 백준 1197 ] 최소 스패닝 트리 (C++) 백준의 최소스패닝트리(1197) 문제이다.[ 문제 바로가기 ] [ 문제 풀이]1) 이 문제는 Minimal Spanning ..
https://www.acmicpc.net/problem/16139 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net #문제 해결 방법 우선 시간제한을 확인했을때 매번 매 쿼리마다 구간을 전부 확인하면 시간초과가 난다. 알파벳이 나오는 순서가 고정되어있기 때문에 나는 문자열의 길이와 알파벳의 개수만큼의 크기를 가지는 2차원 배열을 선언해서 예 : [string.size()][26] 문자열의 알파벳 인덱스에 해당하는 열에 카운팅을 해줫다. [index][알파벳-'a..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net #문제 간단 정리 #문제 해결 방법 그래프를 이용한 탐색 구현 문제이다. 주요 로직은 양배추가 있는 x y 좌표들만 따로 저장해서 양배추들 좌표들만 따로 순회를 해주는데 만약 이전에 접근한 적이 없다면 counting 전역변수로 새로운 진입을 카운팅 해준다. 여러모로 전역변수를 쓰면 편하다 #전체 코드 #include #include using namespace std; int M, N, K; int coun..
https://www.acmicpc.net/problem/2615 2615번: 오목 오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호 www.acmicpc.net #문제 간단 정리 #문제 해결 방법 가장 주의해야될 점이 연속된5개의 돌을 확인해서 승리로 판단할 수 있지만, 만약 뒤쪽 방향도 확인하지 않는다면 육목임에도 중간부터 확인해서 오목으로 오판해서 승리로 간주할 수 있다. 때문에 뒤쪽도 확인한 뒤에 뒤의 인덱스로 업데이트 하는 기능을 신경 써 줘야 한다 #전체 코드 #include #include using namespace std; const int..