안 쓰던 블로그

입력 4 6 101111 101010 101011 111011 입력 코드 cin >> n >> m; for (int i = 0; i > a; for (int j = 0; j < m; j++) { map[i][j] = a[j] - '0'; } }

관련 문제 -이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리) -완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리) 이진 검색 트리 문제부터 본다 전위 순회한 결과 값으로 후위 순회하는 문제이다 전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다 이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다 이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 ) 1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다 2. 값을 하나 입력 받는다 3. 현재 노드를 나타낼 now변수를 둔다..

6068 시간 관리하기 1263 시간 관리 '늦잠을 언제까지 잘 수 있냐'가 문제이기 때문에 끝나는 시간을 기준으로 내림차순 정렬하고 앞에서부터(가장 끝나는 시간이 늦은 일부터) 일을 최소 언제부터 시작해야 하는지를 계산한다 예제로 보면, 5 20은 최소 15에는 시작해야 한다 1 16은 최소 15에는 시작해야 하지만, 15에는 5 20이 해야 하므로 앞으로 밀려서 14에는 시작해야 한다 8 14는 최소 6에는 시작하면 된다 3 5는 최소 2에 시작하면 된다 github.com/proqk/Algorithm/blob/master/greedy/6068%20%EC%8B%9C%EA%B0%84%20%EA%B4%80%EB%A6%AC%ED%95%98%EA%B8%B0(1263%20%EC%8B%9C%EA%B0%84%20..

4796 캠핑 단순한 생각- 예를 들어 8일 중에 5일을 사용할 수 있으며 총 휴가가 20일이면 8일(5일)-8일(5일)-4일=14일을 캠핑할 수 있다 계산 방법 그대로 휴가를 일 수로 나누고 나머지를 더하면 된다 근데 여기서 함정은, 남은 일수가 연속 일수보다 큰 경우다 위에서는 8일 중에 5일을 사용할 수 있는데 남은 일수가 4일이라서 그냥 넣으면 됐다 근데 만약 남은 일수가 6일이라면? 최대 5일밖에 사용할 수 없다 이 두 가지 경우를 주의해 주면 되었다 github.com/proqk/Algorithm/blob/master/greedy/4796%20%EC%BA%A0%ED%95%91.cpp 2891 카약과 강풍 각 팀이 가지고 있는 카약의 수를 인덱스로 만들어서 더하거나 빼면 되었다 처음엔 모든 팀이..

1202 보석 도둑 처음엔 보석 값대로 sort하고 가방 sort해서 무게 들어가는 거 넣는 방법으로 했는데 당연히 시간초과 github.com/proqk/Algorithm/blob/master/greedy/1202%20%EB%B3%B4%EC%84%9D%20%EB%8F%84%EB%91%91_%EC%8B%9C%EA%B0%84%EC%B4%88%EA%B3%BC.cpp 여기서 두 sort를 한 이유는, 가격이 높은 보석부터 차례대로 가방 허용 무게에 가장 가까운 보석을 찾기 위해서이다 다르게 말하면 가방 무게 x보다 큰 보석 중에 가장 작은 수를 찾는다 = Lower Bound 그리고 찾은 값을 삭제한다 이진 탐색 트리BST를 사용하면 이 탐색 및 삭제 연산을 O(NlogK)에 할 수 있다 BST로 구현된 C+..

5639 이진 검색 트리 평소에 트리를 읽는 순서인 전위순회대로 주어지는 입력값으로 이진 트리를 만들고, 후회순회를 돌리면 된다 첫 값인 root를 기준(now)으로 잡고 왼쪽 오른쪽 값을 비교한다 만약 노드가 없으면 주어진 값으로 새로운 노드를 만들고, 아니면 그 노드를 now로 두고 다시 탐색 돌아간다 이진 탐색 트리 구현은 전에 썼던 글이 있다 AVL트리 foxtrotin.tistory.com/191 이진 탐색 트리 foxtrotin.tistory.com/190 그리고 입력의 끝이 주어지지 않을 때 c++에서는 while(cin>>num){} 이렇게 하면 된다 while문으로만 EOF처리가 되기 때문에 저렇게 썼는데도 런타임 에러가 난다면 배열 크기나 벡터 초기화나 다른 곳을 살펴본다 github...

신년맞이 작심20일 boj 챌린지 -하루에 정해진 분량만큼 문제 풀이(계획서 참고) -각 문제별 간단 해결 방법+깃헙 링크 블로그 정리 1967 트리의 지름 day1에서 했던 트리의 지름 문제처럼 정점 1에서 가장 멀리 있는 정점을 dfs로 구한뒤, 그 정점에서부터 다시 가장 먼 노드를 찾으면 트리의 지름이 된다 github.com/proqk/Algorithm/blob/master/Tree/1967%20%ED%8A%B8%EB%A6%AC%EC%9D%98%20%EC%A7%80%EB%A6%84(2).cpp 2805 나무 자르기 나무를 세워두고 케이크 자르듯이 칼로 쓰윽 자른다고 생각한다 자른 짜투리의 길이를 전부 더해서 너무 많이 잘랐으면 덜 자르고, 너무 적게 잘랐으면 더 자르는 식으로 조절한다 1. 나무를..