Algorithm
DFS 이론
DFS 이론
2021.09.05전위 순회(preorder) 트리의 전위 순회는 루트노트 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순으로 순회하는 방식이다. 코드 역시 현재 노드를 출력한 후, 왼쪽, 오른쪽 순서대로 함수를 호출한다. 중위 순회(inorder) 트리의 전위 순회는 왼쪽 서브 트리 -> 루트노트 -> 오른쪽 서브 트리 순으로 순회하는 방식이다. 코드는 왼쪽 함수 호출, 현재 노드 출력, 오른쪽 함수 호출 순서로 진행된다. 후위 순회(postorder) 트리의 전위 순회는 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 루트노트 순으로 순회하는 방식이다. 후위 순회 또한 왼쪽 함수 호출, 오른쪽 함수 호출, 현재 노드 출력 순서로 진행된다. package main import "fmt" func dfs(v int) { if..
javascript - 괄호문자제거 (자료구조 stack and queue)
javascript - 괄호문자제거 (자료구조 stack and queue)
2021.08.14문제풀이 이문제는 스택과 큐를 이용해서 해결하는 문제다. 풀이에 사용된 방법은 닫는 괄호를 만나면 여는 괄호를 만날 때까지 pop을 시킨다. pop 되지 않은 문자열을 괄호 안에 없다고 판단하여 join 하여 return 한다. function solution(str) { const stack = []; for (x of str) { if (x === ")") { while (stack.pop() !== "("); } else stack.push(x); } return stack.join(""); } const str = "(A(BC)D)EF(G(H)(IJ)K)LM(N)"; console.log(solution(str)); Github https://github.com/JongyunHa/algorithm..
문제 - 뮤직비디오 (결정알고리즘)
문제 - 뮤직비디오 (결정알고리즘)
2021.06.22지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지 되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기 로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개..
선생님 퀴즈
선생님 퀴즈
2020.11.27#include int main() { int n; scanf("%d", &n); int *input = new int[n]; int *answer = new int[n]; for (int i = 0; i < n; i++) { int a, b; scanf("%d %d", &a, &b); input[i] = a; answer[i] = b; } for (int j = 0; j < n; j++){ int sum = 0; for(int k = 1; k
Anagram (구글 인터뷰문제)
Anagram (구글 인터뷰문제)
2020.11.25#include #include int main() { int a[60]{ 0 }; int b[60]{ 0 }; char str[100]; scanf("%s", &str); for(int i = 0; str[i]!='\0'; i++){ // 대문자를 확인 if (str[i]>=65 && str[i]=65 && str[i]
c++ 1359 : 숫자 피라미드 1
c++ 1359 : 숫자 피라미드 1
2020.11.17문제 설명 길이 nn이 입력되면 다음과 같은 숫자 피라미드를 출력한다. 예) nn이 5이면 1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 입력 길이 nn이 입력된다.(1
c++ 1358 : 삼각형 출력하기 5
c++ 1358 : 삼각형 출력하기 5
2020.11.17문제 설명 어떤 수 n을 입력받으면 다음과 같은 삼각형을 출력한다. 여기서 입력되는 n은 반드시 홀수이다. 입력 3부터 99 까지의 홀수 중 하나가 입력된다. 출력 Sample Output 같은 삼각형을 출력한다. 입력 예시 5 출력 예시 * *** #include int main() { int x, space; scanf("%d", &x); space = x / 2; for (int i = 1; i
c++ 1356 : 사각형 출력하기 2
c++ 1356 : 사각형 출력하기 2
2020.11.14문제 설명 길이 n이 입력되면 다음과 같은 사각형을 출력한다. 예) n이 5일때 ***** * * * * * * ***** 입력 길이 n이 입력된다. (n >= 3) 출력 사각형을 출력한다. 입력 예시 3 출력 예시 *** * * *** #include int main() { int x = 0; scanf("%d", &x); for (int i = 1; i
숫자만 추출해서 약수 출력하기
숫자만 추출해서 약수 출력하기
2020.11.08숫자만 추출 문자와 숫자가 섞여있는 문자열이 주어지면 그 중 숫자만 추출하여 그 순서대로 자연수를 만 듭니다. 만들어진 자연수와 그 자연수의 약수 개수를 출력합니다. 만약 “t0e0a1c2her”에서 숫자만 추출하면 0, 0, 1, 2이고 이것을 자연수를 만들면 12가 됩니 다. 즉 첫 자리 0은 자연수화 할 때 무시합니다. 출력은 12를 출력하고, 다음 줄에 12의 약 수의 개수를 출력하면 됩니다. 추출하여 만들어지는 자연수는 100,000,000을 넘지 않습니다. ▣ 입력설명 첫 줄에 숫자가 썩인 문자열이 주어집니다. 문자열의 길이는 50을 넘지 않습니다. ▣ 출력설명 첫 줄에 자연수를 출력하고, 두 번째 줄에 약수의 개수를 출력합니다. ▣ 입력예제 1 g0en2Ts8eSoft ▣ 출력예제 1 28 ..
나이계산 (문자열 컨트롤하기)
나이계산 (문자열 컨트롤하기)
2020.11.08나이계산 주민등록증의 번호가 주어지면 주민등록증 주인의 나이와 성별을 판단하여 출력하는 프로그램 을 작성하세요. 주민등록증의 번호는 -를 기준으로 앞자리와 뒷자리로 구분된다. 뒷자리의 첫 번째 수가 1이면 1900년대생 남자이고, 2이면 1900년대생 여자, 3이면 2000년대 생 남자, 4이면 2000년대생 여자이다. 올해는 2019년입니다. 해당 주민등록증 주인의 나이와 성별을 출력하세요. ▣ 입력설명 첫 줄에 주민등록증 번호가 입력됩니다. ▣ 출력설명 첫 줄에 나이와 성별을 공백을 구분으로 출력하세요. 성별은 남자는 M(man), 여자는 W(Woman)로 출력한다. ▣ 입력예제 1 780316-2376152 ▣ 출력예제 1 42 W ▣ 입력예제 2 061102-3575393 ▣ 출력예제 2 14 M..
c++ 1292 : 범인을 잡아라 1
c++ 1292 : 범인을 잡아라 1
2020.11.08문제 설명 한적한 시골마을에 도둑이 들었다. 이 도둑은 마을의 재산을 훔쳐가다 마을 사람들에게 들켜 도망쳤다. 급하게 도망치느라 도둑은 신발이 벗겨졌다는 사실도 잊었다. 마을 사람들은 도둑의 신발의 DNA를 분석했다. 도둑의 DNA의 특징은 DNA의 모든 숫자의 합을 77로 나눈 나머지가 44라는 사실을 알았다. 다음 날 경찰이 도둑으로 의심되는 사람을 검거하여 그들의 DNA 샘플을 가져왔다. DNA 샘플을 분석하여 이 자가 도둑인지 아닌지를 판단하여 만약 도둑이라면 “suspectsuspect”, 아니면 “citizencitizen”을 출력하는 프로그램을 작성하시오. 입력 길이가 1010자리로 구성된 1010진수가 입력된다. 출력 프로그램의 조건에 따라 “suspectsuspect” 또는 “citize..
c++ 1289 : 가장 큰 운동장
c++ 1289 : 가장 큰 운동장
2020.11.08문제 설명 학교에서 축구대회를 열기로 했다. 본교 학생 수가 많아서 되도록 큰 운동장을 필요로 한다. 학교 근처에 축구를 할 수 있는 운동장이 3개가 있는데 각 운동장의 가로와 세로의 길이를 홈페이지를 통해서 알 수 있었다. 우리는 3개의 운동장 중 가장 큰 운동장을 빌리기로 했다. 이 3개의 운동장 중 가장 넓은 운동장의 넓이를 구하는 프로그램을 작성하시오. 입력 가로와 세로의 정수 길이를 33세트 입력 받는다. (단, 길이는 10001000 이하의 양의 정수값) 출력 넓이가 가장 넓은 운동장의 넓이를 출력한다. 입력 예시 10 10 9 12 13 8 출력 예시 108 #include using namespace std; int main() { int x, y; int result = 0; for (i..