전체 글
[백준]K번째 수
백준저지 [K번째 수]https://www.acmicpc.net/problem/11004 • C++의 algorithm STL에 있는 nth_element()함수를 이용해서 문제를 풀었다. • nth_element()는 k번째 수까지 정렬을 하는 좋은 함수이다. • 시간도 메모리도 상대적으로 많이 썼다. • 시간이 되면 nth_element함수를 구현해 볼 생각이다. #include #include #include using namespace std; int main(void) { int N, K; scanf("%d%d", &N, &K); vector vecArr(N, 0); for (int i = 0; i < N; i++) { long long int in; scanf("%lld", &in); vecA..
[백준]이진탐색트리
백준저지 [이진탐색트리]https://www.acmicpc.net/problem/2957 • 필자에 너무 어려웠던 문제이다. 이 문제를 풀기위해 3주를 고민했다. • 어렵게 풀었던 만큼 이진탐색트리의 삽입, 삭제, 탐색은 확실하게 이해도가 많이 올라간 것 같아 기분이 좋다. • 추가적으로 Map이란 STL사용법도 확실히 많이 익숙해진 듯하다. [풀이] • 기본적으로 이진탐색트리의 삽입의 성질과 위 문제의 의도를 정확하게 이해해야 풀 수 있는 문제이다. → root의 값보다 크면 오른쪽, root의 값보다 작으면 왼쪽 • 아마 처음 접근은 위 문제에서 수도코드로 짜여있는 예시대로 구현을 했을 것이다. • 필자도 저 예시대로 재귀로 구현해도 해보고 반복으로 구현도 해보고 배열을 30만개 만들어서도 해보고....
[백준]트리
백준저지 [트리]https://www.acmicpc.net/problem/1068 • 문제를 푸는데 30분정도 걸렸다. • 두 번 실패를 하였다. → 원인은 노드의 삭제가 재귀적인 성향을 가지고 있다는 것을 늦게 발견하였음 → 즉, 삭제하려고 하는 노드를 포함한 자손까지 전부 삭제를 해주어야 됨 → 일차원적으로 삭제하려고 하는 노드의 자식만 삭제하여 계속 실패를 하였음 [풀이] • 삭제에 유용한 list STL을 사용하여 트리를 구성하였음(리스트 배열 51개를 생성) • 입력 값들 중 두 번째 줄에서 부모 노드가 없는 경우는 루트 노드이기 때문에 따로 –1처리를 해주지 않았음 • 두 번째 줄에서 부모 노드를 입력 받기 때문에 listArr[51]의 인덱스를 노드의 번호로 간주, 인덱스르 이용해서 트리 그..
2017년 새해 맞이
날이 좋아서날이 안좋아서날이 적당해서모든 날이의미있었던2016년 굿바이... 그리고 2017년 정유년의 해가 밝았다.2017년의 첫번째 일출을 보기위해"강원도 고성 옵바위"로 떠났다. 고성은 내가 2년간 군생활을 했던 곳.처음에는 사람많은 곳을 최대한 피하자는 마음에고성을 선택했다.하지만가는 내내 고성에서 군생활했던추억(?)들이 떠올랐는데기분이 나쁘지만은 않았다. 일산에서 밤 11시에 출발해서 새벽 4시쯤고성 옵바위에 도착했다.정확한 주소는"강원 고성군 죽왕면 공현진리"이다. 여튼 도착해서 차안에서2~3시간 잠을 잔뒤일어나서 나가보니엄청 멋있는 장관이펼쳐졌다. 의외로 날씨가 많이 춥지가 않아서좋았다. 서서히 여명이 밝아왔는데파스텔 칠한것 처럼엄청 이뻤다. 그리고 새해 풍등을 날리는 사람들도많았다. 풍등이..