나름 개발자의 IT블로그

Q : N개의 정수 배열에서 a~b까지 합을 구하려면 어떻게 하나요? A : for문을 돌면서 더해요! $O(N)$ Q : 그럼 Q개의 쿼리형식으로 들어온다면요? A : 누적합배열을 사용해요! $O(N+Q)$ Q : 그럼 여기에 업데이트도 있다면 있다면 어떻게 할까요? A : 세그먼트 트리를 쓰면 되죠! $O(Q \log N)$ 위의 모든 답변은 실제로 정답이고 더 어려운 알고리즘이 하위 문제를 해결할 수 있다. 예를들어 누적합으로 1번 문제를 해결할 수 있고 세그먼트 트리로 1, 2번 문제를 해결할 수 있다. 하지만 위 문제들을 제곱근 분할법(a.k.a. 루트질)을 사용해서 해결할 수도 있다! 물론 쉬운 알고리즘을 사용할 수 있다면 그걸 사용하는게 좋겠지만 연습용으로 풀기 좋다. 어떻게 해결할 지 알아..

요즘 Chat-GPT가 핫하다. 이 대화형 인공지능이 알고리즘 문제도 해결한다고 하는데 어디까지 해결할 수 있는지 궁금해서 백준 문제로 실험을 해봤다. 문제가 될까봐 실제 제출은 하지 않았고 정답이 맞는지는 내가 판단했다. 문제는 브론즈 5부터 한단계씩 올라가면서 내가 푼 문제들 중 한국어 문제 기준으로 테스트했다. B5 16394 홍익대학교 B4 16204 카드뽑기 주석까지 적는 여유가 보인다. B3 15917 노솔브 방지문제야!! B2 2954 창영이의 일기장 B1 5533 유니크 입력형식이 올바르지 않아 런타임에러가 났는데 풀이만 놓고 보면 정답이다. 입력형식이 복잡해서 그럴 수 있으니 좀 단순한 문제로 다시 시도했다. B1 1110 더하기 사이클 틀렸다. 표본이 적고 solved 난이도가 개인차에..

이번에 건국대학교 교내 알고리즘 대회 KUPC를 개최하게 되었다. 뭐든지 대회를 참여만 해서 개최하고 운영하는건 처음이었는데 좋은 경험을 얻은 것 같다. 운영을 하면서 배운 것과 느낀점, 뒷이야기 등이 많아 기록해두려고 한다. 이번 운영진은 UCPC팀원과 ICPC팀원의 합집합으로 구성되어있다. riroan, aru0504, kth990303, delena0702 개최하게 된 이유 UCPC가 끝나고 알고리즘 문제에 대한 아이디어가 마구마구 샘솟아서 어딘가에 문제를 출제하고 싶었다. 하지만 백준에 출제하려면 적어도 2000문제를 풀어야했는데 아마 몇백문제 남아있었던 것 같다. 그렇게 찾다가 나온 사이트가 누구나 출제할 수 있는 삼성 SW Expert. (문제는 여기) 위에 냈는데 더 많은 사람이 봤으면 하는..

몇달 전에 프로그래머스에서 알고리즘 관련 자격증같은걸 만들었다고 했다. PCCP와 PCCE인데 P가 E보다 어렵다고 한다. 프로그래머스에서 어떤 코테를 하다가 PCCP무료 응시 쿠폰(원래 약 4만원)을 줘서 한번 응시하게 되었다. 특징 난이도는 데브매칭에서 살짝 어려운 정도였다. 시험시간은 2시간 채점 결과를 알려주지 않는다. 온라인 감독을 진행한다. 결과가 30분 안에 나온다. 웅장한 인증서를 준다. 다 푼줄 알고 퇴실했는데 결과를 보니 뭐 하나 틀린 것 같다. 채점 결과를 알려주지 않는게 너무 어렵다. 817점을 받아 Lv4를 얻었다. (목표는 Master...) 이 성적을 가지고 기업에 지원할 수 있는것으로 보아 미래에는 데브매칭 자리를 대신할 수 있겠다는 생각을 했다. (단 기업마다 언어는 다름,..

지난 토요일 코드 몬스터 예선을 통과하여 본선을 보러 갔다. (온라인이라고 했는데 오프라인으로 바꼈음) 코드 몬스터는 알고리즘 실력만으로 LG CNS에 입사 기회를 부여하는 대회같은 코딩테스트(?)이다. 알고리즘쪽은 워낙 잘하는 분들이 많아서 여기서 좋은 성적으로 입사 기회는 얻지 못할 것같고(..) 오프라인 대회 체험을 위해 참석하였다. Before Contest 코드 몬스터는 LG CNS가 있는 마곡에서 진행되었다. 아침을 안먹었는데 빵과 먹을 것을 줘서 맛있게 먹었다. 사용하는 노트북은 역시 LG Gram이었다. Main Contest 메인 대회는 프로그래머스에서 진행되었고 외부 IDE나 구글링은 당연히 통제되었다. 문제를 소개하면 안될 것 같아 느낌만 남기려고 한다. 그냥 내 입장에서 문제가 정말..

지난주 토요일 ICPC 2022 Seoul Regional에 참가했다. 올해는 킨텍스에서 진행됐고 금요일 예비소집, 토요일 본 대회로 이틀을 참석했다. (암호학 수업을 빠졌다. ㅠㅠ) Before Contest 교내 대회 개최 준비로 팀 연습을 많이 안해서 전략은 별로 없었다. 대회가 시작되면 한명은 앞에서부터, 다른 한명은 뒤에서부터, 그리고 내가 파일을 만들고 환경을 세팅해놓는 역할을 하기로 했다. vscode를 지원해서 좋아하고 있었는데 아무 확장이 없는 상태라 pycharm, clion을 사용하기로 했다. 본 대회에서 총 4문제를 풀었는데 내가 푼건 0개이다. ㅠㅠ 예비소집날 세종대팀과 같이 저녁을 했는데 양쪽팀 목표가 서로를 이기는 것이었다. ㅋㅋ 00:11 J solve! 대회가 시작되고 전략..

인생에서 마지막 UCPC를 후회없게 마무리했다. 최근 3개년 UCPC본선 문제를 확인해보니 한문제가 골드급이고 나머지는 플래급 이상이어서 한문제만 풀자라는 느낌으로 참가했는데 생각보다 쉬운 문제가 꽤 있어서 재미있게 풀었던 것 같다. 대회는 삼성 스페이스쉐어에서 진행됐고 티셔츠와 식사, 간식거리가 무한제공 되었다. 또한 많은 후원사의 기념품도 받아왔다. Before Contest 자리배치가 왼쪽같을 줄 알았는데 오른쪽모양 배치여서 살짝 부담스러웠다. 11시 시작이었지만 모종의 이유로 5분이 미뤄졌고 뭔가 앞에서 통제를 해야할 것 같은 분위기였는데 4분까지 아무 통제가 없어 어수선하다가 5분에 시작됐다. During Contest 00:00 문제가 12문제여서 각각 4문제씩 보기로 하고 내가 A~D를 읽기..

지난 UCPC 2022에 PBDS가 나왔다. 몰랐던 자료구조니까 공부하긴 했는데 이게 생각보다 강력한 것 같다. C++에서 지원하는데 이게 있으면 세그트리를 안짜도 된다.(근데 짜는게 맘편하긴 하다.) 감사한 곳 https://codeforces.com/blog/entry/11080 C++ STL: Policy based data structures - Codeforces codeforces.com 일단 g++에서만 가능하다고 한다.(unfortunately only for the GNU C++) 개념적으로는 set(map)인데 순서를 기록한다고 한다. 특정 수가 몇번째로 큰지, 특정 수보다 작은 수가 몇개 있는지를 구할 수 있는 내장 자료구조이다. 사용하려면 헤더를 따로 인클루드 하고 네임스페이스도 쓰..

건국대학교에서 만난 훌륭한 실력을 가진 팀원들과 함께 UCPC를 참가하였다. 다들 실력이 좋으셔서 5솔이라는 좋은 성적을 거두었다. 팀원 : riroan, aru0504, kth990303 Before Contest 예비소집 문제에서 최근 UCPC에서 A번이 가장 쉽다는 힌트를 주었다. 그래서 올해도 A가 가장 쉬울 것으로 예상해서 누가 A를 풀지 정해야 했는데 kth990303님이 풀겠다고 했다. 어려운 문제도 붙잡고 있는 스타일이어서 확실하게 풀 수 있는 A를 빠르게 풀고 그동안 나와 aru0504님이 다른 문제를 보기로 했다. 나는 대회에서 문제를 딱 보고 10초 안에 풀이가 떠오르지 않으면 넘기는 성격이라 모든 문제 파악하는게 더 좋았는데 잘 된것같다. 00:01 A solve! 대회 시작 후 몇..

문제가 그렇게 어렵지 않고 재미있는 문제들이 많아 남겨보고자 한다. (푸는대로 업데이트 할 예정..) A. 2의 보수 정수를 하나 입력받아 그 수의 2의 보수를 출력하면 된다. 입력받은 정수를 $a$라고 하면 $a \oplus (2^{32}-1) + 1$ 이 정답이다. (지난 코드포스 768에서 영감받음) B. 조커 찾기 카드 27장을 섞는 방법이 주어졌을 때 $n$번 섞고 난 후 조커($1$번 카드)가 어디있는지 찾는 문제이다. - 덱 위에서 13장을 왼쪽, 14장을 오른쪽으로 보낸다. - 배열 $a$가 있을 때 $i$가 홀수이면 오른쪽, 짝수이면 왼쪽에서 $a_i$장을 가져와 새 덱 밑에 추가한다. 문제에서 나타낸대로 구현하면 된다. 파이썬으로 큐를 사용해봤는데 시간초과가 나서 리스트 전체를 조작하는..