The Way
5월 11일 백준 본문
* 코드는 맨 아래에 있습니다
하루에 7시간씩 문제풀기를 한다. 상당히 벅차다.
재밌는건 7시간동안 계속 풀어도 질리지 않는다는 것이다. 코딩은 나랑 정말 잘 맞는다.
재능..도 있다고 나름 생각했는데 나보다 위에 있는 사람들을 볼 때마다 확실히 아니라는 걸 느낀다.
뛰는 놈 위에 나는 놈 있다고나 할까ㅠㅠ
항상 그들을 동경하면서, 따라잡으려고 악착같이 노력할 것이다.
# 백준 1012번: 유기농 배추
단순 탐색 문제
# 백준 1057번: 토너먼트
규칙을 조금만 생각해보면 쉽게 풀린다.
1, 2, 3...번보다는 1씩 내려서 0, 1, 2...로 해야 편할 것이다.
참고로 둘이 대결하지 않는 경우는 당연히 없다.
# 백준 1018번: 체스판 다시 칠하기
단순 비교가 개꿀이다.
최대 크기 50이라 42*42*64 = 112896밖에 안된다.
나는 비트마스크를 연습 겸 써봤는데, 코드만 길어지고 약간 까다롭긴 하다.
그래도 크기가 커지면 비트마스크가 미묘하게 더 빠르지 않을까..
# 백준 1051번: 숫자 정사각형
단순 브루트 포스 문제
# 백준 1068번: 트리
노드를 제거할 때, 만약 해당 노드가 유일한 자식이라면 부모 노드가 리프로 변한다는 점에 유의하자.
# 백준 1049번: 기타줄
생략
# 백준 1015번: 수열 정렬
stable_sort를 사용하는 문제이다.
* 특정 struct를 원하는 기준으로 정렬하고 싶을 때
struct s { int a, b; };
s arr[20];
bool comp(s a, s b) { return a.a < b.a; }
sort(arr, arr + 20, comp);comp 부분에 call by reference를 사용하면 컴파일 오류가 나는데 왜 그런지 잘 모르겠다.
즉, bool comp(s& a, s& b) { return a.a < b.a; } 이런 식으로 쓰면 안 된다는 것.
# 백준 1182번: 부분집합의 합
단순 브루트 포스 문제. 재귀를 쓰면 코드가 편하다.
# 백준 1197번: 최소 스패닝 트리
굉장히 유명한 알고리즘 문제인 최소 스패닝 트리이다.
크루스칼 알고리즘과 프림 알고리즘이 있는데, 크루스칼이 더 간편해보여서 크루스칼로 썼다.
나중에 정리해서 게시글 하나 써야겠다.
# 백준 1120번: 문자열
붙이는 것은 결국 B랑 똑같도록 붙이면 되기 때문에,
결국 A랑 B랑 제일 조금 다른 부분을 찾고, 얼마나 차이나는지를 구하는 문제
# 백준 1212번: 8진수 2진수
수의 길이가 30만이 넘는다는 점에 유의. 8진수라서 당연히 맨 처음만 신경쓰고, 각 자릿수를 이진수로 바꾸면 된다.
# 백준 1238번: 파티
오늘의 하이라이트 문제.
다익스트라 알고리즘이 드디어 나왔다. 알고리즘 시간에 배운 거라 너무 반가웠는데 하나도 기억이 안나서 내 머리가 돌임을 다시 입증한 듯 하다.
다른 곳에서 출발->A로 가는 거를 어떻게 구하냐고 물을 수 있겠는데, 화살표를 반대로 하면 A에서 출발하는 것과 동일해진다.
내가 공부하는 책에서 다익스트라 알고리즘을 잘 구현해놓아서 따라했다. 아예 달달 외워버려야겠다.
# 백준 1261번: 알고스팟
처음엔 단순 DP 문제인 줄 알고 코딩을 했는데, 다 풀고보니 세상에.. 거꾸로 갈 수가 있다.
당연히 탐색이겠거니 하고 풀어나갔다. 당연히 처음 접근할 수 있는 곳은 횟수 0, 그 다음은 1, ...의 방식
접근 횟수를 줄여나가기 위해 상당히 깔끔한 방법을 썼다. status에 depth값을 저장해서 depth번 탐색에서는 한 번만 접근할 수 있고, 그 다음에는 다시 접근하도록 만들었다.
다 풀고보니 다익스트라 알고리즘이라고 한다. (나는 원래 다 풀고 나서 알고리즘 분류를 본다)
왜 그런지 아직은 잘 이해가 안된다. 내일 자고 일어나서 생각해봐야겠다.
1012.cpp