티스토리로 옮겼습니다.
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시쯤 출근하시는듯. 이거 진짜 좋아보인다. 옷차림도 자유다.
사실 난 장래희망이 "넥타이를 메지 않는 직업"일 정도로, 분위기를 많이 생각하고 취직을 고려해서 삼성은 죽어도 안갈래 라는 생각이 컸는데, 최근에 점점 바뀌다가 이번 기회에 직접 견학(?)을 다녀오니 생각이 정말 많이 바뀌었다.
가장 도움이 된 건, 지금 일하시는 분들과 이야기를 나눌 수 있었고. 비슷한 공부를 하는 사람들을 알아갈 수 있었다는 점, 회사가 돌아가는 것을 눈으로 직접 보고 느꼈다는 점 정도일 것 같다.
진짜 열심히 공부해야지라는 생각이 머리 끝까지 차올랐다. 의욕이 마구마구 생기는 보람찬 시간이었다!
캠프 참가 여부를 물어보는 별도의 메일이 왔었고, 대상은 역량테스트 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 환경에서 완전히 동일하진 못해도 컴파일 채점환경과 비슷하게 실행하는 방법이 있습니다.
- MinGW(http://www.mingw.org/) 프로그램 설치하기
Windows에서 사용하기 적당한 IDE로 Dev-C++가 있습니다. 이 IDE의 경우에는 MinGW에서 제공하는 GCC compiler를 통해 컴파일하기 때문에, 채점 환경과 어느정도 비슷한 결과를 보실 수 있을겁니다. Dev-C++을 설치하시면 컴파일러 설치부터 환경변수 설정까지 자동으로 됩니다.
- Online IDE에서 실행하기
저는 이 방법을 추천합니다. 백준 온라인 저지와 비슷하게 Ubuntu + GCC 로 실행할 수 있기 때문에 가장 비슷한 환경에서 확인할 수 있기 때문입니다.
엄청나게 많은 온라인 IDE가 있지만, 개인적으로 쓸만한 사이트를 추천하자면 아래 3개정도입니다.
저는 이 중에서도 ideone.com이 가장 편하고 좋다고 생각합니다.
각자 장단점이 있지만 글의 주제에 벗어나므로 간단하게만 적자면, IDEone.com은 간단하게 코딩하기에 정말 좋지만, 가끔 사이트가 엄청 느리고 컴파일 옵션(O2 등)을 지정하지 못합니다.
c9.io는 Bash 환경을 제공해서 진짜 좋습니다. 하지만 가입도 해야하고 가상환경도 생성하는 등 문제풀이를 하기엔 첫 세팅이 오래걸립니다.
1. ANSI 표준 확인하기
"표준"이라는 것은 중요합니다. 서로 다른 환경과 플랫폼에서 동일한 실행 결과를 보장해줄 수 있기 때문입니다. 이는 모든 컴파일러에도 해당됩니다.
대표적으로
itoa 함수는 표준이 아니기 때문에, 사용을 권장하지 않습니다. 표준이 아니라는 의미는 컴파일러에 따라 존재하지 않는 함수로 취급될 수 있다는 의미입니다. (즉, 컴파일 에러가 나타날 수 있습니다.)
그럼 지금 사용하려는 함수가 표준인지 아닌 지는 어떻게 알 수 있을까요? 바로 다음에서 설명하겠습니다.
*2. 헤더 확인하기
사실 다 필요없고 이 부분만 잘 지켜주어도 컴파일 오류의 90%를 예방할 수 있다고 생각합니다.
C++의 표준 함수들은 각각 그것이 정의되어 있는 헤더파일이 C++ 표준 스펙에 정의되어 있습니다.예를 들어 memset 의 경우는또는 에 정의되어 있고,
C++의 표준 함수들은 레퍼런스를 확인하는 것이 가장 좋습니다.
사용하려는 함수를 아래 레퍼런스들 중 아무 곳에서나 검색하셔서 헤더를 확인하시면 됩니다.
- http://www.cplusplus.com/
- http://ko.cppreference.com/w/
- http://msdn.microsoft.com/ko-kr/library/52cs05fz%28v=vs.100%29.aspx
이 외에도 많지만, 개인적으로 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<n; i++)와 같이 for문 안에 변수를 선언 했을 때, 변수 i는 해당 for문 블럭을 벗어나면 사라지게 됩니다.itoa함수는 ANSI에서 규정한 표준 함수가 아닙니다.__int64는 ANSI 표준이 아닙니다. 하지만, 64비트 정수를 사용하고 싶은 경우에는long long을 사용하면 됩니다.
부족한 지식과 글솜씨지만, 앞으로 답변하실 분들과 질문하실 분들의 수고로움을 대신할 수 있다면 좋겠습니다.
중간에 잘못된 내용이 있다면 지적해주세요!
글을 어떻게 마쳐야할 지 모르겠네요.
2017년 4월 29일 토요일
Sublime Text 3에서 "프로시저 시작 지점" 오류 해결법
가벼운 코딩을 위해 서브라임 텍스트로 간단한 코드를 실행할 환경을 구성하였다.
Windows10 에서 MinGW를 설치한 후, g++을 연결하여 빌드되도록 스크립트를 수정하여 사용하고 있었는데 어느날 아래와 같은 오류가 났다.
main.exe는 내가 실행하려는 파일이었고, 앞에 문자열은 에러메시지인 것 같은데, 암호코드처럼 길고 복잡했다. 여튼 코드를 하나씩 지워본 결과 <string> 헤더를 추가하고 std::string을 사용하려면 위 에러가 발생했다.
원래 컴파일하던 옵션은 아래와 같았는 데,
-static-libstdc++ 옵션을 붙여서 아래처럼 컴파일했더니 오류가 해결되었다!
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 파일을 건드렸다.
dbpath를 /data/mongodb 로 변경하고 /data/mongodb 디렉토리를 만들어줬다.
그리고 다시 mongodb를 구동하면 실행에 실패한다.
mongodb에서 해당 디렉토리에 접근 권한이 없기 때문이다.
다음과 같이 권한을 추가해주면 정상적으로 구동된다.
정상적으로 작동하는 모습
정상적으로 설치된 것을 확인하고 이후에 기본 저장 디렉토리를 변경하기 위해서 /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 로 바꿨더니 정답을 맞았다. 너무 허무함
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;
}1939 - 중량제한
https://www.acmicpc.net/problem/1939
S에서 E로 가는 데, 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 구한다.
문제를 읽고 왠지 이거 다익스트라처럼 그리디하게 풀면 풀리겠다 싶어서 그래프 몇개 끄적거렸는데 무한루프에 빠질것만 같은 공포에 휩싸였다.
dp를 적용하자니 다리의 중량제한 \(c(1 \le c \le 10^9)\) 라서 안되겠다싶었고.
그럼 스패닝 트리를 만들어볼까해서 프림을 생각했는데 몇 개 적어놨던 예제에서부터 안됐다.
그래도 트리로 만드는게 가장 정답같아서 크루스칼로 구현했는데 정답이었다.
크루스칼로 최대 스패닝 트리를 만들고, S에서 E로 가는 경로 중에 가장 중량제한이 작은 것을 출력한다.
다른 사람들 정답 코드를 보니까 다익스트라도 있었는데, 크루스칼로 푼 사람들 중에 하나를 보고 배웠다.
S에서 E로 가는 경로를 다시 탐색할 필요가 없이, S가 속한 집합과 E가 속한 집합이 같아지는 시점에 연결하는 간선의 중량이 "가능한 가장 큰 중량제한"이었다.
S에서 E로 가는 데, 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최대값을 구한다.
문제를 읽고 왠지 이거 다익스트라처럼 그리디하게 풀면 풀리겠다 싶어서 그래프 몇개 끄적거렸는데 무한루프에 빠질것만 같은 공포에 휩싸였다.
dp를 적용하자니 다리의 중량제한 \(c(1 \le c \le 10^9)\) 라서 안되겠다싶었고.
그럼 스패닝 트리를 만들어볼까해서 프림을 생각했는데 몇 개 적어놨던 예제에서부터 안됐다.
그래도 트리로 만드는게 가장 정답같아서 크루스칼로 구현했는데 정답이었다.
크루스칼로 최대 스패닝 트리를 만들고, S에서 E로 가는 경로 중에 가장 중량제한이 작은 것을 출력한다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef pair<int,int> ii;
struct edge {
int u, v, d;
bool operator < (const edge& e) const {
return d < e.d;
}
};
vector<edge> E;
int group[100001];
int find(int v){
if(v != group[v])
return (group[v] = find(group[v]));
return v;
}
bool Union(int p, int q){
p = find(p);
q = find(q);
if(p == q) return false;
group[q] = p;
return true;
}
vector<ii> adj[100001];
bool visit[100001];
int answer(int pos, int dst, int m = INF){
if(pos == dst) return m;
if(visit[pos]) return 0;
visit[pos] = true;
for(auto& v : adj[pos]){
int r = answer(v.first, dst, min(v.second, m));
if(r != 0) return r;
}
return 0;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
E.push_back({a-1, b-1, c});
}
sort(E.rbegin(), E.rend());
for(int i=0; i<n; ++i) group[i] = i;
for(auto& e : E){
if( Union(e.u, e.v) ){
adj[e.u].push_back(ii(e.v, e.d));
adj[e.v].push_back(ii(e.u, e.d));
}
}
int src, dst;
scanf("%d %d", &src, &dst);
printf("%d", answer(src-1, dst-1));
return 0;
}
다른 사람들 정답 코드를 보니까 다익스트라도 있었는데, 크루스칼로 푼 사람들 중에 하나를 보고 배웠다.
S에서 E로 가는 경로를 다시 탐색할 필요가 없이, S가 속한 집합과 E가 속한 집합이 같아지는 시점에 연결하는 간선의 중량이 "가능한 가장 큰 중량제한"이었다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef pair<int,int> ii;
struct edge {
int u, v, d;
bool operator < (const edge& e) const {
return d < e.d;
}
};
vector<edge> E;
int group[100001];
int find(int v){
if(v != group[v])
return (group[v] = find(group[v]));
return v;
}
int main(){
int n, m;
scanf("%d %d", &n, &m);
while(m--){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
E.push_back({a-1, b-1, c});
}
sort(E.rbegin(), E.rend());
for(int i=0; i<n; ++i) group[i] = i;
int src, dst;
scanf("%d %d", &src, &dst);
for(auto& e : E){
group[find(e.u)] = find(e.v);
if( find(src-1) == find(dst-1) ){
printf("%d", e.d);
break;
}
}
return 0;
}2016년 10월 31일 월요일
2146 - 다리 만들기
https://www.acmicpc.net/problem/2146
각 대륙마다 번호를 붙여서 동기적으로 대륙을 넓혀간다. 넓어가는 도중에 다른 대륙과 만난다면, 그 시점에 각 대륙이 넓혀진 거리만큼이 (부딪혔으므로) 연결된 거리이고, 그 중에 최소를 구한다.
동기적으로 넓혀가는 이유는 대륙 하나를 잡고 나머지와 비교하면 아래와 같은 경우가 생긴다.
대륙간의 거리를 모두 비교하면 \(O(N^2)\)이다. 물론 N이 최대 100까지이므로 모두 비교해도 문제될 건 없다.
각 대륙마다 번호를 붙여서 동기적으로 대륙을 넓혀간다. 넓어가는 도중에 다른 대륙과 만난다면, 그 시점에 각 대륙이 넓혀진 거리만큼이 (부딪혔으므로) 연결된 거리이고, 그 중에 최소를 구한다.
동기적으로 넓혀가는 이유는 대륙 하나를 잡고 나머지와 비교하면 아래와 같은 경우가 생긴다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
int n, a[100][100];
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};
bool visit[100][100];
bool giveId(int y, int x, const int id){
if(y < 0 || y >= n || x < 0 || x >= n) return 0;
if(visit[y][x] || a[y][x] == 0) return 0;
visit[y][x] = true;
a[y][x] = id;
for(int i=0; i<4; ++i){
giveId(y+dy[i], x+dx[i], id);
}
return 1;
}
struct land {
int y, x, color;
};
int Distance[100][100];
int main(){
scanf("%d ", &n);
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
scanf("%d", &a[i][j]);
Distance[i][j] = a[i][j] ? 0 : INF;
}
}
int color = 1;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
color += giveId(i, j, color);
}
}
queue<land> q;
for(int i=0; i<n; ++i){
for(int j=0; j<n; ++j){
if(a[i][j] != 0) continue;
for(int d=0; d<4; ++d){
int ny=i+dy[d], nx=j+dx[d];
if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if(0 != a[ny][nx]){
Distance[ny][nx] = min(Distance[ny][nx], 1);
q.push({i, j, a[ny][nx]});
break;
}
}
}
}
int answer = 0;
int dist = 0;
while(!q.empty()){
++dist;
int qs = q.size();
while(qs--){
int y = q.front().y;
int x = q.front().x;
int c = q.front().color;
q.pop();
if(a[y][x]) continue;
a[y][x] = c;
Distance[y][x] = dist;
for(int d=0; d<4; ++d){
int ny=y+dy[d], nx=x+dx[d];
if(ny < 0 || ny >= n || nx < 0 || nx >= n) continue;
if(a[ny][nx] == 0){
q.push({ny, nx, c});
} else if(a[ny][nx] != c){
int expected = dist + Distance[ny][nx];
if(answer) answer = min(answer, expected);
else answer = expected;
}
}
}
if(answer > 0) break;
}
printf("%d", answer);
return 0;
}2016년 10월 27일 목요일
2873 - 롤러코스터
https://www.acmicpc.net/problem/2873
홀수x짝수, 짝수x홀수, 홀수x홀수 크기에 대해서는 모든 경로를 방문하여 가장 오른쪽 아래 칸으로 갈 수 있다.
짝수x짝수 크기는 1칸 빼고 나머지는 다 방문해서 도착할 수 있는데, (홀수, 짝수) 또는 (짝수, 홀수)에 위치한 칸을 들리지 못한다. 빼는 1칸은 가장 작은 기쁨이 있는 칸을 선택하면 될 것이다.
여기까지는 어떻게 생각해냈는데, 경로를 어떻게 만들어야할지 몰라서 한참 고민하다 결국 솔루션을 참고해버렸다.
경로를 크게 3부분으로 나눈다.
가운데 지그재그로 제외할 1칸을 피해서 이동하는 것 때문이다. 지그재그로 2줄만 어떻게 해결하면 되므로, 그 전행까지는 R...RDL...LD 로 이동하고, 이후의 행부터는 DL...LDR...R 로 이동하면 된다.
홀수x짝수, 짝수x홀수, 홀수x홀수 크기에 대해서는 모든 경로를 방문하여 가장 오른쪽 아래 칸으로 갈 수 있다.
짝수x짝수 크기는 1칸 빼고 나머지는 다 방문해서 도착할 수 있는데, (홀수, 짝수) 또는 (짝수, 홀수)에 위치한 칸을 들리지 못한다. 빼는 1칸은 가장 작은 기쁨이 있는 칸을 선택하면 될 것이다.
여기까지는 어떻게 생각해냈는데, 경로를 어떻게 만들어야할지 몰라서 한참 고민하다 결국 솔루션을 참고해버렸다.
경로를 크게 3부분으로 나눈다.
가운데 지그재그로 제외할 1칸을 피해서 이동하는 것 때문이다. 지그재그로 2줄만 어떻게 해결하면 되므로, 그 전행까지는 R...RDL...LD 로 이동하고, 이후의 행부터는 DL...LDR...R 로 이동하면 된다.
#include <cstdio>
using namespace std;
int H, W;
int a[1000][1000];
void repeat(char ch, int repeated){while(repeated-->0)putchar(ch);}
int main(){
scanf("%d %d", &H, &W);
for(int i=0; i<H; ++i){
for(int j=0; j<W; ++j){
scanf("%d", &a[i][j]);
}
}
if( H%2 ){
repeat('R', W-1);
for(int i=0; i<H-1; i+=2){
repeat('D', 1); repeat('L', W-1);
repeat('D', 1); repeat('R', W-1);
}
} else if( W%2 ){
repeat('D', H-1);
for(int i=0; i<W-1; i+=2){
repeat('R', 1); repeat('U', H-1);
repeat('R', 1); repeat('D', H-1);
}
} else {
// finding minimum cell
int x=0, y=1;
for(int i=0; i<H; ++i){
for(int j=0; j<W; ++j){
if((i+j)%2 && a[y][x] > a[i][j]){
y = i, x = j;
}
}
}
int h=0, w=0;
// top
for(; h+1 < y; h += 2){
repeat('R', W-1); repeat('D', 1);
repeat('L', W-1); repeat('D', 1);
}
// middle
int ny = h^1;
for(w=0; w < W-1; ++w){
if( ny != y || w != x ){
repeat( ny%2 ? 'D':'U', 1);
ny ^= 1;
}
repeat('R', 1);
}
if( ny%2 ) repeat('D', 1);
// bottom
h = (h/2*2) + 2;
for(; h < H; h += 2){
repeat('D', 1); repeat('L', W-1);
repeat('D', 1); repeat('R', W-1);
}
}
return 0;
}
2016년 10월 26일 수요일
1541 - 잃어버린 괄호
https://www.acmicpc.net/problem/1541
음수 부호(-)가 나오는 순간부터 모든 수가 음수라고 생각하면 된다. a+b-(c+...+z) 가 되기 때문.
음수 부호(-)가 나오는 순간부터 모든 수가 음수라고 생각하면 된다. a+b-(c+...+z) 가 되기 때문.
#include <bits/stdc++.h>
using namespace std;
int main() {
char s[101];
scanf("%s", s);
int num=0, sum=0;
bool sub = false;
for(int i=0; s[i]; ++i){
if('0' <= s[i] && s[i] <= '9'){
num = 10*num + (s[i]-'0');
} else {
if(!sub) sum += num;
else sum -= num;
num = 0;
sub |= s[i] == '-';
}
}
if(!sub) sum += num;
else sum -= num;
printf("%d", sum);
return 0;
}1080 - 행렬
https://www.acmicpc.net/problem/1080
왼쪽에서 오른쪽으로, 위에서 아래로 한 칸씩 확인하면서 3x3크기의 부분행렬이 서로 다르다면 바꾼다. 마지막에 바꾼 횟수를 출력하면 정답이다.
이런 그리디가 통할 수 있는 것은, 이미 지나간 부분(탐색한 부분)에서 서로 다른 칸이 존재하면 안되기 때문이다.
왼쪽에서 오른쪽으로, 위에서 아래로 한 칸씩 확인하면서 3x3크기의 부분행렬이 서로 다르다면 바꾼다. 마지막에 바꾼 횟수를 출력하면 정답이다.
이런 그리디가 통할 수 있는 것은, 이미 지나간 부분(탐색한 부분)에서 서로 다른 칸이 존재하면 안되기 때문이다.
#include <bits/stdc++.h>
using namespace std;
int h, w;
char A[50][51];
void flip(int y, int x){
for(int i=y; i<y+3; ++i){
for(int j=x; j<x+3; ++j){
A[i][j] = !A[i][j];
}
}
}
int main(){
scanf("%d %d", &h, &w);
for(int i=0; i<h; ++i) scanf("%s ", A[i]);
for(int i=0; i<h; ++i){
char s[51];
scanf("%s ", s);
for(int j=0; j<w; ++j){
A[i][j] = A[i][j] == s[j];
}
}
int ans = 0;
for(int i=0; i<h-2; ++i){
for(int j=0; j<w-2; ++j){
if( A[i][j] == 0 ){
flip(i, j);
ans += 1;
}
}
}
for(int i=0; i<h; ++i){
for(int j=0; j<w; ++j)
if(A[i][j] == 0) return puts("-1"), 0;
}
printf("%d\n", ans);
return 0;
}2016년 10월 23일 일요일
띠용 이게 무슨 일이지
띠용
무슨일인지 갑자기 트래픽이 평소를 훌쩍 넘긴 811을 기록했다.
최고기록이니 일단 글로 적어서 저장하자 (....)
레퍼러 보니까 구글에서 1509 - 팰린드롬 분할 이거 타고 온거 같은데 무슨일이지 정말..
맨날 구글 크롤러 봇따위만 오는 블로그인줄 알았는데.. 크흡ㅠ
다시 문제풀이를 열심히 하라는 계시로 알아들어야겠다.
2016년 10월 20일 목요일
5535 - 패셔니스타
https://www.acmicpc.net/problem/5535
각 날짜에 대해 최고기온을 고려해서 입을 수 있는 옷들을 정리한다.
각 날짜마다 한 옷을 선택한다고 하면, D일동안 N개의 옷으로는 경우의 수는 \(O(N^D)\) 이다.
dp 점화식을
각 날짜에 대해 최고기온을 고려해서 입을 수 있는 옷들을 정리한다.
각 날짜마다 한 옷을 선택한다고 하면, D일동안 N개의 옷으로는 경우의 수는 \(O(N^D)\) 이다.
dp 점화식을
dp[D][N] = D번째 날에 N번째 옷을 선택했을 때의 문제의 정답
이라고 하면 \(O(ND)\) 으로 줄일 수 있다.#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long lld;
int D, N;
vector<int> a[201];
int dp[201][201];
int f(int pos, int sel){
if(pos == D-1) return 0;
int& r = dp[pos][sel];
if(r != -1) return r;
r = 0;
for(int i=0; i < a[pos+1].size(); ++i){
int diff = abs(a[pos][sel] - a[pos+1][i]);
r = max(r, diff + f(pos+1, i));
}
return r;
}
int main(){
memset(dp, -1, sizeof(dp));
scanf("%d %d", &D, &N);
int T[D];
for(int i=0; i<D; ++i) scanf("%d", &T[i]);
for(int i=0; i<N; ++i){
int low, high, c;
scanf("%d %d %d", &low, &high, &c);
for(int j=0; j<D; ++j){
if(low <= T[j] && T[j] <= high){
a[j].push_back(c);
}
}
}
int r = 0;
for(int i=0; i < a[0].size(); ++i){
r = max(r, f(0, i));
}
printf("%d", r);
return 0;
}
2016년 10월 13일 목요일
13325 - 이진 트리
https://www.acmicpc.net/problem/13325
각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다.
이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다.
왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다.
가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다.
2016 ACM-ICPC 한국 인터넷 예선 A번
각 노드에서 리프 노드까지의 거리가 (왼쪽으로 가든지, 오른쪽으로 가든지) 같도록 조정하는 것이므로 재귀를 생각할 수 있다.
이를 해결할 작은 문제로 재귀의 중간 과정부터 생각했다.
왼쪽과 오른쪽의 길이가 달라져서 조정이 필요한 상황은 "왼쪽 != 오른쪽" 이다. 이를 조정하는 작업은 더 작은 쪽에 가중치를 증가시키는 것이다.
가중치는 보정을 위해 추가하는 것이므로, 맞추고자 하는 차이만큼 증가시키면 된다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long lld;
int n;
int a[(1<<21)+1];
int leftPos(int pos){ return 2*pos+1; }
int rightPos(int pos){ return leftPos(pos)+1; }
int f(int pos){
int l = leftPos(pos), r = rightPos(pos);
// is leaf
if(l > n || r > n) return a[pos];
int lsum = f(l), rsum = f(r);
if(lsum < rsum){
a[l] += rsum - lsum;
}
else if(lsum > rsum){
a[r] += lsum - rsum;
}
return a[pos] + max(lsum, rsum);
}
int main(){
int k;
scanf("%d", &k);
n = (1<<(k+1))-1-1;
for(int i=1; i<=n; ++i) scanf("%d", &a[i]);
f(0);
int ans = 0;
for(int i=1; i<=n; ++i) ans += a[i];
printf("%d", ans);
return 0;
}2016년 9월 23일 금요일
Codeforces Round #372 (Div. 2)
http://codeforces.com/contest/716
A. Crazy Computer
수 사이의 차이가 C 이하이면 카운팅하고, 그렇지 않으면 카운트가 0으로 초기화된다. 수열 끝에서 카운트가 몇인지 출력한다.
B. Complete the Word
본문에서 "... to replace all the question marks with uppercase letters such that ..." 이라고 했는 데, 강조된 uppercase letters만 보느라 "replace all the question marks"를 놓쳤다. 물음표를 계속 그대로 방치해서 결국 계속 틀렸던 문제.
본문의 조건을 좀 더 세심하게 읽자.
틀린거 고치느라 급해서 $O(50000 * 26)$ 으로 제출
A. Crazy Computer
수 사이의 차이가 C 이하이면 카운팅하고, 그렇지 않으면 카운트가 0으로 초기화된다. 수열 끝에서 카운트가 몇인지 출력한다.
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long lld;
int main(){
int n, c, a[1000001], len=0;
scanf("%d %d", &n, &c);
for(int i=0; i<n; ++i){
scanf("%d", &a[i]);
if(i > 0){
if(a[i]-a[i-1] <= c) len += 1;
else len = 1;
} else len = 1;
}
printf("%d", len);
return 0;
}
B. Complete the Word
본문에서 "... to replace all the question marks with uppercase letters such that ..." 이라고 했는 데, 강조된 uppercase letters만 보느라 "replace all the question marks"를 놓쳤다. 물음표를 계속 그대로 방치해서 결국 계속 틀렸던 문제.
본문의 조건을 좀 더 세심하게 읽자.
틀린거 고치느라 급해서 $O(50000 * 26)$ 으로 제출
#include <bits/stdc++.h>
using namespace std;
#define INF 987654321
typedef long long lld;
int main(){
char s[50501]={};
scanf("%s ", s);
bool ans = false;
for(int i=0; s[i]; ++i){
bool used[26]={};
char f[26]={};
int j, c=0;
for(j=0; j<26 && s[i+j]; ++j){
if(s[i+j] == '?') continue;
if(used[s[i+j]-'A']) break;
used[s[i+j]-'A'] = true;
}
if(j == 26) ans = true;
if(ans){
for(j=0; j<26; ++j){
if(!used[j]) f[c++] = 'A'+j;
}
int c2=0;
for(j=0; j<26; ++j){
if(s[i+j] == '?') s[i+j] = f[c2++];
}
break;
}
}
if(!ans) return puts("-1"), 0;
for(int i=0; s[i]; ++i) putchar(s[i] == '?' ? 'A' : s[i]);
return 0;
}
2016년 9월 12일 월요일
문제적남자 73화:수학 - 코딩으로 풀어보기
문제적남자 73화 - 수학 풀이
수능 D-100 특집으로 이런 문제가 나왔다.
다음과 같은 몇 가지 규칙을 발견하고 브루트 포스로 풀어보기로 했다.
1. 열 번째 숫자는 0 이다. (10의 배수는 0으로 끝나기 때문)
2. 다섯 번째 숫자는 5 이다. (5의 배수는 0, 5로 끝난다. 0은 열 번째 숫자이므로 5)
3. 짝수 번째 숫자는 2, 4, 6, 8 중 하나이다.
4. 홀수 번째 숫자는 1, 2, 3, 4, 6, 7, 8, 9 중 하나이다.
소스: https://jsfiddle.net/J00nas/yrmen84L/
javascript로 적어봤는데, 비동기식이라 그런지 제대로 걸러지지가 않는다. (그리고 브라우저의 자바스크립트 버전별로 다르게 보일 수 있다.) 그래도 답은 나온다.
모던 브라우저에서는 위처럼 보일것이다.
자바스크립트로는 코드가 정확하지 않은 것 같아서 C++로 다시 적었다.
소스: https://ideone.com/yoLJXx
신기하게도 규칙을 만족하는 숫자는 3816547290 뿐이었다.
수능 D-100 특집으로 이런 문제가 나왔다.
첫 번째 숫자까지는 1로 나누어지고,
두 번째 숫자까지는 2로, .... 열 번째 숫자까지는 10으로 나누어진다.
0부터 9까지 10개의 숫자를 모두 사용해 규칙에 맞는 수를 만들어라.
다음과 같은 몇 가지 규칙을 발견하고 브루트 포스로 풀어보기로 했다.
1. 열 번째 숫자는 0 이다. (10의 배수는 0으로 끝나기 때문)
2. 다섯 번째 숫자는 5 이다. (5의 배수는 0, 5로 끝난다. 0은 열 번째 숫자이므로 5)
3. 짝수 번째 숫자는 2, 4, 6, 8 중 하나이다.
4. 홀수 번째 숫자는 1, 2, 3, 4, 6, 7, 8, 9 중 하나이다.
소스: https://jsfiddle.net/J00nas/yrmen84L/
javascript로 적어봤는데, 비동기식이라 그런지 제대로 걸러지지가 않는다. (그리고 브라우저의 자바스크립트 버전별로 다르게 보일 수 있다.) 그래도 답은 나온다.
모던 브라우저에서는 위처럼 보일것이다.
자바스크립트로는 코드가 정확하지 않은 것 같아서 C++로 다시 적었다.
소스: https://ideone.com/yoLJXx
신기하게도 규칙을 만족하는 숫자는 3816547290 뿐이었다.
2016년 9월 10일 토요일
2991 - 사나운 개
https://www.acmicpc.net/problem/2991
$p$분 후에 우체부가 도착한다면, $p \% (a+b)$ 가 $a$(공격시간)보다 이후라면 공격받지 않는다.
$p$분 후에 우체부가 도착한다면, $p \% (a+b)$ 가 $a$(공격시간)보다 이후라면 공격받지 않는다.
#include <cstdio>
bool attacked(int n, int a, int b){
n %= (a+b);
return n < a;
}
int main(){
int a, b, c, d, n;
scanf("%d %d %d %d", &a, &b, &c, &d);
for(int i=0; i<3; ++i){
scanf("%d", &n);
printf("%d\n", attacked(n-1, a, b) + attacked(n-1, c, d));
}
return 0;
}2016년 9월 9일 금요일
2118 - 두 개의 탑
https://www.acmicpc.net/problem/2118
문제를 푸는 데 가장 크게 작용한 아이디어는
두 지점 사이의 거리는 "$x$ = [a, b) 사이의 부분 합" 라고 할 때 $x$ 와 전체 길이의 합 - $x$ 중 더 작은 것이 된다.
이러한 부분합들 중 가장 큰 것이 문제의 정답이다.
부분합을 구하려는 데 계속 $O(N^2)$ 밖에 안 떠올랐다. 시계방향과 반시계방향 두 경로 중 더 작은것을 선택하는 것 때문이었다.
"문제의 정답 $\le$ 전체 길이의 합 / 2" 이니까 전체 길이 합의 절반보다 작지만 가장 큰 수만 찾으면 되겠구나 생각하고 이진탐색을 궁리해보았다.
계산하고 하는 거리 [a, b) 는 a $\le$ b인 것들만 확인해도 충분했다. 예를 들어, [5, 3) 을 확인하고 싶다면 전체 거리의 합에서 [3, 4) 를 빼면 되기 때문이다. (한쪽 방향에 대해서만 본다면)
시계방향/반시계방향에 대해 위 계산을 범위를 좁혀가면서 했다.
문제를 푸는 데 가장 크게 작용한 아이디어는
라는 사실이었다.문제의 정답 $\le$ 전체 길이의 합 / 2
두 지점 사이의 거리는 "$x$ = [a, b) 사이의 부분 합" 라고 할 때 $x$ 와 전체 길이의 합 - $x$ 중 더 작은 것이 된다.
이러한 부분합들 중 가장 큰 것이 문제의 정답이다.
부분합을 구하려는 데 계속 $O(N^2)$ 밖에 안 떠올랐다. 시계방향과 반시계방향 두 경로 중 더 작은것을 선택하는 것 때문이었다.
"문제의 정답 $\le$ 전체 길이의 합 / 2" 이니까 전체 길이 합의 절반보다 작지만 가장 큰 수만 찾으면 되겠구나 생각하고 이진탐색을 궁리해보았다.
계산하고 하는 거리 [a, b) 는 a $\le$ b인 것들만 확인해도 충분했다. 예를 들어, [5, 3) 을 확인하고 싶다면 전체 거리의 합에서 [3, 4) 를 빼면 되기 때문이다. (한쪽 방향에 대해서만 본다면)
시계방향/반시계방향에 대해 위 계산을 범위를 좁혀가면서 했다.
피드 구독하기:
글 (Atom)