joseph0528 코딩 블로그

오랜만에 새로운 소식으로 글을 작성하게 되었다. 대학 입시를 마치고 최종적으로 gist에 입학하게 되었다. gist 들어가서는 평범하게 대학생활하다가 ucpc를 나가보고 싶어 학교에서 팀원을 모아서 나오게 되었다. 사진에 보이는 거처럼 에타에 구인글을 올렸다. gist 가 ps판이 활성화가 안되어 있다 보니 사람 찾는 게 힘들었고, 그래서 많은 사람들이 볼 수 있는 에타에 올렸다. (많은 분들이 칭찬을 해주셔서 기분이 좋았다 ㅎ) 그렇게 어찌저찌 팀원 3명을 모으게 되었다. 다른 친구들의 정확한 프로필을 알 수 없지만 정황상 내가 가장 잘하는 포지션에 있음을 알게 되었다. 그래서 혼자 다 풀 생각으로 대회에 임해야겠다고 생각을 했고, 시험이 끝난 직후 일주일 동안 DOJ와 ucpc 기출에서 골플 문제를..

[📣 ACPC 2026 (AWS x Codetree) 전국 대학생 프로그래밍 경진대회 안내] AWS 코리아 × 코드트리 주최, IOI·ICPC 출신 코드트리 팀이 직접 문제를 출제하는 전국 대학생 프로그래밍 경진대회가 올해에도 열립니다! 📌 대회 개요- 참가 자격: 대학교, 대학원 재·휴학생, 전공·학년 무관- 오프라인 본선: 8/2(일) AWS 코리아 본사- 사용 언어: C/C++, Java, Python, JavaScript 🏆 시상- 본선: 1등 200만 / 2등 100만 / 3등 50만 / 특별상- 예선: 성적 상위 10명 각 10만 원 🎁 본선 진출 전원: (1)AWS Kiro 구독권 (2)기념 티셔츠, 메달 (3)참여 기업 굿즈 (3)인증서 (4)IOI·ICPC 수상자 출신 주최진, 전..

문제를 풀기에 앞서, 문제에 대한 설명 하겠다. 이 문제는 n과 k가 주어지고 이후 n 줄에 걸쳐 점의 좌표가 주어진다.이때 n개중 k개를 제거해 n-k 개의 점에 대해 직선 y=ax+b에 대해 y좌표 차이가 최소가 되게 하는 거리를 구하는 문제다.즉 n-k개의 점을 고르고 다양한 y=ax+b를 그려보면서 거리 차이가 최소가 되게 하는 y=ax+b를 찾고, 그때의 거리를 구하라는 문제다. 위 그림은 예제를 좌표평면에 나타낸 것이다. 4개의 예제 중 k = 0 일 때를 알아보자.k = 0 은 모든 점에 대해 거리가 가장 가까운 점을 찾는 것이다.이때 답은 그림에서 나타난 두 직선의 중앙에 있는 직선이 된다. 그럼 이제 문제를 해결해 보자.문제를 해결하기 위해선 크게 2가지를 해결해야 한다. 1. y = ..

이 문제는 내용 자체는 간단하다.트리가 처음에 주어지고, 쿼리로 2가지 입력 중 하나가 들어온다. 1번 쿼리는 트리의 정점 u에서 정점 v로 이동하는 경로에 u부터 0, 1, 2, 3 ... v에 k을 더하는 쿼리다.2번 쿼리는 각 정점에 대해 얼마의 값이 더해졌는가, 그 합을 구하는 쿼리이다. 위 트리는 예제에서 제공하는 트리다.예제에 나온대로 쿼리를 진행해보자. 일단, 맨처음 1 3 5 쿼리가 주어진다. 3에서부터 5까지 0부터 k까지를 더하는 것이다.1번 쿼리를 진행하면 다음과 같이 될 것이다. 2번 쿼리는 1 4 5 이다. 이도 맞찬가지로 진행해주면,다음과 같이 만들어진다는 것을 알 수 있다.4에서부터 시작했기 때문에, 4에는 0, 3에는 1, 2에는 2, 5에는 3을 더해준 모습이다. 다음 쿼..

이 문제는 "정보과학관"이라는 곳에서 출발해서 D번째에 다시 "정보과학관"에 있을 경우의 수를 구하는 문제다.D가 작다면 DP 를 이용해 풀어주면 되지만, 이 문제는 D가 10억까지 제공된다. 그럼 어떻게 풀 수 있을까? 우리는 여기서 모든 정점 간의 거리가 같음을 이용해야 한다. 위 그림은 문제에서 제공된 그림이고, 숫자는 각 정점에 부여해준 번호이다. 이제 위 그래프를 가지고 DP를 생각해 보자. DP [n][d] : n까지 오는데, d만큼 소요될 때 경우의 수 라고 DP를 정의할 수 있다. 그리고 n이 작으니 각 정점별로 DP 식을 정리해 보자. DP [1][d] = DP [2][d-1] + DP [3][d-1]DP [2][d] = DP [1][d-1] + DP [3][d-1] + DP [4][d..

문제를 요약하면 정의역 X={1,2,3 .... n} 에 대한 함수가 있고, c와 r 이 주어지면 f^c(r) 을 구하는 문제이다.f^c(r) 은 f 를 c번 합성하고 r 을넣은 함수다. 이와 같이 문제에 잘 나타나 있다.이때 1500번의 쿼리 안에 f^c(r) = c 를 만족하는 c와 r을 출력하면 된다. 이를 어떻게 풀 수 있을까? 여러 풀이가 존재하지만 이 문제는 놀랍게도 O(1) 에 해결할 수 있다. 함수 f를 생각하면 어떤 함수가 주어지더라도 c=n 이라면 최소 한번 이상 사이클이 돌게 될것이다.이는 자명하니 넘어가겠다. 이에 대해서는 몇가지 예제를 만들어보면 금방 알 수 있다. 그 이후 c=n과 임의의 r 을 제공했을 때 받은 값을 우리가 찾고자 하는 c라고 하자.그러면 우리는 이 값으로..

2024.06.01 자율주행차 제작 A to Z 시작 SW 미래채움에서 자율주행차 제작을 해보면서 자율주행차 만드는 거에 관심이 생겼다. 키트를 만드는건 재미없을 거 같아서 실제 사람이 탈 수 있는 자율주행차를 만들어보고자 한다.기획서도 만들었다.엄청나게 큰 프로젝트이기 때문에 혼자선 할 수 없다고 생각했고, 팀프로젝트로 진행해야겠다는 생각을 했다. 팀프로젝트라면 나뿐만 아니라 다른 친구들도 이점이 있어야 되니 각자가 원하는 방향성을 최대한 추구할 수 있게 프로젝트를 기획했다. 오늘 2024년 6월 1일부터 언제끝날지 모르겠지만 자율주행차 제작 일지?를 작성해보자.2024.06.04팀원 모집 오늘은 팀원을 뽑기 위해 신청 폼을 만들었다. 소프트웨어는 내가 한다고 해도, 하드웨어는 잘 모르니까 잘하는 친..

이 문제는 8 * 8 사이즈의 맵에서 특정 위치에 비료액을 뿌리는 자동 분무기 혹은 제초제를 뿌리는 자동 분무기가 위치해 있다.비료액 분무기는 해당 위치에서 십자가 모양으로 값을 1씩 더하고, 제초제 분무기는 해당 위치에서 십자가 모양으로 1씩 뺀다.예를 들어 위의 맵에서 X와 Y에 분무기가 있다고 할 때, X는 {a, b, c, d, e, f, g, h, i, j, k, l, m, n}에 영향을 미치고, Y는 {A, B, c, C, D, E, F, G, H, I, J, k, K, L}에 영향을 미친다.X가 비료액 분무기, Y가 제초제 분무기라고 한다면 문제에서 주어지면, 문제의 입력은 아래와 같이 주어지게 된다.이렇게 맵이 주어지면 분무기의 위치와 상태를 파악해서 맵을 출력하면 되는 문제다. 여기서 우..