본문 바로가기

알고리즘

BOJ 백준 17136 색종이 붙이기 #include #include #include using namespace std; const int SIZE = 10; int arrMap[SIZE][SIZE]; bool arrBoolMap[SIZE][SIZE]; int arrCount[5]; struct EmptySpace { int x, y; }; vectorvecEmptySpaces; intg_nCnt = 999999999; intg_nRemainArea = 0; boolg_bFind = false; void Input() { for (int i = 0; i < SIZE; ++i) { for (int j = 0; j < SIZE; ++j) { scanf("%d", &arrMap[i][j]); if (arrMap[i][j]) { g_nRemain..
마름모 내부의 점 x, y : 점의 x, y좌표 centerX, centerY : 마름모의 x, y좌표 a : 가로 길이의 절반 b : 세로 길이의 절반 마름모 방정식 : | x - centerX | / a + | y - centerY | / b = 1 따라서 마름모 내부에 존재하는 지 알려면 | x - centerX | / a + | y - centerY | / b
[HackerRank] Tree : Top View https://www.hackerrank.com/challenges/tree-top-view/problem Tree : Top View | HackerRank Given a binary tree, print it's top view. www.hackerrank.com 문제 풀이) distance(level order) 와 vertical order를 기억하자. 수직 별로 노드를 저장하는 것, 처음 겪어보았다. 기억해두자. queue를 이용해서 left, right 노드들의 거리를 통해 수직 별로 노드를 저장할 수 있다. HackerRank의 discussion의 첫 설명에서 영어센스가 부족하여 이해하지 못했음.. 답은 expected이다. in fact가 아니고.. ...더보기 void..
[HackerRank] Array Manipulation https://www.hackerrank.com/challenges/crush/problem Array Manipulation | HackerRank Perform m operations on an array and print the maximum of the values. www.hackerrank.com 문제 풀이) 문제에 주어진대로 쿼리문을 실행하여 배열에 값들을 더해주고, 최대값을 찾아가는 연산은 시간초과가 난다. 20만개의 쿼리문, 그리고 최대 1000만개까지 데이터가 존재하고 a와 b도 1부터 n까지 가능하므로 최악의 경우 20만 x 1000만 만큼의 for문이 돌아간다. 당연히 시간초과가 날 수밖에 없다. 이러한 문제를 쿼리문의 개수(최대 20만) + 데이터의 개수(1000만) 으로 줄일 수..
[HackerRank] Attribute Parser https://www.hackerrank.com/challenges/attribute-parser/problem Attribute Parser | HackerRank Parse the values within various tags. www.hackerrank.com 문제 풀이) 1. 새로운 태그 생성 - tag 이름 찾기 - 속성 이름 찾기 - 속성에 해당하는 값 찾기 tag이름의 경우 의 형태처럼 빈칸이 나올때까지 찾아도 되겠지만, 속성 값이 없는 경우, 즉 와 같은 값으로 들어올 때는 빈칸이 아닌 '>'까지 조사해주어야 한다. 따라서 인덱스 1부터 문자가 ' ', '>'가 아닐 때까지가 tag임을 알 수 있다. 속성과 속성에 해당하는 값의 경우, 이 둘은 한 세트로 ..
[ HackerRank] Attending Workshops https://www.hackerrank.com/challenges/attending-workshops/problem Attending Workshops | HackerRank Define a structure for the workshop and find the number of workshops that the student can attend. www.hackerrank.com 문제 풀이) 워크 샵의 종류와 워크 샵의 시작 시간, 진행 시간이 주어질 때, 학생들이 시간이 겹치지 않게 워크 샵을 최대한 몇 번 참여할 수 있는 지 출력해주는 문제이다. 시작 시간 혹은 끝 시간 둘 중 하나를 기준으로 잡고 DP 배열을 이용하여 풀면 된다. 먼저 워크 샵의 시작 시간의 최대치, 즉 가장 늦게 시작하는 경우..
[HackerRank] Deque-STL https://www.hackerrank.com/challenges/deque-stl/problem Deque-STL | HackerRank Learn to use deque container. Find the maximum number in each and every contiguous sub array of size K in the given array. www.hackerrank.com 문제 풀이) 총 원소의 개수와 한 묶음의 원소의 개수가 주어질 때, 각 묶음에서 가장 큰 수들을 찾아 순서대로 출력해주는 문제이다. Input & Output 5 2 3 4 6 3 4 5개의 원소 중, 2개씩 묶으므로 {3, 4} {4, 6} {6, 3} {3, 4} 로 총 4개의 묶음이 나오고 각 묶음에서 가장 큰..
[HackerRank] Bit Array https://www.hackerrank.com/challenges/bitset-1/problem Bit Array | HackerRank Calculate the number of distinct integers created from the given code. www.hackerrank.com 문제 풀이) 나타나는 숫자의 개수를 세는 문제이다. 예를 들어 1, 2, 3, 4, 0, 1, 2, 3, 4 와 같이 나왔다면 1, 2, 3, 4, 0 으로 총 5가지의 수가 나타났음을 출력해주면 된다. set이나 map을 unordered로 선언하고 해도 시간초과가 난다. 그 이유는 총 1억개의 수가 중복되지 않는다면 1억개의 원소가 추가되고, 이 연산은 시간을 감당할 수 없기 때문이다. 친구랑 같이 고민을..

티스토리툴바