N

문제 설명 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩 경기를 합니다. 각 경기당 A팀에서 한 사원이, B팀에서 한 사원이 나와 서로의 수를 공개합니다. 그때 숫자가 큰 쪽이 승리하게 되고, 승리한 사원이 속한 팀은 승점을 1점 얻게 됩니다. 만약 숫자가 같다면 누구도 승점을 얻지 않습니다. 전체 사원들은 우선 무작위로 자연수를 하나씩 부여받았습니다. 그다음 A팀은 빠르게 출전 순서를 정했고 자신들의 출전 순서를 B팀에게 공개해버렸습니다. B팀은 그것을 보고 자신들의 최종 승점을 가장 높이는 방법으로..

추석 트래픽 이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다. 입력 형식 solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다. 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss ..

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다. 제한사항 문자열 s의 길이 : 2,500 이하의 자연수 문자열 s는 알파벳 소문자로만 구성 입출력 예 s answer abcdcba 7 abacde 3 팰린드롬을 찾기 위해 s의 가운데부터 탐색을 시작한다. size = s의 길이, mid = s의 가운데를 나타낸다. 우선 size가 1 이하라면 size를 그대로 리턴해준다. while문을 통해 size가 0이 될 때까지 반복. 가장..

문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, ULURRDLLU로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9이지만, 캐..

vector answer에 n만큼의 공간을 0으로 할당해준다. 그리고 비어있는 tmp 벡터도 선언한다. 만약 s < n이라면 최고의 집합이 존재하지 않는 경우이므로 tmp에 -1을 넣어주고 리턴. for문을 통해 최고의 집합을 만들도록 한다. n ~ 1까지 반복하며, q = s / i를 하여 answer의 앞에서부터 차례대로 몫을 넣어준다. 그리고 s -= q를 하여 다음 수를 구할 수 있도록 한다. for문이 끝나고 마지막에는 s의 나머지 값을 넣어주고 리턴하면 된다. answer를 n개로 미리 할당하는 이유는 효율성 테스트때문이다. 동적할당이라서 push_back 할 때마다 시간초과가 일어나므로 미리 n개만큼 할당하여 시간을 줄였다. #include #include #include using name..

이분탐색을 통해 문제 해결. 처음에는 완전탐색으로 시도했지만 효율성 테스트를 통과하지 못하므로, 이분탐색으로 문제를 풀었다. front = 1, back = stones 배열에서의 max 값으로 초기화한다. front = k가 된다면 true를 리턴하여 back = mid - 1을 해주도록 한다. false가 반환되면 front = mid + 1. 결국 front가 징검다리를 건널 수 있는 친구의 수가 된다. #include #include #include using namespace std; bool bs(vector stones, int mid, int k) { int count = 0; for(int i = 0; i < stones.size(); i++) { if(stones[i] - mid = k..

DFS 문제. 전역변수로 bool형 visited[10001]을 선언하여 false로 초기화. 마찬가지로 vector answer, int max_count = 0으로 선언하여 사용하기 쉽게 만든다. 우선 sort를 수행한다. 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 선택하기 편하도록 하기 위함이다. 그리고 임시변수 tmp를 선언하고, dfs 함수에 전달. 처음에는 "ICN"에서 출발하기 때문에 dfs(tickets, tmp, "ICN", 0)으로 호출한다. dfs함수를 재귀적으로 호출. for문을 돌면서 start와 같으면서 방문하지 않았다면 visited[i] = true로 바꿔주고, dfs 함수에 다음 목적지를 전달하도록 해주면 알아서 재귀적으로 답을 찾아준다. #include ..

1번 기지국부터 n번 기지국까지 검사를 한다. start는 현재 위치한 기지국 번호, index는 stations의 인덱스를 나타내는 변수다. while문을 통해 start ~ n까지 반복하도록 한다. 만약 stations[index] - w