아무코딩

문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. ..

문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K무게까지의 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 ..

문제 가로와 세로의 길이가 같은 평지에서 벌목을 한다. 그 지형은 0과 1로 나타나 있다. 1은 아직 잘려지지 않은 나무를 나타내고 0은 아무 것도 없음을 나타낸다. 다음 지형을 보자. B 0 0 1 1 B 0 0 0 0 B 0 0 0 0 1 1 0 0 0 E E E 0 0 위의 지형에서 길이 3인 통나무 BBB를 밀거나 회전시켜 EEE의 위치로 옮기는 작업을 하는 문제를 생각해 보자. BBB와 EEE의 위치는 임의로 주어진다. 단 문제에서 통나무의 길이는 항상 3이며 B의 개수와 E의 개수는 같다. 통나무를 움직이는 방법은 아래와 같이 상하좌우(Up, Down, Left, Right)와 회전(Turn)이 있다. 코드 의미 U 통나무를 위로 한 칸 옮긴다. D 통나무를 아래로 한 칸 옮긴다. L 통나무를..

문제 갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파일이 걱정되기 시작했다. 다행히 상근이는 저장되어 있는 중요한 디렉토리의 전체 경로를 텍스트 파일로 따로 저장하고 있었다. 예를 들면, WINNT\SYSTEM32\CERTSRV\CERTCO~1\X86. 상근이의 중요한 디렉토리의 전체 경로가 모두 주어졌을 때, 디렉토리 구조를 구해 보기 좋게 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 중요한 디렉토리 전체 경로의 개수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개 줄에는 디렉토리 경로가 주어진다. 경로는 한 줄로 이루어져 있으며, 공백을 포함하지 않는다...

문제풀이 벡터의 외적을 활용한 문제이다. "다음 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; ..

문제풀이 위상정렬을 활용한다. 이 문제에서는 위상정렬이 성립되지 않는 경우를 생각해야된다. 위상정렬이 이루어지는 조건은 노드가 다 출력될때까지 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..