The Way

소수 컬렉션을 풀어보았다. 백준 1456: 거의 소수범위가 10^14이다. 다행히 N제곱 꼴인 경우를 물어봤으므로, 10^7까지의 소수를 미리 구해놓고, 2제곱/3제곱/...을 잘 세어보면 된다.코드의 생명은 오버플로우 관리. 예를 들어서, 소수 p를 곱해가면서 b보다 커질 때까지 한다고 하면, b가 10^14라고 하면 10^7보다 약간 작은 소수에 대해서는 10^21 정도까지 가게 되는데, 이는 long long 범위도 넘어선다. 적당히 max값을 잡는 것이 이롭다. #include #define N 10000005 using namespace std; bool notprime[N]; int main() { for (int i = 2; i * i < N; ++i) { if (!notprime[i]) {..

꽤 쉬운 것 같길래 공부를 시작하기 전 가볍게 워밍업으로 풀어보았다. 백준 17173번: 배수들의 합N이 작아서 그냥 다 더해주면 된다. 생략. #include #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, t; cin >> n >> m; vector arr(n + 1, 0); while (m--) { cin >> t; for (int i = t; i > m; int ans = 0; while (n) { ans += n; n /= m; } cout n; cout = 'A' && c = 'a' && c > a >> b >> c; int p, q, r; p = a; q = 2 * b * c; r..

백준에는 가끔 경이로운 문제들이 있다.재능이 많은 사람들이 그 재능을 발산할 곳을 찾다 못해 백준 문제에 그 정수를 담아놓는 듯한 기분이다.구데기컵의 이 문제도 그러하다. 본격적인 채굴 문제... 문제의 기본적인 원리는 비트코인의 그것을 이용한다.비트코인에 조금이나마 관심이 있는 사람이라면 비트코인이 hash를 쓴다는 것 정도는 알고있을 것이다. 하지만 사실 hash를 직접 써 볼 기회가 그리 많지는 않다. 이 문제는 그런 의미에서 요즘 각광받는 블록체인 기술의 맛보기라도 볼 수 있다는 점에서도 아주 좋은 문제이다. 배경 지식을 아주 간단하게만 설명하면, 비트코인은 블록 전체를 sha-256이라는 해시 알고리즘을 통해 hash를 돌려서 hash값이 특정 숫자 이하가 나오도록 하며,블록에는 거래정보 / 직..

인기 문제에 있는 꿀문제만 조져보았다. 백준 15637번: Lotto구데기컵스럽게 이상한 문제인데 쉬운 편.https://dhlottery.co.kr/gameResult.do?method=byWin링크 아래쪽에서 친절하게 ~회부터 ~회까지 당첨번호를 엑셀로 다운받을 수 있다.코드는 굳이 첨부하지 않는다. 백준 17202번: 핸드폰 번호 궁합어릴 적에 한번쯤은 해보았을 듯한 이름 궁합과 비슷하다.틀리기가 더 힘든 문제. #include using namespace std; int main() { char num1[9], num2[9]; int arr[16]; cin >> num1 >> num2; for (int i = 0; i < 8; ++i) { arr[i * 2] = num1[i] - '0'; arr[..

오랜만에 백준을 풀어보았다. 감이 좀 떨어진 것이 느껴진다.오랜만에 codeforces도 해보았다. Div3이었는데도 참교육당했다. 백준 17144번: 미세먼지 안녕!정직한 구현 문제. 미세먼지는 상하좌우 4방향으로 확산이 일어나고, 공기청정기 바람의 경로에 있는 먼지들은 바람의 방향대로 한 칸씩 이동한다.공기청정기 바람의 방향 때문에 조금 노가다가 심하다. 더 짧게 짤 수는 있겠지만 빨리 짜는 것과 적당히 밸런스를 맞추어야 한다. #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int r, c, t; cin >> r >> c >> t; int air[51][51] = {}; int pos1 = -1, pos2..

다이나믹 프로그래밍 위주로 한 번 풀어보았다. 백준 2618번: 경찰차 경찰창의 위치와 각 위치일 때 그 위치가 될 때까지 이동한 거리의 최솟값을 저장해놓으면 된다. 나는 빡대가리같이 map을 써서 코드를 짰다. 굉장히 똥코드지만.. 뭐 통과만 하면 됐지 정석 방법은 각 위치를 1~1000번 번호를 붙여준 뒤 2차원 배열에 저장하는 방법이다. 문제가 치사하게 경로까지 출력해야 하기 때문에 아마 거리, 직전 위치 2가지는 저장해야 한다. #include #include #include using namespace std; typedef pair ii; int dist(int a, int b) { return abs(a / 10000 - b / 10000) + abs(a % 10000 - b % 10000)..

거의 2달만에 푸는 백준이다. 컴퓨터 환경 세팅을 오랫동안 하고(...) 간단히 워밍업 느낌으로 안 푼 문제 중 쉬운 문제들 몇 개만 풀어보았다. 백준 14502번: 연구소처음에 보고 당황했는데, 다행히 n이 작았다. 모든 조합을 다 해보면서 DFS/BFS를 돌리면 간단하게 풀 수 있다.만약 n이 크다면? 유량으로 풀어야 할 것 같은데 정확히 모르겠다. #include #include using namespace std; typedef pair ii; int n, m, cnt, ans; int map[8][8], temp[8][8]; int loc[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; vector two; void dfs(int i, int j) { if (i <..

* 코드는 맨 아래에 있습니다 쉬운 문제는 거의 다 푼 것 같다. 이제 난이도 있는 문제들이 슬슬 나올.. 것 같다. # 백준 1406번: 트리의 지름# 백준 1967번: 트리의 지름트리의 지름을 구하는 좋은 알고리즘이 있다.http://blog.myungwoo.kr/112여기에 잘 설명되어 있음 # 백준 11650번: 좌표 정렬하기# 백준 11651번: 좌표 정렬하기 2pair은 문제의 조건대로 비교 연산자가 잘 정의되어 있으므로 사용하면 된다11651번의 경우 연산자 정의를 새로 하기보단 순서를 바꾸어주면 된다. # 백준 10814번: 나이순 정렬stable_sort 문제이다.그런데 한쪽이 string이라 약간 번거로운 면도 있고, swap시 시간도 오래 걸릴 것 같아서string은 따로 저장하고, ..

* 코드는 맨 아래에 있습니다 울 학교 학생분께 ACM-ICPC 같이 나가자고 연락이 왔다나랑 같은 휴학생이고 되게 열심히하실 것 같고 성격도 완전 천사같다앞으로 더 열심히 해야겠다 # 백준 10799번: 쇠막대기간단한 스택 문제. 스택에 막대 n개가 쌓여 있을 때 레이저가 자르면 n개의 조각이 더 생긴다. # 백준 1406번: 에디터특이하게 list를 사용하는 문제이다.list에서 insert와 erase할 때 iterator 위치가 약간 헷갈릴 수 있으니 주의 # 백준 10820번: 문자열 분석맨 마지막줄이 엔터가 있는지 없는지 참 아리까리하다..이것 때문에 틀림 ㅠ # 백준 11655번: ROT13뭐... 엄청 많이 접해봤을법한 카이사르 암호이다.오버플로우가 일어날 수 있으니 편하게 unsigned..

* 코드는 맨 아래에 있습니다 문제야 다 덤벼라 이얍 # 백준 7576번: 토마토BFS 문제 # 백준 2309번: 일곱 난쟁이재귀를 써야 예쁜 코드지만, 사실 7개정도면 노가다 코드가 코딩이나 성능 면에서 더 빠르다. # 백준 11403번: 경로 찾기플로이드-와샬 알고리즘이다. 알고리즘 자체는 되게 간단하기는 한데 아직 마음깊이 이해가 되지 않은 기분이다. 활용이 나오면 못 풀 것 같다. # 백준 13458번: 시험 감독디버그할 때 오류나서 배열 크기를 살짝 줄이는데, 다시 늘리는 걸 깜빡해서 자꾸 틀린다.진짜 실수하지 말자 이런 기본적인건... # 백준 1652번: 누울 자리를 찾아라구현 문제.문제가 약간 표현이 모호하다고 느낄 수도 있는데, 2칸 이상 빈칸이 이어지면 2개든 3개든 100개든 (.....