8월 5일부터 일정이 있어서 PS를 당분간 못할 가능성이 높다. 1557 제곱 ㄴㄴ 더보기 기회가 되서 풀게 됐다. 옛날엔 감도 안잡힐 정도로 어려운 문제였는데 지금은 쉽게 풀이가 떠오르는게 기분이 매우 좋다. 내 풀이는 DB 풀이인데 Segmented Sieve를 사용한다. https://www.acmicpc.net/problem/1016 를 풀고 나면 적당한 min, max만 찾으면 된다는 생각을 할 수 있다. 그 min,max를 구하기 위해 구간을 적당한 블록(2*10^6 정도)로 나눠주고 각 블록의 제곱 ㄴㄴ수의 개수를 구하는 것이다. 미리 전처리를 해놓고 (블록의 크기에 따라 다르겠지만 나의 경우 2000개의 수를 저장) 구간을 찾은 뒤 만들어놓은 체로 K번째 제곱ㄴㄴ수를 구해주면 된다. 내 풀..

UCPC에서 맞고 나니 정신이 차려져서 게임도 끊고 PS에 다시 집중하기 시작했다. 브론즈5 올솔 더보기 모든 제출은 Python 및 Text로 했다. 비하인드를 말하자면 고등학교 문제 수 랭킹이 2등으로 밀려 있길래 랭킹작을 했다. 문제 빨리, 정확히 푸는 연습하는 겸, 파이썬 연습하는 겸 밀었다. # import sys # input = sys.stdin.readline N=lambda:int(input()) M=lambda:list(map(int,input().split())) P=print # from functools import reduce if __name__ == "__main__": A = N() 이건 내 파이썬 문제풀이 템플릿. 풀면서 reduce, filter, map을 굉장히 많이 ..

2409 더보기 백준에 있는 USACO 중 가장 오래된 문제 17일날 꽂혀서 계속 풀고 dfs+커팅이라는 정보를 얻어서 ( = 완전한 해답이 없다) 커팅 방향으로 계속 풀이를 고쳐나가는중이다. UPD: 7/21 AC 어찌저찌 풀이를 짜다가, dfs 탐색의 횟수를 제한시키는 방법을 떠올리게 되었다. 커팅이라 보기에도 애매하고 이게 무작위 데이터에 대해 돌아갈지 또한 전혀 정확하지 않은 방법이지만 배열을 랜덤셔플하면 최소한 사람이 추가할 수 있는 데이터 내에서는 돌아갈 수도 있다는 생각이 든다. 내가 푼 시점에 총 3사람이 풀었더라. 분명 문제 풀기 전에 봤을 때 한 사람이 1730ms? 이정도로 통과해있었는데 내가 풀고 나니 사라져 있었다. 계정을 지웠거나 지워진건가? 다른 두 사람의 코드를 터트리고 싶다..

15940 더보기 본선 팀연습 때 jjaewon9와 함께 해결한 문제. 트리에서 각 간선에 대해, 그 간선이 나누는 두 서브트리의 지름을 빠르게 구해 문제에서 원하는 최댓값을 갱신해주면된다. 루트를 하나로 고정해두면 이제 루트가 아닌 각 정점에 대해 그 정점이 루트인 서브트리의 지름과, 이 서브트리의 여집합 (정점의 부모로부터 이어진) 트리의 지름을 구하면 된다. 서브트리의 지름을 구하는 방법 중 dp 방식이널리 알려져 있는데, 각 서브트리에서 루트로부터 가장 먼 정점과의 거리를 저장해 두고 max( max(dp(자식)), max(가장 긴 2개 다리 길이의 합))을 구하면 된다. 아래 지름을 dpD, 위 지름을 dpU에 저장하자. dpU를 구하는 방법도 dpD와 비슷한데, 정점과 부모를 고정하고 생각하면..

1년 간의 휴식을 끝나고 참가하는 첫 대회 icpc팀원인 sean9892의 제안으로 jjaewon9와 팀을 이루었다. 셋 다 약 1년의 휴식을 가지고 있어 걱정반, 오랜만의 PS라 설레임 반이였는데 팀원들이 잘 이끌어준 덕분에 연습과 예선을 성공적으로 마무리할 수 있었다. 팀명을 비롯한 대회 참가 내용의 99%는 아래 두 글의 합집합에 있다. https://sean9892.tistory.com/22 https://jjaewon.tistory.com/29

https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 이 문제는 Exchange Arguments의 전략을 쉽게 발상할 수 있는데, (문자열 A,B에 대해 AB>BA?) 인접한 것끼리만 교환한다고 생각하면 AB > BA 일 경우 X AB Y > X BA Y 이기 때문에 인접한 걸 계속 이득이 되도록 교환해나가면 최종적으로 가장 이득인 상태가 되는 것을 알 수 있다. 이는 결국 버블정렬을 시행하는 것과 같은데 N lo..

문제풀이 사이트(집중) Codeforces 백준 UCPC 기출 ACM-ICPC ACM-ICPC 서울 리저널 튜토리얼 https://www.geeksforgeeks.org/how-to-prepare-for-acm-icpc/ https://blog.shahjalalshohag.com/topic-list/ https://usaco.guide/ 라이 알고리즘/문제 목록 https://cp-algorithms.com/ https://csacademy.com/contest/archive/ https://cses.fi/problemset/ 동아리 2022 Spring Worksheet https://codeforces.com/gym/103470 https://codeforces.com/gym/103430 https:..

상위 100개 문제를 다이아 이상의 문제로 채웠다! 공부하고 연습한 기록이 이만큼 쌓여서 뿌듯하다. 이제는 사고력을 키워보자. 스스로 사고해서 문제를 풀어내는 것이 재밌어지는 그날까지 연습!

https://codeforces.com/blog/entry/91363 I compiled a list of almost all useful blogs ever published on Codeforces [update: till 04.06.2021] - Codeforces codeforces.com 너무 좋다! ㅎㅎ 코드포스 공부할 때 정말 최고

http://kocw.or.kr/home/search/kemView.do?kemId=1346284 KOCW에 이런 좋은 자료가 있다는 것에 감동 받았다. 6장 매칭과 커버에 좋은 내용이 많다.

2021년 7월 31일까지 PS에서 실시함. https://www.acmicpc.net/group/9175 p.s) 원래는 개인적으로 진행하던 프로젝트였으나, 때마침 cgiosy와 뜻이 맞아 격일로 플*2 +다5*1 // 플*1+다5*2 문제풀이를 실시한다. Routine: 매일 아침 저녁 내일 문제 3개 프린트 + 다음 날 문제 풀이 20210531: 10124 다5 더보기 Merge Sort Tree와 Small To Large의 아이디어를 차용해서 풀었다. O(N log^2 N) 각 Value 1~N에 대한 인덱스를 저장해서 벡터를 만들고 Merge Sort Tree를 만든다. 포인터를 이용해서 구현했고, 별도로 좌표압축 또한 하지 않았다. 포인터 안쓰는 구현으로 바꾸면 더 빨라진다 풀면 보세요: ..

구간이 올바른 괄호문자열인지 판정하는 쿼리, 구간 문자 뒤집기 '(' ')' 업데이트 쿼리 모두를 O(log N)에 처리하는 세그먼트 트리 C. Sereja and Brackets : 업데이트 X 17407 괄호 문자열과 쿼리 : 점 업데이트 19851 버거운 버거: 구간 업데이트 일반적으로 사용하는 세그 트리의 노드의 종류는 2가지다. 레이지 값은 별도로 저장한다고 가정한다. 1. 구간합과 최소,최대 저장 앞서 '('를 1, ')'를 -1로 모델링했을 때 [a,b] 부분문자열이 올바른 괄호문자열일 조건은 $Sum([a,b]) = 0$ 이고 $Min(Sum([a,i])) >= 0$임을 언급했다. 이를 이용하기 위해 노드에 구간합과 최솟값을 저장한다 만약 구간의 문자를 뒤집을 경우 최솟값이 구간합의 최댓값..

세그 트리 문제를 다시 풀고 있다. 구현에 초점을 맞췄음. 2021.01.23 - [Problem Solving] - 머리로만 문제 풀기 글에 있는 문제들 중 세그 카테고리 문제들을 구현해봤다. 9623 부분 수열의 길이 처음에는 플4라는 게 믿기지 않았던 문제. 업데이트가 없기 때문에 누적합 배열로 구간의 합을 나타낼 수 있는 것이 핵심. 기본적으로 스위핑인 것은 잘 보인다. 끝점 i를 고정시키고 시작점 j+1중 가장 뒤에 있는 것을 찾는 느낌 $0

최근 희자님이 금광을 풀기 위한 연속합 세그먼트 트리를 공부하셨다고 한다. (heeda0528) 볼 때마다 풀고 싶었지만 귀찮아서 넘겨왔던 ㅋㅋ 그런 문제다. 그런데..! 희자님 코드가 너무 깔끔한 나머지 최대 연속합 세그를 구현해보고 싶은 욕구가 생겼다..! 30분 정도 시간 투자해서 2달만에 세그를 짜봤다. - 코드 잘된 구현을 봐서 그런지 생각보다 간단했다! 그리고 내가 왜 그렇게 이 연속합 세그를 귀찮아 했는가 생각을 해보니.... 작년 이맘때 2020년 3월 코드업 1등님한테 한 질문 中 3일을 꼴아박아서 꾸역꾸역 연속합 세그를 만들어냈는데 보다 시피 코드 상황이 벌써 끔찍하다. 세그 3개라니 OTL 이제 그 당시에는 뿌듯해서 굳이 새로운 코드를 찾아보지는 않았는데, 이게 내게 정말 큰 충격으로..

JOI 깃발 캬 ㅋㅋㅋㅋㅋ 오늘 정말 행복하다! 신이 많이 도와주시는군 >ㅇ< 기차 타면서 내내 이 문제의 구현에 대해 생각했는데 저녁 10시 25분 경에 드디어 구현에 성공했고, 3484ms 라는비범한 시간에 내 코드가 1트만에 통과하는 기적을 목도했다. 구사과님한테 어그로 끌려서 이 문제를 풀게 되었는데 끌리기 정말 잘했다는 생각이 든다!! 메모 1. 적어도 1개 이상이라는 조건은 매우 더럽다. 여사건을 이용하자. 2. 비트 필드 dp를 할 거다. M개의 비트를 들고 다니자. 3. 현재 넣을 알파벳이 'J' 나 'O'라면 위에는 아무 상태나 넣어도 된다. 4. 현재 넣을 알파벳이 'I'라면 바로 위가 'JO'인 상태는넣으면 안된다. 5. J와 O를 같은 비트(0)으로 취급할 건데, 맨 첫번째 비트는 ..

1. Palindrome DP 팰린드롬https://www.acmicpc.net/problem/1243 팰린드롬의 개수https://www.acmicpc.net/problem/1204 팰린드롬 문장https://www.acmicpc.net/problem/1054 N개의 문자열을 붙여 만들 수 있는 팰린드롬의 개수를 구하는 유형. 1054는 단어를 1번씩만 사용 가능한 것이 차이점이다. dp 상태를 정하기에 앞서 관찰을 해보면 항상 dp는 한 단어를 정하고 이를 사용하는데서 시작한다. 단어를 앞/뒤에 번갈아 붙이게 된다. 첫 단어 이후부터는 조건이 생긴다. 가령 abcd라는 단어를 골라서 앞쪽에 붙였다고 하면 뒤쪽에 dcba를 접미사로 가지는 문자열이나 dcba의 접미사인 문자열만 뒷쪽에 붙일 수 있다. ..

Bit Scrolling DP 문제들 밀기 정말 재밌는 알고리즘이다. 두부 모판 자르기가 입문으로 가장 좋은 듯 감 안 오면 휘님 블로그 풀이 보세요~ https://www.acmicpc.net/problem/10937 10937번: 두부 모판 자르기 KOI 두부 공장에서 만들어내는 크기가 N × N (N ≤ 11)인 두부모판이 있다. 이 모판을 1×1 크기의 단위두부가 2개 붙어있는 형태의 포장단위(즉, 1×2 혹은 2×1 크기)로 잘라서 판매한다. 그런데 두부 www.acmicpc.net https://code.sasa.hs.kr/problem.php?id=2143 SASA OJ discuss3 세종이는 자신의 동생, 제인이와 블록을 채우는 놀이를 하고 있다. 세종이는 제인이의 두뇌를 말랑말랑하게 만..

파이썬에 '한글 변수명'을 사용 가능하다는 사실을 알고 있는가? 이 사실을 망각하고 있다가, 기억나서 당장 BOJ 1000번 A+B 문제를 풀어보았다. def 입력(): return input() def 출력(변수): print(변수) def 맵(함수,리스트): return map(함수,리스트) def 정수화(변수): return int(변수) 에이,비 = 맵(정수화,입력().split()) 출력(에이+비) 코드포스할 때 미리 자주 사용하는 함수들을 템플릿화 시켜놓는 것처럼 한글 템플릿을 미리 만들어놓으면 한글 프로그래밍도 더 이상 꿈이 아니다. ㅋㅋ!

1. Class 3까지 금장 Class 3의 남은 문제들을 전부 해결하므로써 금장을 땄다. 2. 0/1 BFS 기억할만한 요소 https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 0/1 BFS 문제로 접근했다. 그리고 0/1 bfs를 그동안 잘못 구현하고 있었다는 사실을 깨달았다. 가중치가 0 또는 1뿐이므로 0의 가중치를 가진 간선을 연결할 때는 dq의 front에, 1의 경우는 dq의 back에 p..

1. Class 2 남은 문제들을 땀 자투리 시간을 쓰면 굉장히 많은 일들을 할 수 있다. 생각보다 오래 걸리기는 한다. 실버 문제를 10분씩 걸림. 2. KOI 수상 확인 동상. 아쉽다. 미친 듯이 아쉽다. 옛날처럼 내 자신에게 화가 나고 그러지는 않다. 다른 내신 과목들을 챙기기 시작했고, 난 그걸 실천했으니. 다시 내가 좋아하는 PS 시작할거고 ACM ICPC 국대를 노린다.

1. PS 다시 시작 삶의 활기를 되찾기 위해 PS를 다시 시작한다. //Always Do Your Best Ku! #include using namespace std; #define all(v) (v).begin(),(v).end() #define nl '\n' #define sp ' ' using ll = long long; using pii = pair; #define dbg(X) cerr

Special Thanks to Cgiosy Slope Trick: 함수 개형을 이용한 최적화 백준 13323 BOJ 수열 1 풀이 백준 13324 BOJ 수열 2 풀이 *20210513 수정#1 2021/05/13 정보과학세미나 시간에 보고서 및 발표자료의 내용으로 사용함. WhiteBoard Tutorial BOJ수열1 BOJ수열2

퀴즈를 보고 나서야 이 과목에 대한 열정이 생겼다. 나라는 인간은 꽤 엄청난 (그러나 해결 가능한) 자극이 주어질 때 그때서야 어떤 분야에 흥미를 느끼나 보다 교과우수 각이 나왔다~ 자만하지 말고 재밌게 해보자 UPD) 1문제 틀렸다. 다 푼건데 입력을 잘못 받아서 틀렸군 급할 수록 차분하게 지내자. 매일 되새기고 있음. 탁구도 마찬가지다. 1. 공보고 치기 2. 차분하기 3. 몸을 움직이기 UPD) 2문제 틀렸다. 조만간 이곳에 주어진 문제와 이를 해결하는 코드를 올릴 것이다.

gratus907.com/74 BOJ 1557 제곱 ㄴㄴ / BOJ 8464 Non-Squarefree Numbers 난이도 : Solved.ac 기준 다이아 5 사실상 거의 같은 문제인 1557과 8464는 둘 모두 Square Free Number의 개수에 관한 문제이다. 풀이는 1557을 기준으로 설명하고, 마지막에 8464에 적용하는 것은 간단하다 :) gratus907.com codeforces.com/blog/entry/53925 [Tutorial] Math note — Möbius inversion - Codeforces codeforces.com codeforces.com/blog/entry/54090 [Tutorial] Math note — linear sieve - Codeforces ..

보호되어 있는 글입니다.

(학교 정보과학프로젝트 시간에 만들었다고 아무도 말하지 않았습니다.) || || || V 사진을 입력하면 사진에 웃는 형태의 틀을 덮어 씌워 준다. 본격 Pic2Face 메소드 이 버전은 검은색이 주류인 사진은 사용할 수 없다. //Full Code : http://colorscripter.com/s/STJKOfy inline void Gradient(unsigned char B[HEIGHT][WIDTH],unsigned char G[HEIGHT][WIDTH],unsigned char R[HEIGHT][WIDTH],int weight=400) { double fordivideheight = 1.0*HEIGHT / weight; double fordividewidth = 1.0*WIDTH / weight;..

나도 다른 블로그를 참 많이 읽는다. 나만 그런 것인지는 모르겠지만 알고리즘 글을 읽을 때 유난히 "이게 무슨 개소리야" 하는 상황이 많이 닥친다. 철없을 때는 다른 사람이 글 참 못 쓴다.. 생각했지만 내가 블로그를 해보고 나니, 그 귀차니즘에 대해 이해해버렸다. 문제 풀고 맞추는게 재밌지, 그 지식을 다른 사람에게 전달하는 것에서 재미를 느끼는 것은 또 전혀 다르다. 흥미를 느끼지 않는데 글이 술술 잘 써질리 전무하다. 그런데, 대부분 그 사실을 잘 모른다. 알고리즘 정리/문제 풀이 글에는 대부분 댓글이 거의 달리지 않기 때문이다. (...) 내 블로그를 떠나서 PS블로그계는 정말 질문에 인색하다는 생각이 많이 든다. 나부터도 글을 읽다 막혀도 대부분 혼자 고민하고, 정 안되면 다른 글로 그냥 넘어간..

이 글의 발단은 메타인지#0을 참고 바랍니다. 2021/03/06 - [Problem Solving/Road to PS GOD] - 메타인지 #0 현재 L=1, R=31 => mid = 16 => Platinum 5 Platinum 5 문제를 푼다. 문제를 맞은 사람 수 대로 정렬하고 위에서부터 안 푼 문제를 푼다. 첫 문제는 단절점이다. 이 기세를 모아서 단절선도 풀었다. 비슷한 유형의 문제이기에 이건 카운팅 안 함. 두 번째 문제는 소트다. 친구가 푸는 거 보고 따라 풀었는데, 생각보다 많이 절었다 .-. 처음엔 그래프 문젠줄 알았지만, 길이가 n인 경로를 빠르게 찾을 수 없어 실패. 다음날 그냥 그리디적으로 고른 다음 반복적으로 시뮬레이션하면 쉽게 풀 수 있더라. n이 좀 커져도 될 듯 multis..

Saycorn과 함께 봤다 문제가 어려웠다. 이번 라운드 업솔빙하면 실력 많이 늘 것이다. 아이디어가 떠올랐을 때 바로 구현하지말고 시간복잡도를 예측해보는 시간을 들여야 한다는 것을 배웠다. 이와 반대로 시간이 촉박할 경우 어떤 아이디어든 세세하게 재지 말고 바로 구현에 들어가야 한다.

Problem Solving을 할 때, 내 자신에 대해 느껴왔던 것 중 하나는 "답지"를 유난히 많이 본다는 것이다.모방은 창조의 어머니라지만, 모방만이 반복되면 결국 표절의 대가가 되어버리고 만다. 현재 나의 solved.ac 티어는 Diamond 2다. 내 실력보다는 훨씬 높은 티어라는 생각이 든다. 나의 본 실력을 파악하기 위해 한 가지 실험을 진행하려고 한다. 가설: 나는 Bronze 5부터 Diamond 2까지 모든 문제들을 풀 수 있는 실력을 가졌으며, 그 이상의 문제는 답지를 참고해야 한다. 실험은 다음과 같다. 기본 컨셉) Bronze5를 1, Ruby1을 30으로 놓고 이분탐색을 진행한다. L: 내가 풀 수 있는 문제 티어의 최댓값 R: 내가 풀 수 없는 문제 티어의 최솟값 L, R의 초..