study/problemsolving

    UCPC 2022 본선 후기

    예선을 운좋게 진행한 덕분에 본선을 잘 보고 왔다! 인터넷으로 돌아다니면서 구경했던 풍선 달기, 단체 티셔츠 입기, 간식 먹으면서 문제풀기 등등.. 다양한 사람들이 모여서 같은 목표를 가지고 오랜 시간동안 고민한다는 게 참 매력적이다. 우리 팀은 총 12문제 중에 4문제를 해결해서 41위를 차지했다! 본선 진출 팀이 53팀이라 높은 순위는 아니었지만, 이제 시작이라는 생각으로 즐기고 왔다. 대회는 삼성역 주변 지하 대관홀에서 진행됐다. 스탭 분들께서는 다들 목걸이를 미리 하고 계셨는데, 백준에서 자주 봤던 아이디들이 목에 걸려있는 걸 보고 정말 놀랐다. 인사를 하고 싶었지만 정말정말 바빠 보여서 말 걸기도 어려웠다 🙄 세명이서 하나의 노트북으로 문제를 해결해야 했어서, 종이를 보면서 풀이를 떠올리고 코딩..

    UCPC 2022 예선 후기

    어떻게 같은 학교에서 인연이 맞아 함께 참가한 UCPC, 몇번 만나 연습셋도 풀었다 이번에 2시부터 3시간동안 예선이 진행됐는데, 어후 이거 진짜 너무 어렵다 A 는 기본 입출력 문제라서 바로 태현님이 솔브 G 읽어보다가 할만한 것 같았는데 순서 구분하는 걸 나중에 알아채서 패스 B 보다가 CCW 넣으면 될 것 같아서 건드리다가 태현님한테 넘기고 F 구현 몇번 틀리고 AC (믿음의 제출을 했어야 했다,,,). 이때 태현님이 B도 같이 해결해 주셨음 E, J는 명기님이 해결. :fan: 끝나기 전에 D를 오프라인쿼리 + 레이지세그 + 이분탐색으로 풀다가 시간 없어서 못 풀게 됐다. (이렇게 푸는 거 맞아요..?) 5솔브를 해서 아슬아슬한 곳에 위치했다. UCPC 꼭 나가보고 싶었는데 생각보다 좋은 성적을 ..

    [Codeforces] Round #784 Div. 4

    처음으로 올솔브를 했다 ! 매번 코포 치다가 일이 생겨서 점수가 바닥으로 고꾸라졌는데, 이번엔 제대로 집중해서 풀어봤다. A. Division? 단순 조건문으로 판단한다. B. Triple $N

    [Codeforces] Round #773 Div. 2

    요즘 코드포스를 돌리고 있는데, 어렵다,, Div2 4개 푸는 걸 목표로 달리고 있다만, 계속해서 ABC를 풀거나 ABE를 풀거나(???)... A. Hard Way 삼각형이 주어졌을 때, $(0, x)$ 점에서 삼각형에 닿지 않는 변의 길이를 구하는 문제이다. 그림을 몇 번 그려 보면, 삼각형의 한 변이 x축에 평행하고, 나머지 한 점이 그 변보다 아래에 있는 경우, x축에 평행한 변은 닿을 수 없다. 다행히 닿지 않는 변의 길이를 구하면 되니, 저 경우면 변의 길이를, 그렇지 않으면 0을 출력하면 된다. B. Power Walking $N$ 개의 파워업을 적당히 나눠서, 나눈 그룹마다 unique한 원소의 개수의 합을 최소화하는 문제이다. 이 때, $1$ 부터 $N$ 까지의 정수 $K$ 에 대해서, ..

    [백준 | BOJ] 문제풀이

    알고리즘 공부하는 소모임이 있다! 나도 감 잃지 않으려고 가입해서 공부는 계속 열심히 하려고 하는 중. 오늘 20-22시까지 문제풀이를 적어뒀는데, 기록해 두려고 블로그에도 공유. 문제 목록은 아래와 같다. A: 정육각형과 삼각형 https://www.acmicpc.net/problem/14264 B: 가희야 거기서 자는 거 아니야 https://www.acmicpc.net/problem/21771 C: Router https://www.acmicpc.net/problem/15828 D: 점프왕 쩰리 (Small) https://www.acmicpc.net/problem/16173 E: 쇠막대기 https://www.acmicpc.net/problem/10799 F: Ocean View (Large) h..

    [백준 | BOJ] Good Bye, BOJ 2021! 후기 및 풀이 (ABCD)

    백준에서는 연말에 굿바이 백준, 연초에 헬로 백준(굿모닝 백준) 행사가 있다. 2021 백준 마무리할 겸 문제풀이. 대회에서는 2솔브, 끝나고 CD 업솔빙까지 했다. A. 2021은 무엇이 특별할까? $N$ 범위가 $10,000$이다. 소수를 쭉 늘어놓고, 두개를 미리 곱해두고 이분탐색해서 풀었다. 사실 이분탐색은 필요가 없는데. 원소 개수가 30개가 안 된다. 배열을 한 바퀴 돌 걸. $N = 10,000$일 때 103까지 넣어둬야 하는데, 넣지 않아서 WA, 테스트한답시고 넣은 코드를 안 없애서 WA. 자잘한 실수를 많이 했다. 제출 전에는 꼭 체크하자. B. 예쁜 케이크 대회 중에는 OEIS의 힘을 받아서 풀었다. 손으로 줄줄 쓰다가 뭔가 규칙이 있는 것 같아서 넘겼다. 증명은 아래와 같다. $N ..

    [백준 | BOJ] 가희와 함께 하는 2회 코딩 테스트 후기

    저번에 재밌게 풀었던 시리즈 대회가 열렸다. 1회때와 같이 문제들이 재밌다. 처음 생각한 풀이와는 다르게 생각하는 문제들도 있었다. 1시부터 바짝 참여하지는 못했지만, 5문제를 풀었다. 풀이는 아래. 가희와 함께 하는 2회 코딩 테스트 www.acmicpc.net 1. 가희와 파일 탐색기 문자열 관련 문제를 풀 때면 파이썬밖에 못 하는 나를 조금은 이해할 수 있게 된다.. 단순 정렬 세 번으로 문제를 해결했다. 우선순위의 반대순서대로 정렬을 진행하면, 우선순위를 모두 만족하게끔 정렬할 수 있다. 파일명과 확장자로 나눠 입력받고, 지원하는 확장자들을 dict 를 통해 관리한 뒤, key 를 각각 확장자, 지원 여부, 파일명 순서대로 정렬을 세 번 한다. 2. 가희와 키워드 이 문제도 브루트포스로 해결했다...

    [2021 Dev Carnival] 데브카니발 2021 코딩테스트 금손 배지 후기 (문제 복기)

    goorm.io에서 진행하는 2021 Dev Carnival : 데브 카니발에 참가했다 ! 5월 22일에 진행됐던 코딩테스트였는데, 얼마 전에 테스트 결과가 메일로 날아왔다. 잊고 있었는데 다시 생각나서 글을 쓴다. 테스트를 하면서 작성한 코드를 따로 저장해두지는 않아서 정확한 코드를 가지고있지는 않다. 기억나는 대로 문제를 복기해봐야겠다. 1번 문제는 단순구현 문제였다. 사람마다 먹을 수 있는 음식 양이 정해져 있고, 음식을 순서대로 먹으며 양을 넘는 사람들의 순서를 출력하는 문제였다. 배열 돌려가면서 빠르게 해결했었다. 2번은 구현이 조금 힘들어보여서 3, 4번을 먼저 봤었다. 3번은 보자마자 DP라는 생각이 들어서 도망쳤고, 4번 문제를 붙잡았다. 단방향 그래프가 주어지고, 한 번 정점을 방문할 때..

    [백준 | BOJ] 가희와 함께 하는 1회 코딩 테스트 후기

    요즘 백준에서 문제를 좀 풀고 있다. 어려운 고급알고리즘보다는 대회나 코딩테스트에서 자주 보이는 알고리즘 위주로 연습하려고 한다. Codeforces의 Round나, 백준의 대회나, Atcoder의 Contest 모두 참 좋지만, 신분이 군인인지라 쉽게 응시하지 못하고 있다. 가희와 함께 하는 1회 코딩 테스트 www.acmicpc.net 오늘 괜찮은 시간대에 대회가 열려서 참가하게 됐다. 문제들은 재밌었고, 다양한 알고리즘들이 문제셋에 녹아있어서 이렇게저렇게 풀어보기도 했다. 공지사항에서 미리 "빠른 입출력"을 사용하라고 조언했었는데, 꽤 테스트케이스들이 무거운 모양이다. 파이썬으로 힘겹게 돌아갔다. 저번 숙명여대 SMUPC에서는 2문제만 풀고 대회를 마무리했었는데, 이번 대회에서는 8문제 중에서 6문..

    [프로그래머스 | Programmers] 월간 코드 챌린지 시즌2 5월 문제풀이

    프로그래머스에서 월간 코드 챌린지를 진행했다 ! 시간이 적절한 시간대에 잡혀서 여유롭게 참여할 수 있었다. 4월달에 한 번, 이번 달에 한 번이 시즌 2 챌린지였는데, 나는 이번 챌린지를 두 번째 대회가 돼서야 접했다. 두 번째 대회까지 총 8문제 중에 4문제만 풀어도 이벤트에 응모할 수 있다는데, 이번에 3문제를 풀면서 아쉽게 응모는 하지 못했다. 이번 달 챌린지에서는 6546명 중 53위를 달성했다 ! 개인적으로 DP가 굉장히 약한 편이라고 생각하는데, 이번 문제셋에서는 구현 / 그리디 / 자료구조 / 그래프 쪽으로 출제돼서 3문제를 맞았다. 1. 약수의 개수와 덧셈 약수의 개수가 짝수면 더하고, 홀수면 빼야 한다. 약수의 개수가 홀수인 경우는 제곱수인 경우이고, 수의 범위가 $1000$ 이니까 $3..