https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 1. Logic 중복을 포함하지 않는다고 했기 때문에 map대신 unordered_map을 사용했다. 그리고 입려이 50만이기 때문에 logN을 시간복잡도로 가지는 map에 비해 O(1)을 가지는 unordered_map을 사용하는게 좋을 것 이라고 생각했따. unordered_map의 key:학번 value:클릭한 순서 로 설정하고 입력은 받은 후 vector 로 설정하여 원소를 넣..
Algorithm/Beakjoon
https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 1. Logic 입력이 1000000이기 때문에 시간복잡도가 logN인 map을 사용해서 입력을 받았다. 2. Code #include using namespace std; map m; int n; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int ..
https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 1. Logic 물에 잠기지 않는 지점이 최대가 될 때를 구하는 문제이다. 처음에 이 문제를 봤을 때 그냥 주변높이 보다 높으면 안전지역인줄 알았는데 문제를 다시 읽어보니 0~최대 높이까지 확인하면서 그중에 가장 많은 안전지역의 갯수를 구하는 문제이다. 풀이 방법은 입력을 받으면서 최대 높이를 구하고 0~최대 높이 까지 BFS를 돌면서 최대 안전 지역의 갯수를 구하면 된다. 2. Code #include..
https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 1. Logic 1. pair를 원소로 가지는 stack 하나를 선언한다. pair는 이다. 2. 현재 입력받은 키보다 작은 애들은 무조건 볼 수 있기 때문에 pairCnt를 올려주고 어짜피 나보다 작은애들이기 때문에 나보다 큰 애가 들어오게 되면 내 뒤의 작은애는 보지 못하기때문에 스택에서 pop해주고 다시 넣어주지 않는다. > 이 방식으로 스택을 항상 내림차순으로 정렬해..
https://www.acmicpc.net/problem/1244 1244번: 스위치 켜고 끄기 첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 www.acmicpc.net 1. Logic 남학생은 배로수 바꿔주면 쉽지만 여학생이 문제이다. 여학생이 받은 번호 기준으로 왼쪽 오른쪽이 같으면 바꿔주고 다르면 바꿔주면 안된다. 그래서 while문의 조건을 swit[start] == swit[end]로 잡아줬다. 그리고 20개마다 줄 바꿔주는것을 잘 신경쓰면 된다! 2. Code #include using namespace std; int n, m; bool swit..
https://www.acmicpc.net/problem/25757 25757번: 임스와 함께하는 미니게임 첫 번째 줄에는 사람들이 임스와 같이 플레이하기를 신청한 횟수 $N$과 같이 플레이할 게임의 종류가 주어진다. $(1 \le N \le 100\,000)$ 두 번째 줄부터 $N$개의 줄에는 같이 플레이하고자 하는 사람들 www.acmicpc.net 1. Logic 임스와 lms는 다른 사람이라는거에 유의해서 입력을 받고 Map에 없으면 카운트해주고 있으면 넘어가준다. 코드를 보면 쉽게 이해가 갈 것이다. 2. Code #include using namespace std; map name; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cou..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1. Logic - check배열을 만들어서 리턴된 수는 생성자가 있는 숫자이기 때문에 체크를 해서 check배열이 true인 숫자들만 출력해주면 된다. 2. Code #include using namespace std; bool check[10001]; int cur(int num) { int sum = num; while(num != 0) { ..
https://www.acmicpc.net/problem/17484 17484번: 진우의 달 여행 (Small) 첫줄에 지구와 달 사이 공간을 나타내는 행렬의 크기를 나타내는 N, M (2≤ N, M ≤ 6)이 주어진다. 다음 N줄 동안 각 행렬의 원소 값이 주어진다. 각 행렬의 원소값은 100 이하의 자연수이다. www.acmicpc.net 1. Logic 브루트 포스로 풀 수 있지만 각 칸에서의 최솟값은 변하지 않기 때문에 그 값을 저장해 놓고 DP로 풀이할 수 있다. 2. Code #include using namespace std; int n, m; int space[10][10]; int dp[10][10][4]; //0:왼 1:dir 2:오 int solve(int y, int x, int p..
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 1. Logic 다리가 버틸 수 있는 무게가 10억까지이기 때문에 택배의 무게를 이분탐색으로 찾아준다. 이분탐색의 Check함수는 택배의 무게인 mid보다 각 경로가 버틸 수 있는 무게가 크거나 같을 때만 통과시켜 입력받은 출발지에서 시작하여 도착지에 도달할 수 있으면 택배의 무게를 늘리고 도착하지 못하면 택배의 무게를 줄이면서 적절한 택..
https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. Logic 자기 자신을 포함할 수는 없기 때문에 start와 end가 자신의 인덱스일때는 각각 ++, --를 해주고 투포인터로 탐색해주면 된다. 2. Code #include using namespace std; long long n; vector input; long long ans = 0; void solve(long long i) { long long start = 0; long long end = n-1; whi..
