[백준/C++] 18115번: 카드 놓기(S3) 문제 https://www.acmicpc.net/problem/18115 18115번: 카드 놓기 수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다. 제일 위의 카드 1장을 바닥에 내려놓는다. www.acmicpc.net 사용한 알고리즘 2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱) -> 덱 풀이 위에서도 버리고 아래에서도 버릴 수 있는 자료구조인 덱을 사용해야 한다. 기술들을 뒤에서부터 보면서 역연산을 수행하며 1~N을 덱에 담으면 카드의 처음 상태를 알 수 있다. 기술들을 벡터 v에 입력받고 거꾸로 뒤집어준다.(reverse) 벡터 v를 순회하.. 2022. 1. 27. [백준/C++] 1863번: 스카이라인 쉬운거(G5) 문제 https://www.acmicpc.net/problem/1863 1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1 ≤ x ≤ 1,000,000. 0 ≤ y ≤ 500,000) 첫 www.acmicpc.net 사용한 알고리즘 2022.01.27 - [PS/Algorithm] - [알고리즘 개념정리] 5. 선형 자료구조(스택,큐,덱) -> 스택 2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디 풀이 스카이라인의 고도가 바뀌는 지점의 y좌표에만 관심을 가지면 된다. y좌표가 이전보다 작아질 때마다 건물 개수를 .. 2022. 1. 27. [백준/C++] 5052번: 전화번호 목록(G4) 문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 사용한 알고리즘 2022.01.16 - [PS/Algorithm] - [알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)+기초지식 풀이 각 테스트케이스마다 전화번호들을 벡터v에 담아준다. 벡터 v를 오름차순 정렬한다. (길이가 짧은 번호가 앞쪽에 오도록) 각 전화번호마다 hash값을 구해준다. hash[i][j]는 i번째 전화번호의 j번째 .. 2022. 1. 24. [백준/C++] 23559번: 밥(G5) 문제 https://www.acmicpc.net/problem/23559 23559번: 밥 제주대 학생회관 식당에는 두 개의 메뉴가 있다. 코너 A로 가면 5,000원짜리 메뉴를 먹을 수 있고, 코너 B로 가면 1,000원짜리 메뉴를 먹을 수 있다. 준원이는 대면 수업이 시작되는 바람에 이제 남 www.acmicpc.net 사용한 알고리즘 2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디 풀이 어차피 1000원 짜리는 늘 먹을 수 있으므로 5000원 짜리가 1000원 짜리보다 맛 수치가 높으며(a-b>0) 1000원 짜리와의 차이가 큰 것(gap으로 정렬)을 골라야 한다. 구조체 menu를 만들어 준다. a와 b에는 각각 5000원, 1000원 짜리 학식의 맛의 수치.. 2022. 1. 23. [백준/C++] 13305번: 주유소(S4) 문제 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 사용한 알고리즘 2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디 풀이 리터 당 가격이 가장 싼 주유소가 있는 도시에서 최대한 많은 기름을 넣는 게 이득이다. 따라서 임의의 (i-1)번 도시에서 i번 도시로 가는 기름은 1~(i-1)번 도시의 주유소들 중 가장 리터당 가격이 싼 주유소에서 넣고 오는 게 최적 전략이다. road[n-1]와 p.. 2022. 1. 23. [백준/C++] 9251번: LCS(G5) 문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 사용한 알고리즘 2022.01.19 - [PS/Algorithm] - [알고리즘 개념정리] 3. 동적계획법(DP) 풀이 두 문자열을 각각 s1, s2라고 하자. dp[i][j] 에는 s1의 i까지, s2의 j까지 문자들의 LCS길이를 담았다. dp A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C .. 2022. 1. 21. 이전 1 2 3 4 5 6 7 다음
