황현석 일지

문제 링크https://www.acmicpc.net/problem/1146 문제 풀이 일단 수는 1부터 $N$까지 하나씩만 사용하면 된다. 일단 수열을 만드는 조건을 조금 단순화 시켜서 시각화 해보면,3번째 수를 2번째 수보다 큰 수에서 골랐다면, 그 다음 4번째 수는 3번째 수보다 작은 수, 그 다음은 4번째 보다 큰 수 이런 식으로 지그 재그 모양으로 고르게 된다. 이런 식으로 지그재그 모양으로 고르게 된다. 여기서, 우린 dp로 경우의 수를 구해 줄 수 있다. $N$개의 수가 있을 때, 우린 최초의 수 $a$를 선택해보자. 그 다음 수 $b$를 선택하면, 우린 $a \rightarrow b$로의 수열을 일단 만들 었고, $b$에서 $a$로의 역방향 ($a$에서 $b$로의 증감 반대) 으로 시작하는 ..

문제 링크9616번: 홀수 정사각형 (acmicpc.net) 문제 풀이 자 문제에서는 $N, \; M$을 주지만, 일단 $N$과 $M$에 각각 1씩 더해서, $N \times M$ 격자점에서 사각형을 만드는 것으로 바꾸자. 일단 쉽게 한 변의 길이가 홀수인 정사각형을 평면에 맞게 평행하게 몇 개 만들 수 있는지부터 계산해 보자. 한 변의 길이가 $2i - 1$인 정사각형은, 격자점이 총 $(2i) \times (2i)$개가 필요하다.  그리고 수식으로 나타내면, 가로로는 $N - 2i$ 번, 세로로는 $M - 2i$번 움직 일 수 있다.그리고 한 변이 먹는 격자점은 $2i$개 이므로, 이것이 $N$ 이나 $M$을 초과 하면 안 된다.$$2i \leq \min(N, M)$$$$i \leq \bigg\lfl..

오늘도 어김없이 버츄얼을 한판 돌렸다. 바쁘거나 그러지 않으면, 밤 10시쯤에는 버츄얼을 무조건 돌리고 있다.오늘은 성적이 역대급이지만, 버츄얼이라 그런지.. 오히려 좀 슬프다..  A. Verify Password 이 문제는 보자마자 좀 짜증이 났다... 저걸 언제 다 구현하지...그래서, 문제에서 요구하는 데로 Comparator를 하나 만들고, 정렬시킨 다음 똑같은지 비교했다.  B. Increase/Decrease/Copy$A$ 배열의 원소를 1, -1씩 연산해서 $B$배열을 만드는 최소 연산 횟수를 묻고 있다.근데 $B[N]$도 주어져서 $A$배열의 원소를 하나를 복사해 와야 한다. 최대한 가까울 때 복사해서 만들면 된다.. 간단한 구현이다.. A문제보단 쉬웠다. 구현만 하면 됐다.근데 한번 틀..

컨디션이 좀 안 좋았는데, 콘까지 말아먹으니까, 기분도 안 좋아졌다. 지문을 잘못 읽은 게 제일 컸다. 거의 모든 지문을 잘못 읽었다.  A. Strong Password 일단, 문자열 어디에든 한 개를 삽입할 수 있다고 지문에 나와있지만, 진짜 지문을 날려 읽었다.이 부분만 읽고, "아 맨 앞이나, 맨뒤 하나? 그냥 브루트 포스를 하라는 건가?"라고 접근했고, 정말 앞뒤에 한 개씩 붙이는 52시도 브루트포스를 구현했다. 당연히도, 틀렸고, 정말 당황해서, 지문 다시 읽고 제대로 풀었지만, 코딩미스를 한번 해서 2번 틀렸다.  B. Make Three Regions 인접한 행과 열 그리고 접근 가능하다면, 하나의 컴포넌트로 묵는다. 문제는 한 블록을 막을 수 있을 때, 컴포넌트가 총 3개 되는 그런 블록..

한동안 PS를 안하고, 여러 가지 개발공부를 시작했다. HTML + CSS + JS 를 일주일안에 켠왕을 한다던지, 선형대수학을 한번더 파본다던지, 다양한 분야를 탐닉중이였다.  (아무것도 안하니, 뭐든 해보자는 생각이었다..) 그래도 코포는 무조건 꾸준히 참가해서 이런 환경의 문제를 푸는 것에 익숙해지려 했다. 이번 결과는 그래서, 4솔도 못했다. 4번째 문제는 심지어 레이팅이 낮았던 문제라서, 푸는 내내 당황만 계속했던 것 같다. A, B, C는 보자마자 어떻게 풀어야 할 지 알았고, 그냥 한 번에 통과할 수 있도록 예외정도만 잠깐씩 깊게 살펴봤었다.D에서 그냥 막혔다. A, B, C는 보자마자 정답이 튀어나왔는데, D에서 갑자기 난이도가 수직 상승해서, 무지 당황했다... 중간 중간.. 이건 쉬운문..

문제 링크Problem - D - Codeforces Problem - D - Codeforces codeforces.com  문제 풀이 평소에 그냥 딱 하고 풀리던 Dp문제들과 다르게 조금 오래걸려서 풀이를 쓰면서 익숙해지려고 한다. 왜 풀리는지 살짝 이해가 안 돼서 써보면서 나도 이해하려고 한다. 일단 Alice 는 케이크를 무조건 가중치가 적은 것부터 먹는 게 유효한 전략이다.따라서, 배열의 값들을 잘 압축하고, 갯수를 세서 재정렬한다. 즉, {4, 6, 1, 3} 이와 같이, 가중치가 낮은 순으로 정렬해서, 개수만 나는 담았다. 그럼 Bob이 Alice를 방해하는 전략이 중요하다. 근데, 전략이 유효한 전략이 없어서, 다이나믹 프로그래밍으로 모든 경우의 수를 적절하게 시행해야 한다. 이 시행방법을..

A, B는 대부분 지문 이해하는데 시간을 사용했고, 지문을 이해하자마자, 풀이가 떠올랐다. 1년 전에는, 초반 두 지문 푸는데만 30분가량을 소모했는데, 이젠, 10분 만에 두 문제를 풀정도가 되었다. (군대 가서 아무것도 안 했다.) C는 보자마자, 자료구조가 떠올랐다. $i$ 번째 배열에서 모든 $L \leq i$에 대해, 구간 $[L, i]$ 의 정답을 그때 그때 알아내면 되겠구나라고 생각이 매몰되었고, 그럼 모든 출발지점에서부터 $A[i]$ 값들을 더해주며, $X$를 넘으면, 다 0으로 보내자라고 생각을 했다. 내게 가용가능한 스플레이트리 템플릿이 없었기에, rotate() 랑 splay()만 복붙 해서 가져온 다음, 하드코딩을 했다. 당연히 구현이 힘들므로, 50분이나 잡아먹었다. D. Funn..

Notion – 자료구조 및 알고리즘을 정리하고 있습니다. Algorithm | NotionProblem Solving에 주로 등장하는 알고리즘들을 사용하기 편하게 구조화, 함수화 해놓았습니다.hy3ons.notion.site 해당 노션 사이트에 알고있었던 알고리즘을 다시 풀어볼 때마다, 따로 템플릿을 만들어서, 넣어두고 있습니다.전역(24. 7. 16) 하고 나서부터 작성하기 시작해서 아직은 뭐 없지만, 점점 늘려가겠습니다. 참고하셔도 돼고, 배끼셔도 됩니다. 알고리즘 템플릿이라고 적어놧지만, 특정 문제를 푸는 소스코드가 그대로 쓰여진 것도 있습니다. 아직은 몇개 안적어서, 서식도 없고, 일단은 적기라도 시작하면서, 정리 좀 하자라는 마인드입니다. 제가 워낙 정리하기 귀찮아 하고, 템플릿 없어서 손해본..