아무코딩

문제풀이 java 의 경우에는 비트마스크를 이용해서 풀어보았고, c++의 경우에는 dfs를 사용해서 풀었다. 7달 전에 작성한 방법과 다른방법으로 풀어보고자 비트마스크를 사용해보았다. 문제 풀이 방법은 구역을 다 나누어보고(완탐), 그렇게 나누었을 때 조건이 성립하는지(연결이 되는 상태인지)를 체크해준다. 조건이 만족할시에는 최솟값 업데이트를 해준다. 소스코드 java 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ..

문제풀이 벡터의 외적을 활용한 문제이다. "다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. " 라는 말을 처음에 파악하지 못해 어려움을 겪었지만 이말인 즉슨 시계방향 혹은 시계반대방향으로 쭉 다각형을 이어 그리며 바로 인접한 점의 점이 주어진다는 것을 의미한다. 아마 문제 출제의도였던 CCW라는 알고리즘을 적용하기 좋게 인풋이 주어지도록 한것 같다. CCW는 그냥 내용을 살펴보니 외적을 이용한 사선공식과 같았다. 위의 식이 세점이 주어졌을때 삼각형의 넓이를 구하는 공식이다. 이를 이용하여 쭉 더하다보면 면적을 구할 수 있다. 이식은 각이 유의미 해서 점의 순서도 중요하다!! 유의해서 문제를 풀면 오목한 다각형의 상황이 나오더라도 예외처리가 된다. (음수의 넓이로 더해지기..

문제풀이 union-find를 이용한 문제입니다. paraent를 자기자신으로 초기화 한뒤 계속 한쪽을 붙여주며 붙여주고나서는 parent를 가리키는 방식입니다. 간단한 방식이고 더 효율적으로 푸려면 자식이 많은 트리에 계속 붙여나가고 루트노드에 바로 직접 자식이 붙어있도록 최적화를 한다면 더 빨라 질것 같으나 해당문제에서는 그정도 까지는 필요없다고 판단하여 이렇게 풀었습니다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 #include using namespace std; int N,M;..

문제풀이 매우 아이디어가 좋은 문제이다. 루트 노트로부터 가장 멀리있는 노드로부터 또다시 가장 먼노드를 찾으면 그 두 노드가 지름을 담당하는 두노드다 그 두노드의 사이의 길이가 트리의 지름의 길이이다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include using namespace std; typedef struct treeNode{ int edge,num; ..

문제풀이 투포인터를 사용한 문제이다. 계산된 값이 크면 기억한 몸무게를 계산된 값이 작거나 같으면 현재 몸무게를 증가시키며 일치하는 값의 현재몸무게는 바로 출력해준다. 값이없을때 처리를 따로해주지않아 한번 틀렸었다... 주의하자.. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; int G; int curWeight=2; int memWeight=1; long long getG(){ return pow(curWeight,2) - pow(memWeight,2); } int main() { cin>>G; bool ch..

문제풀이 매우 복잡하게 푼거 같은느낌이 든 문제이다. 1. 탐색은 bfs를 사용하였고 bfs를 사용하여 계속 파이프를 따라간다. 2. 파이프가 이어져야 하는 곳에 파이프가 없을때('.' 일때) 3. 해당 위치에서 사방을 탐색하여 적절한 파이프를 기존에 저장해놓았던 map에서 반환한다. 모든 걸 넣어보고 문제없는지 확인하는 방법도 있겠지만 더 효율적으로 짜보고자 map을 활용하였다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 ..

문제풀이 카카오에 블록이동과 비슷한것 같지만 다른 문제입니다. 그때는 기준을 왼쪽 위(목적지와 상대적으로 가까운 지점)를 기준으로 잡았지만 이번에는 목적지와 상대적으로 가까운 지점을 기준으로 잡습니다. 그리고 현재 방향, 다음 방향을 모두 고려하여 불가능한 케이스를 제거해주고, 다음 위치의 벽유무, 범위 체크등을 해주며 dfs를 진행해 주면 되는 문제입니다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 6..

문제풀이 위상정렬을 활용한다. 이 문제에서는 위상정렬이 성립되지 않는 경우를 생각해야된다. 위상정렬이 이루어지는 조건은 노드가 다 출력될때까지 in-degree가 0이 아닌 노드가 없는 것인데 그거 말고 이상한 방법으로 사이클 체크를 하려해서 고생을 했다. 개념에 충실하자... 추가로 위상정렬을 간략하게 설명하자면 indegree가 0인 노드를 큐에다 추가하는 방식 프린트는 물론 큐에서 하나씩. 그러면 순서가 보장된다. 소스코드 더보기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54..