본문 바로가기

ALGORITHM

 (71)
14621 나만 안되는 연애 www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 최소 스패닝 트리(MST) 에서 남고-여고 조건이 추가된 문제 #include #include #include #include #include #include using namespace std; typedef pair pipii; int N, M, u, v, d, length = 0; bool check; int parent[1001]; char school[1001]..
12789 도키도키 간식드리미 https://www.acmicpc.net/problem/12789 12789번: 도키도키 간식드리미 인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두 www.acmicpc.net 한 명씩만 설 수 있는 공간이 매우 스택을 쓰고싶게 생겨서 오랜만에 스택을 써서 구현 #include #include #include using namespace std; vector student; stack temp; int main() { int N, input, out = 1, i = 0; cin >> N; for (int i = 0; i > input; s..
12781 PIZZA ALVOLOC https://www.acmicpc.net/problem/12781 12781번: PIZZA ALVOLOC 입력의 첫 줄에는 도윤이와 친구들이 선택한 점의 좌표 x, y(-10,000 ≤ x, y ≤ 10,000)가 순서대로 4개 주어진다. x, y값은 항상 정수이다. www.acmicpc.net 단순하게 수학처럼 선의 방정식을 구해서 교점을 찾으려고 했지만, 교점이 그 도형 안에 존재하는지에 대한 확신을 구하기에는 너무 복잡해서 다른 식으로 접근해야 했다._. https://www.acmicpc.net/blog/view/27 점 3개의 방향성을 나타내는 CCW 세 점 P1(x1, y1), P2(x2, y2), P3(x3, y3)가 있을 떄, 점 3개를 이은 선분은 어떤 방향성을 나타내게 될까요? 117..
11585 속타는 저녁 메뉴 https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net KMP 알고리즘 문제 처음에 한칸한칸 모두 확인하니 75% 쯤에서 시간초과 발생 알고리즘 시간에 배운 KMP 알고리즘으로 해결해야 O(N+M) 시간으로 시간초과가 발생하지 않는다. 분명 머리로는 이해하고 납득했는데 코드가 이해가 안가서 한참 생각한 문제._. 푸는 방법을 글로 써내려가면, 환형 문자열의 문제들은 문자열을 두배해서 문제를 푸는 것이 일반적이라고 한다. 'I W A N T M E ..
11578 팀원 모집 https://www.acmicpc.net/problem/11578 11578번: 팀원 모집 3번 학생과 4번 학생을 선택하면 1번부터 5번까지 모든 문제를 풀 수 있는 팀을 만들 수 있다. 1번, 2번, 4번 학생을 선택해도 모든 문제를 다 풀 수 있지만 팀원의 수가 3명이라 답이 될 수 없다. www.acmicpc.net 백트래킹은 아니고 브루트 포스 문제 같다. 전체 경우의 수를 다 해봐야 하니 DFS로 전체 탐색 #include #include #include #include #include using namespace std; #define initialize(x, y) memset(x, y, sizeof(x)); int N, M, cnt, min_cnt; int std_solve[11][11]..
11582 치킨 TOP N https://www.acmicpc.net/problem/11582 11582번: 치킨 TOP N 인하대 주변 치킨칩의 맛의 정도를 측정해 수치화하는 동아리 C.T.P(Chicken Tastes Perfect)의 회장 민호는 치킨집의 맛의 수치를 감소하지 않는 순으로 정렬을 하고 싶었다. 하지만 치킨집이 너무 많 www.acmicpc.net 쉬운 문제인데 기본적인 sort 함수 범위에서 막혀서 당황했던 문제 일반적으로 vector에서 sort함수를 사용할 때 , sort(v.begin(), v.end()); 이렇게만 사용했더니 범위에 대한 것은 생각지도 않고있었다. https://www.cplusplus.com/reference/algorithm/sort/?kw=sort sort - C++ Referen..
11581 구호물자 https://www.acmicpc.net/problem/11581 11581번: 구호물자 서기 2050년 엄청나게 강력한 폭풍이 인천을 강타했다. 강력한 폭풍의 영향으로 모든 사람은 대피소로 대피하였으며, 많은 도로가 유실되었다. 그나마 남아있는 도로도 모든 표지판과 가로등이 www.acmicpc.net 구현방법: DFS (재귀함수) dfs 함수 안에 도착점(N)에 도착하면 return 하는 조건을 넣었을 때 75% 까지만 완료되고 '틀렸습니다'가 반복됐는데, 딱 cycle이 발생하는지 아닌지만 확인하려고 이 조건을 지우니 맞았다. 아무튼 cycle이 존재하는지 확인하는 문제 memset은 cstring 헤더가 필요하다는 것도 다시 알게 된 사실 초기화 부분은 안 써도 되지만 새로운 걸 알게 돼서 써봤..

티스토리툴바