pseong

Problem - E - Codeforces codeforces.com 간단한 문제지만 업솔빙에 시간이 좀 걸려서 정리. 최소의 비용을 찾기 위해선 d(a)가 작아져야하고 m(a)가 커져야 한다. 잘 생각해 보면 m은 d보다 커질 수 없다. m이 커지려면 0부터 m-1까지의 숫자가 배열 a에 존재해야 한다.0부터 m-1까지의 숫자가 존재하면 d는 m이 되어버리기 때문이다. 반대로 d는 m보다 커질 수 있다. m보다 큰 숫자가 존재하면 d의 값이 1이 증가하기 때문이다. 결국 문제를 요약하자면, 배열 a에서 m값보다 큰 숫자 종류의 개수가 문제에서 정의하는 비용이다. m값보다 큰 숫자 종류를 줄이기 위해서는 m값을 크게 키우면 된다. 이는 배열 a의 어떠한 값을 m으로 바꿔 준다면 m값은 1이 증가하게 된..

Problem - C - Codeforces codeforces.com 쉬운 문젠데 어마어마한 실수를 했다. 기존 배열을 복사를 해서 1번째 행부터 n번째 행까지 확인하면서 스왑 할 두 개의 인덱스를 찾으면 되는데 중간쯤에 스왑해야 하는 부분을 찾으면 이전 행에도 적용해야 하는걸 간과하고 이후에만 스왑을 적용했다. 결과적으로 테스트 케이스는 맞았으나, 당연히 저격 데이터는 있을 것이고 그렇게 틀렸다. 맞왜틀 하루하고 버리고 오늘 다시 봤는데 이런 어마어마한 실수였다. 이전 사건에도 영향을 미치는지 잘 판단해야 할 것 같다.

2022 인하대 프로그래밍 경진대회를 참여했다. 결론은 3등을 했다. 이번 대회는 개인 대회이고 처음으로 오프라인 대회를 진행했는데 노트북으로 하다 보니까 좀 시행착오가 많았다. 정신도 많이 없었고. 그래서 중간에 등수보니까 아예 20위 아래로 밀려나서 보이지도 않았다. 하지만 멘탈 잡고 천천히 풀다 보니 10문제 중에 7 솔브를 해서 3위까지 올라왔다. 사실 지금 생각해보면 전부 쉬운 문제이긴 하다. 정말 PS는 쉽지 않다. 쉬운 문제라도 막상 대회에서 보면 머리가 잘 안 돌아간다. ㅋㅋ 일단 하루정도 쉬고 다음 대회인 UCPC 랑 ICPC 그리고 이번에 입상해서 생긴 shake 경인지역 대회도 잘 준비해야겠다. 근데 지금 생각해보면 운이 좀 좋았던거 같다. 대회 종료 2시간 전에 F번 풀이가 번뜩하고..

Problem - D - Codeforces codeforces.com 그냥 구현 문젠데 어려워서 정리 잘 관찰만 하면 되는데 그게 어려운 문제 행과 열을 각 각 따로 계산해서 더해줘야 한다. 행에서는 m개의 요소가 계속 돌면서 채워주기 때문에 행 카운트는 항상 단조 증가한다. m개의 요소가 계속 돌기 때문에 만약 안 채워져 있으면 카운트를 1 증가시켜주고 채워주면 된다. 열에서의 관찰이 조금 어려웠는데 일일이 1이 들어오는 경우의 수를 따지다 보니까 굉장히 문제가 어려워졌다. 사실 열에서도 m개의 요소가 사이클을 도는 건 맞지만 한 번 돌 때마다 새로운 m개의 요소가 앞에 추가가 된다. m개의 요소가 사이클을 도니까 m번마다 열 카운트가 반복될 것이다. 반복될 때마다 새로운 요소 한 줄이 맨 앞에 붙으..

F - Ignore Operations AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp dp [i][j] : i개까지 문자를 봤을 때 변환되는 문자의 길이를 j라고 할 때의 경우의 수 라고 놓고 문제를풀면 잘 풀리지만 최적화를 해야 풀린다. 그냥 dp 채우면 O(N^3)이다. 1. 1차원 또는 2차원 또는 3차원 dp 상관없이 dp를 바텀업으로 채울 때 중간에 어떤 연속적인 값을 더하는 구간이 존재한다면 dp를 채우면서 prefix_sum을 이용하면 연속적인 숫자의 방향의 개수에 따라 그 개수만큼 시간 복잡도의 차수를 줄..

F - One Fourth AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 신발끈 공식을 사용하면 한 포인터가 움직일 때마다 계산이 가능하기 때문에 투 포인터로 둘 다 왼쪽부터 탐색하면 될꺼라고 생각했지만 구현에서 조금 문제가 있어서 틀리게 됐다. 중요 포인트는 2가지를 기억하면 된다. 1. 신발끈 공식을 사용하면 맨 마지막 곱셈은 다음 첫번째와의 곱로 넘어가게 되는데 무식하게 그대로 구현했다. 첫번째 점을 원점으로 맞춰주면 더해줄때 마지막 곱셈은 안해도 된다. 이렇게 되면 포인터가 움직일 때마다 크로스곱 한번만 하면 돼..

드디어 백준 다이아를 달았다. 하지만 실력은 다이아가 아닌 듯하다. 최근에 PS에 대해 깨달은 것이 있어서 당분간 백준은 잠시 접어두고 리트코드와 코드포스를 주로 풀 계획이다.

사실 어려운 알고리즘 중에서 세그먼트 트리만 제대로 쓸 줄 안 다면 정말 정말 편하다. 세그 문제가 아닌데도 세그로 풀리는 문제가 많기 때문이다. 세그먼트 트리만 깊게 파서 나쁠건 없다고 생각한다. 공부 대비 가성비가 정말 좋은 알고리즘 이다. 세그먼트 트리의 구조 세그먼트 트리는 간단하게 부모의 노드가 자손의 노드들 중 리프 노드를 관리한다고 생각하면 된다. 만약 입력값이 1부터 6까지 주어졌다고 생각해보자. 세그먼트 트리의 모양은 아래와 같다. 노드1 : 인덱스 1부터 6까지 관리하는 노드 노드2 : 인덱스 1부터 3까지 관리하는 노드 노드3 : 인덱스 4부터 6까지 관리하는 노드 노드4 : 인덱스 1부터 2까지 관리하는 노드 노드5 : 인덱스 3부터 3까지 관리하는 노드 이렇게 구간을 절반씩 나눠서..