boj, 백준) 13344. Chess Tournament (C/C++)
1. 문제 링크 www.acmicpc.net/problem/13344 13344번: Chess Tournament Your friend is an organizer of the International Chess Playing Championship. He is worried that some of the contestants may be cheating, and he has asked you to help out. The chess players are allowed to report matches to the jury themselves, and this is www.acmicpc.net 2. 문제 개요 체스 대회에서 출전자들이 심판을 본다. 그런데 이게 출전자들이 심판을 보다 보니 진짜인지 가짜인지..
boj, 백준) 2252. 줄 세우기 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 2. 문제 개요 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 했다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 3. 문제 힌트 위상 정렬을 사용해보자. 4. 문제 풀이 문제를 푼 사람도 많고, 정답률도 높..
[C++/STL] Map 분석
가끔 꼭 필요한 Map 컨테이너에 대해서 알아보겠습니다. Map에 대한 정보는 C++ Reference를 참고했습니다. www.cplusplus.com/reference/map/map/?kw=map map - C++ Reference difference_typea signed integral type, identical to: iterator_traits ::difference_type usually the same as ptrdiff_t www.cplusplus.com 1. Map의 특성 Map은 Key와 Value의 쌍을 특별한 순서로 저장하고 있는 연관 컨테이너(associative container)입니다. 이진 트리로 구현되어있고, Key를 통해 Value에 접근하고자 할 때, [] 연산자를 사..
boj, 백준) 14725. 개미굴 ( C++ )
1. 문제 링크 www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 2. 문제 개요 개미 로봇이 개미굴을 탐사하면서 보내온 신호를 토대로 개미굴의 구조를 파악하는 프로그램을 작성하기. (문제가 복잡해서 링크를 타고 들어가서 읽어보는 걸 추천합니다.) 3. 문제 힌트 트라이를 구현해보자.(트라이에 대한 기본 지식이 있어야 함) 그리고, 자식노드를 만들 텐데 정렬을 편하게 하기 위해 map을 사용해보자. 4. 문제 풀이 이 문제는 알고리즘 뿐만아니라 ..
boj, 백준)16946. 벽 부수고 이동하기 4 ( C / C++ )
1. 문제 링크 www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 2. 문제 개요 N x M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 변을 공유할 때, 인접하다고 한다. 각각의 벽에 대해서 다음을 구해보려고 하는데, - 벽을 부수고 이동할 수 있는 곳으로 변경 한다. - 그 위치에서 이동할..
boj, 백준) 17387. 선분 교차2 ( C/C++ )
1. 문제 링크 www.acmicpc.net/problem/17387 17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 2. 문제 개요 2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있으면 교차하는 것이다. 3. 문제 힌트 여러 가지 예외 케이스들을 생각해보자. 가장 기본적인, 두 선분이 교차하는 것에서 시작해서.. 이런 다양한 경우가 있을 수 있다. 어떻게 예외를 처리해야 할까 4. 문제 풀이 많은 예외처리를 다룬 선분 교차 알고리즘을 다른 블로그에서도 많이 올려놓아서 자..