2017년 10월 14일 토요일

카카오 블라인드 채용 테스트 후기 (2차)


예상치도 못하게, 2차 테스트는 RESTful API + json 조합이 나왔다. 내용은 이렇다.
카카오에서 API 서버를 제공하는 데, API 호출 횟수가 50번/초로 제한된 상황에서 10분동안 얼마나 정확하고 많은 처리를 응답할 수 있느냐였다.

node.js 로 할까하다가 문제풀이에 더 초점이 맞춰진 형태면 어떡하지싶어서 C++로 준비했었는데, 생각보다 그렇진 않았다.

테스트는 오후 2시부터 10시까지 8시간동안 진행됐고, 난 최종 32000점으로 광탈예상이다. (참고로 1등은 23만점정도)
오후 5시 좀 넘어갈때는 2만점 조금 넘겨도 50등이길래 좋았는데, 후에 파이썬이나 다른 언어로 REST API 공부를 마친 사람들이 있었는지, 평균 점수들이 쭉쭉 오르더라.

테스트가 끝나고나니 결과가 좀 이해되는데, 나는 그냥 게시글마다 전부 next_url이 있어서 그거 타고 쭉 가면 되는줄 알았더니 그게 아니었나보다. 아직 next_url이 없을수도 있고 자신과 같을 수 있는데, 그때 재요청을 하면 된다고한다. 어쩐지 계속 다른 사람보다 처리량이 낮더라했다.

정직하게 구현했다면 10만점정도는 나왔다는 것 같고, 쓰레드로 어떻게 잘 비벼보거나 조건들 잘 읽으면 파훼법이 나오는 듯.

람다식 처음 써봐서 이게 뭐지 찾느라 시간 다 보냈다. 비동기랑 동기 같이 쓰다가 피보고, 처리속도가 너무 느려서 중간에 쓰레드 쓰려고 삽질하고 별짓 다한거같다. 여튼 진짜 문제는 그게 아닌거같았고... 재요청해야되는거 몰라서 끝까지 쉐도우복싱만 하다 끝났다.

테스트 방식이 특이했지만 재밌긴했다. 근데 그때도 C++로 할지는 의문.

17.10.20 수정
2차 합격 커트라인은 80000점이라는 공지가 떴다.

2017년 9월 17일 일요일

카카오 블라인드 채용 테스트 후기 (1차)


2018 카카오 블라인트 채용 테스트 1차에 참가했다.

요즘엔 기업들이 programmers.co.kr 같은 플랫폼을 사용하여 대회 또는 시험을 진행하는 같다. 제출이나 문제 설명은 codecademy 와 비슷한 방식이고, 문제를 제출하고 검사하는 방식은 TopCoder와 유사하게 class 나 어떤 함수의 반환으로 채점한다.

1차 온라인 테스트는 https://programmers.co.kr/competitions/35/welcome-kakao 또는 https://welcomekakao.com 에서 진행되었다.

5시간동안 총 7문제가 주어졌었는데, 문제는 난이도순이 아닌 것 같았다.

1,2,3,6,7,5번 순서대로 풀었었고, 4번은 읽고 나니 테스트 종료 15분 정도 남았었다. 제출하기 전에 테스트케이스를 돌렸는 데 몇 개가 틀렸다. 디버깅 할 시간도 없고 해서 제출하지 않았다.

7번에서 시간을 너무 보내버린 나머지 시간이 부족했다. 문제 조건을 자세히 읽다보니 고려해도 되지 않은 부분이 있었는 데, 그걸 너무 늦게 알아서 늦었다.. 다음부터는 꼭 문제 조건을 침착하게 읽어야겠다.

정확히는 기억이 안 나는데, 1번 문제는 비트의 모양을 한 문자열->숫자를 반대로 디코딩하는 거였고, 2번은 점수에 대한 정보가 담긴 문자열을 뜯어 점수를 계산하는 구현 문제였다.
3번은 LRU를 시뮬레이션 하는 거였는데, 제출했더니 부분 문제에서 우수수 틀렸다. map을 써서 cache hit 타이밍을 업데이트하고 그랬는 데, 왜 틀렸는 지 모르겠다. 나중에 풀이를 공개해주면 좋겠다.
4번은 셔틀 버스 9시부터 t분마다 총 n회 운행하고 한 번에 최대 m명만 탈 수 있을 때, 최대한 늦장부리면 몇시 몇분 버스를 타느냐였는데, 나중에 꼭 풀어보고싶다.
5번은 두 집합에 대해 A∩B / A∪B 를 구하는 거였는 데 이것도 map 쓰면 된다.
6번은 연세대 대회 중에 뿌요뿌요랑 비슷했다. 대신 dfs를 안 쓰는 방식
7번에서 좀 고생했는데, ISO 형태 비슷하게 ms초까지 적힌 문자열을 뜯어서 정해진 범위 내에서 겹치는 구간의 개수를 구하는 문제였다. 구간을 Open/Close하면서 범위 내의 구간의 개수를 구했는 데, Codeforces Round 422-C 에서 사용해봤던 방법이었다. (같은 문제는 아니다.) 시간복잡도는 대략 O(nlogn)

전체적으로 문제가 "엥 이거 완전 억지 아닌가"라는 느낌은 없었다. 다만, 프로그래머스 사이트 자체의 특성인건지 입력과 출력의 범위가 제대로 주어지지 않는 경우가 몇 있어서, 최소/최대 케이스를 테스트하기가 어렵다. main() 함수를 따로 구현해서 테스트 하는것도 일이다..

PS) ACM을 앞두고 너무 실력이 부족한 것 같아 걱정이다. 새로운 알고리즘을 배우기엔 늦었고, 기존의 발상과 구현 능력을 다듬어야 할 때 같다.

17.09.28
몇일 전에 메일이 도착했다. 우선은 합격했는데 컷이 4문제였다고 한다. 그리고 카카오에서 풀이를 공개하였다. 글은 http://tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1 에서 확인할 수 있다.

2017년 8월 31일 목요일

삼성 대학생 우수 프로그래머 캠프 후기

8/24(목)~25(금) 동안 진행된 삼성 대학생 우수 프로그래머 캠프를 다녀왔다.
캠프 참가 여부를 물어보는 별도의 메일이 왔었고, 대상은 역량테스트 pro 통과자 또는 타 대회 입상자들이라고 하더라.
좋은 기회인 것 같아서 큰 고민없이 일찍 신청했다.

후기를 어디까지 자세히 적어야할지 모르겠어서, 그냥 의식의 흐름대로 적어볼까 한다. 전반적으로 장소의 이동이 잦았고, 회사의 분위기 설명이나 회사 소개를 자주 들었다. 그리고 밥은 아쉽지 않을 만큼 맛있었다.

양재역에서 모여서 출발하는지라, 전주에서 출발하긴 꽤 먼 거리였기에 출발 시간을 정하기 애매했다. 같이 가는 친구랑 끝까지 고민하다가 친구는 24일 아침, 나는 23일 저녁에 출발하기로 했다.

24일 11시에 양재역 앞에서 버스가 기다리고 있었다. 50인승정도 되는 큰 버스였다. 버스에서 하스스톤 몇 판 하다보니 서울 R&D 캠퍼스에 도착했다. 그룹으로 나누어서 실제 근무하시는 분들과 점심 식사를 함께 하면서 얘기를 나눌 수 있는 시간을 줬는 데, 꽤 많은 궁금증을 풀어낼 수 있었던 좋은 시간이었다.
내가 있었던 그룹의 개발자분은 클라우드쪽 업무를 하고 계셨는 데, 연구실과 관련한 질문을 좀 많이 했다. 사실 지금 연구실의 주제가 취업 이후에 어떤 가치가 있을 지, 현업에서 어느 정도의 개발이 이루어지는 지 궁금했었다. 생각 이상으로 주제가 밀접한 관계가 있었고 간단한 조언이나 경험을 들을 수 있어서 좋았다.

점심 먹고는 강당에 모여서 세미나 같은 걸 여러 개 들었다. 삼성 내에서 진행하는 C-Lab의 소개부터, 애자일 프로세스와 개발 문화 정도였다. (C-Lab은 사내에서 spin-off로 창업할 수 있는 사내 벤쳐 프로그램)
사실 이런 내용은 요즘의 스타트업(또는 실리콘 밸리)에서 많이 사용하고 있다고 알고 있었는데, 삼성에서 적용하고 있을 줄은 몰랐다. 완성된 큰 기업이라는 이미지때문이었을까, 변화가 심한 이런 프로세스를 차용하지 않을 줄 알았는데, 꽤나 적극적이었다.

우면동 R&D 캠퍼스에서는 이정도로 끝났고, 저녁 식사와 이후 일정을 위해 수원 인재개발원으로 이동했다.

저녁 식사때는 각 부서의 인사팀 분들이 나오셔서 여러 이야기를 물어볼 수 있었다. 물론 면접때 점수를 더 받고 그런 이점은 전혀 없는 부분이고, QnA를 직접 물어보는 정도의 편함이랄까.

저녁 이후엔 미니 컨테스트를 했는데, 난이도순으로 A/B/C라 하자면, A는 백트래킹, B는 dp, C는 최적화문제였던것같다. 메모리나 시간제한도 꽤나 넉넉하게 줬었다. (시상식은 다음 날 있었음) 컨테스트가 끝나고 야식으로 치킨/피자를 주더라. 컨테스트 도중에도 과자를 주셨는데.... 약간 하루종일 계속 먹임당하는 느낌이었다. (나쁜건 아니라고 본다)

밤에 잠이 안와서 새벽 5시쯤 잤다.

25일 아침에는 pichulia님이 C형 문제 풀이해주셨는데 내용도 좋고 발표를 재밌게 잘 하신다. 점심에는 수원 Digital City에서 다른 개발자분(expert 통과자)이랑 점심을 먹었는데 좋은 얘기를 많이 나눴다. 원래 PS를 하시던 분이 아니라는 것에 조금 놀랐다. 근데 원래 개발을 진짜 잘 하시던 분인듯.
지금 삼성에서 어떤 기술을 개발하는 지? 이 부서에선 뭘한다 정도? 들려줬고 S/I/M 이라고 삼성 박물관을 갔는데 퍄- 진짜 박물관이었다. 삼성의 역사를 왜 알아야하나하면서 들어갔는데 나올땐 엄마나여기입사할래엉엉 정도.

생각보다 자세하게 적은 것 같다.
정리를 좀 하자면 삼성은 기존의 규모와 수준을 유지하면서, 스타트업의 성격들을 받아들이고 있었다는 점.
스타트업에서 닉네임을 부르듯, 삼성도 호칭을 생략하고 ~님으로 부르고 있다. (위에서 내려온 지침이라고 함)
자율출퇴근제는 귀에 딱지가 생기게 들었다. 어찌됐건 주 40시간만 채우면 된다인데, 다들 여유롭게 오전 10~11시쯤 출근하시는듯. 이거 진짜 좋아보인다. 옷차림도 자유다.
사실 난 장래희망이 "넥타이를 메지 않는 직업"일 정도로, 분위기를 많이 생각하고 취직을 고려해서 삼성은 죽어도 안갈래 라는 생각이 컸는데, 최근에 점점 바뀌다가 이번 기회에 직접 견학(?)을 다녀오니 생각이 정말 많이 바뀌었다.

가장 도움이 된 건, 지금 일하시는 분들과 이야기를 나눌 수 있었고. 비슷한 공부를 하는 사람들을 알아갈 수 있었다는 점, 회사가 돌아가는 것을 눈으로 직접 보고 느꼈다는 점 정도일 것 같다.

진짜 열심히 공부해야지라는 생각이 머리 끝까지 차올랐다. 의욕이 마구마구 생기는 보람찬 시간이었다!

2017년 7월 2일 일요일

Visual Studio에서 C++ 컴파일 에러가 나시나요?

이 내용은 Beakjoon Online Judge, Algospot 등의 온라인 저지를 사용하시는 분들에게 도움이 될 내용입니다.

최근들어 컴파일에러로 오답을 받고 질문을 올리시는 분이 자주 보이는 것 같습니다.
주로 그 내용은 "비주얼 스튜디오에서는 되는 데 백준에서는 오류가 나네요" 등이더군요.
컴파일 에러를 해결하시는 데에 도움이 될 만한 글을 남기고자 합니다.

비쥬얼 스튜디오에서는 되는 데..

비쥬얼 스튜디오는 생각 이상으로 강력한 통합 개발 환경(IDE)을 제공합니다. 아래 코드는 컴파일 에러일까요?
#include <iostream>
int main() {
    printf("%d", strlen("123"));
    return 0;
}
위 코드는 컴파일 에러가 맞습니다. strlen 함수는 cstring 또는 string.h 헤더에 포함되어있기 때문이죠.
하지만 놀랍게도 비쥬얼 스튜디오 2017에서는 정상적으로 실행됩니다. (다른 버전은 테스트 후 추가하겠습니다)
자세한 이유는 여기를 참고하시면 좋을 것 같습니다.
요약하자면 "컴파일러가 다르기 때문"입니다. 비쥬얼 스튜디오는 VS C++ compiler를, 채점은 GCC compiler를 사용합니다.
(정확히는 컴파일러때문이 아니라, 비쥬얼 스튜디오에서는 의존성을 보고 헤더를 자동으로 추가해주기 때문이라고 생각하고 있습니다.)

그럼 제출해야만 에러를 알 수 있나요?

아닙니다. 채점 도움말을 보시면 채점 환경과 컴파일 옵션을 확인할 수 있습니다. 이와 비슷한 환경에서 실행하시면 채점할 때 어떤 오류가 나올 지 미리 확인할 수 있습니다.
C++의 경우 Ubuntu 16.04.1 LTS 64-bit에서 g++ Main.cc -o Main -O2 -Wall -lm로 컴파일 하는군요. O2 최적화, 경고 무시, 수학라이브러리를 포함하고 있음을 알 수 있습니다.

에러를 해결하는 방법

0. GCC Compiler를 사용한다.

여기에는 여러 방법이 있습니다만, 크게 2가지가 있습니다. 직접 설치하거나, 설치된 환경에서 실행하는 것입니다.
Windows 환경에서 완전히 동일하진 못해도 컴파일 채점환경과 비슷하게 실행하는 방법이 있습니다.
  1. MinGW(http://www.mingw.org/) 프로그램 설치하기
Windows에서 사용하기 적당한 IDE로 Dev-C++가 있습니다. 이 IDE의 경우에는 MinGW에서 제공하는 GCC compiler를 통해 컴파일하기 때문에, 채점 환경과 어느정도 비슷한 결과를 보실 수 있을겁니다. Dev-C++을 설치하시면 컴파일러 설치부터 환경변수 설정까지 자동으로 됩니다.
  1. Online IDE에서 실행하기
저는 이 방법을 추천합니다. 백준 온라인 저지와 비슷하게 Ubuntu + GCC 로 실행할 수 있기 때문에 가장 비슷한 환경에서 확인할 수 있기 때문입니다.
엄청나게 많은 온라인 IDE가 있지만, 개인적으로 쓸만한 사이트를 추천하자면 아래 3개정도입니다.
저는 이 중에서도 ideone.com이 가장 편하고 좋다고 생각합니다.
각자 장단점이 있지만 글의 주제에 벗어나므로 간단하게만 적자면, IDEone.com은 간단하게 코딩하기에 정말 좋지만, 가끔 사이트가 엄청 느리고 컴파일 옵션(O2 등)을 지정하지 못합니다.
c9.io는 Bash 환경을 제공해서 진짜 좋습니다. 하지만 가입도 해야하고 가상환경도 생성하는 등 문제풀이를 하기엔 첫 세팅이 오래걸립니다.

1. ANSI 표준 확인하기

"표준"이라는 것은 중요합니다. 서로 다른 환경과 플랫폼에서 동일한 실행 결과를 보장해줄 수 있기 때문입니다. 이는 모든 컴파일러에도 해당됩니다.
대표적으로 itoa 함수는 표준이 아니기 때문에, 사용을 권장하지 않습니다. 표준이 아니라는 의미는 컴파일러에 따라 존재하지 않는 함수로 취급될 수 있다는 의미입니다. (즉, 컴파일 에러가 나타날 수 있습니다.)
그럼 지금 사용하려는 함수가 표준인지 아닌 지는 어떻게 알 수 있을까요? 바로 다음에서 설명하겠습니다.

*2. 헤더 확인하기

사실 다 필요없고 이 부분만 잘 지켜주어도 컴파일 오류의 90%를 예방할 수 있다고 생각합니다.
C++의 표준 함수들은 각각 그것이 정의되어 있는 헤더파일이 C++ 표준 스펙에 정의되어 있습니다.
예를 들어 memset 의 경우는 또는 에 정의되어 있고,
어떤 컴파일러를 써도 이 헤더를 include 하면 memset이 잘 정의됨을 보장받을 수 있습니다. (이 글 by @wookayin)
C++의 표준 함수들은 레퍼런스를 확인하는 것이 가장 좋습니다.
사용하려는 함수를 아래 레퍼런스들 중 아무 곳에서나 검색하셔서 헤더를 확인하시면 됩니다.
이 외에도 많지만, 개인적으로 Cplusplus.com과 cppreference를 가장 많이 사용합니다. (역시 닉값...)

3. 에러 메시지 천천히 읽어보기

컴파일러가 출력하는 에러 메시지에는 생각보다 많은 정보가 담겨있습니다. 당연한 말이지만, 이 메시지에서 출력된 오류들을 하나씩 수정하면 컴파일 오류가 해결됩니다.
백준 온라인 저지에서는 채점 결과에서 보이는 컴파일 에러를 클릭하시면 메시지를 확인하실 수 있습니다!
소스코드와 함께 경고(warning)와 오류(error)가 표시됩니다. 경고는 말그대로 경고일뿐이니, 오류(error)만 확인하시면 됩니다.
// 컴파일 에러 코드
// 에러가 어디서 나는 지 모르겠어요
#include <stdio.h>
int main(){
    char s[1001];
    scanf("%s", s);
    printf("%d", strlen(s));
    return 0;
}
위 소스코드에 대한 오류 메시지는 아래와 같습니다.
Main.cc: In function ‘int main()’:
Main.cc:3:31: error: ‘strlen’ was not declared in this scope
     int a, b, c = strlen("123");
                               ^
Main.cc:3:15: warning: unused variable ‘c’ [-Wunused-variable]
     int a, b, c = strlen("123");
               ^
Main.cc:4:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &a, &b);
                           ^
여기에는 에러가 하나밖에 없네요. 하지만 가장 많이 보실 메시지라고 생각합니다.
error: ‘strlen’ was not declared in this scope 과 같이 ~ not declared in this scope 는 선언되지 않은 변수나 함수에 나타나는 메시지입니다.
표준이 아닌 함수를 사용하는 경우에도 함수가 없는 것으로 간주하기 때문에 이 경우에 해당됩니다.
이 오류는 해당 함수(또는 변수)를 정의하거나 올바른 헤더를 추가하시면 해결됩니다.
이 외에도 여러 메시지가 있지만, 구글에 error: ‘strlen’ was not declared in this scope 처럼 문장을 통채로 검색하셔도 해결되는 경우가 있으니, 갓구글에 의지하셔도 좋습니다.

4. VS에서 제공하는 함수들

비쥬얼 스튜디오는 어떤 함수가 deprecated 되었다던가 등의 이유로 사용을 못하게 하기도 하더군요. 대표적으로 gets인데, 이 부분이 가끔 화날때가 있습니다.
scanf_s 나 gets_s 등 보안을 이유로 제공되는 함수들이 있습니다. 하지만 채점되는 컴파일러 GCC에 이러한 함수는 없습니다.
비쥬얼 스튜디오 프로젝트를 만들 때(혹은 속성에서) SDL를 체크하지 않으시면 됩니다. 자세한 내용은 여기에서 스크린샷과 함께 잘 설명해주셨습니다.
위에서 잠깐 언급했는데, gets의 경우는 사용하기가 참 난감합니다. 비쥬얼 스튜디오에서는 컴파일이 안되고, gets_s를 gets로 제출할 때마다 수정하기에는 번거롭기 때문입니다. 그래서 저는 아래처럼 매크로를 사용합니다.
#define gets(s) gets_s(s)
그리고 제출할 때는 위 매크로를 제거하고 제출하시면 됩니다. fgets(~)도 써봤는데, 이건 Linux와 Windows의 개행방식(\n, \r\n) 때문인지 조금씩 다르게 동작하더군요.
이렇듯 컴파일러가 다르기 때문에 발생하는 컴파일 에러가 은근히 많습니다.

5. 그 외

  • g++에서 main함수는 int형이어야 합니다. void main을 사용하면 컴파일 에러를 받게 됩니다.
  • for (int i=0; i&lt;n; i++) 와 같이 for문 안에 변수를 선언 했을 때, 변수 i는 해당 for문 블럭을 벗어나면 사라지게 됩니다.
  • itoa 함수는 ANSI에서 규정한 표준 함수가 아닙니다.
  • __int64는 ANSI 표준이 아닙니다. 하지만, 64비트 정수를 사용하고 싶은 경우에는 long long을 사용하면 됩니다.
부족한 지식과 글솜씨지만, 앞으로 답변하실 분들과 질문하실 분들의 수고로움을 대신할 수 있다면 좋겠습니다.
중간에 잘못된 내용이 있다면 지적해주세요!
글을 어떻게 마쳐야할 지 모르겠네요.
그럼 20000

https://www.acmicpc.net/blog/view/52 에서 글 옮김

2017년 4월 29일 토요일

Sublime Text 3에서 "프로시저 시작 지점" 오류 해결법

가벼운 코딩을 위해 서브라임 텍스트로 간단한 코드를 실행할 환경을 구성하였다.

Windows10 에서 MinGW를 설치한 후, g++을 연결하여 빌드되도록 스크립트를 수정하여 사용하고 있었는데 어느날 아래와 같은 오류가 났다.

프로시저 시작 지점
_Jnflx__cxx1112..........을(를) DLL main.exe 에서 찾을 수 없습니다.

main.exe는 내가 실행하려는 파일이었고, 앞에 문자열은 에러메시지인 것 같은데, 암호코드처럼 길고 복잡했다. 여튼 코드를 하나씩 지워본 결과 <string> 헤더를 추가하고 std::string을 사용하려면 위 에러가 발생했다.

원래 컴파일하던 옵션은 아래와 같았는 데,
g++ -std=c++11 -O2 main.cpp -o main.exe

-static-libstdc++ 옵션을 붙여서 아래처럼 컴파일했더니 오류가 해결되었다!
g++ -std=c++11 -O2 main.cpp -o main.exe -static-libstdc++

2016년 11월 24일 목요일

MongoDB 설치 후 저장 디렉토리 변경 주의사항

MongoDB를 설치하기 위해 공식 도큐먼트(https://docs.mongodb.com/.../install-mongodb-on-ubuntu/)를 참고하였다.

정상적으로 설치된 것을 확인하고 이후에 기본 저장 디렉토리를 변경하기 위해서 /etc/mongod.conf 파일을 건드렸다.

# mongod.conf

# for documentation of all options, see:
#   http://docs.mongodb.org/manual/reference/configuration-options/

# Where and how to store data.
storage:
#  dbPath: /var/lib/mongodb
  dbPath: /data/mongodb
  journal:
    enabled: true
#  engine:
#  mmapv1:
#  wiredTiger:

# where to write logging data.
systemLog:
  destination: file
  logAppend: true
  path: /var/log/mongodb/mongod.log

# network interfaces
net:
  port: 27017
  bindIp: 127.0.0.1


#processManagement:

#security:

#operationProfiling:

#replication:

#sharding:

## Enterprise-Only Options:

#auditLog:

#snmp:

dbpath를 /data/mongodb 로 변경하고 /data/mongodb 디렉토리를 만들어줬다.

$ sudo mkdir /data && sudo mkdir /data/mongodb

그리고 다시 mongodb를 구동하면 실행에 실패한다.

$ sudo service mongod status
● mongod.service - High-performance, schema-free document-oriented database
   Loaded: loaded (/lib/systemd/system/mongod.service; disabled; vendor preset: enabled)
   Active: failed (Result: exit-code) since Thu 2016-11-24 04:49:20 UTC; 3s ago
     Docs: https://docs.mongodb.org/manual
  Process: 5335 ExecStart=/usr/bin/mongod --quiet --config /etc/mongod.conf (code=exited, status=100)
 Main PID: 5335 (code=exited, status=100)

mongodb에서 해당 디렉토리에 접근 권한이 없기 때문이다.

다음과 같이 권한을 추가해주면 정상적으로 구동된다.

$ chown mongodb:mongodb /data/mongodb

정상적으로 작동하는 모습

$ sudo service mongod status
● mongod.service - High-performance, schema-free document-oriented database
   Loaded: loaded (/lib/systemd/system/mongod.service; disabled; vendor preset: enabled)
   Active: active (running) since Thu 2016-11-24 04:50:04 UTC; 5s ago
     Docs: https://docs.mongodb.org/manual
 Main PID: 5420 (mongod)
    Tasks: 17
   Memory: 32.1M
      CPU: 130ms
   CGroup: /system.slice/mongod.service
           └─5420 /usr/bin/mongod --quiet --config /etc/mongod.conf

2016년 11월 1일 화요일

2022 - 사다리

https://www.acmicpc.net/problem/2022
https://uva.onlinejudge.org/...&problem=1507


\(a, b, c\) 가 주어지면 \(k\) 를 구해내는 문제이다.

피타고라스로 A, B를 구해서 기울기를 구하고, 두 직선의 교점 방정식을 이용했다. 그리고 교점의 y 위치가 \(c\) 가 되는 순간을 구하도록 이분 탐색을 했다.

우선 a가 포함된 직선을 g(x), b가 포함된 직선을 f(x)라 한다면 아래와 같은 정보가 나온다.

\(
\begin{cases}
A = \sqrt{a^2 - k^2} \\
B = \sqrt{b^2 - k^2}
\end{cases}
\)

\(
\begin{cases}
f(x) = \frac{B}{k}x \\
g(x) = -\frac{A}{k}x+A
\end{cases}
\)

두 직선이 만나는 순간을 \( (c_0, c) \)라 한다면 \( f(c_0) = g(c_0) = c \) 이여야 한다.

\(
\begin{align}
f(c_0) = & \frac{B}{k}c_0 = c \\
& c_0 = \frac{k \cdot c}{B}
\end{align}
\)

\(g(c_0) = g(\frac{k \cdot c}{B}) = c\) 가 나온다면 정답일것이다.

k를 찾는 과정에서 \(f(c_0) \gt c\) 라면 높이가 더 높은 좌표이므로 \(c_0\)을 줄여야한다는 뜻이다. k를 줄이면 \(c_0\)도 줄어든다.

k를 조정해서 만들어진 적당한 x로 f(x) = g(x)가 성립하는 지 확인하면서, 결과에 따라 k를 다시 조정하면 정답이 나온다.

k를 찾는 구간을 줄일 때 epsilon을 1e-5로 설정했을 때는 오답이었다. 이분탐색이 중간에 잘못되고 있나 생각에 구글링하다가 더 작은 결과까지 해보도록 1e-9 로 바꿨더니 정답을 맞았다. 너무 허무함

#include <bits/stdc++.h>
using namespace std;

#define INF 987654321

double a, b, c;

double g(double x, double k){
    double A = sqrt(a*a - k*k);
    return A - (A * x / k);
}

double f(double x, double k){
    return sqrt(b*b - k*k) * x / k;
}

int main(){
    while(~scanf("%lf %lf %lf", &a, &b, &c)){
        double l=0, r=min(a, b);
        
        while(r - l > 1e-9){
            double k = (l+r)/2.0;
            double c0 = k * c / sqrt(b*b - k*k);
            if(g(c0, k) > c){
                l = k;
            } else {
                r = k;
            }
        }
        
        printf("%.3lf\n", l);
    }
    return 0;
}

게시글 목록