[Algorithm] DFS (Depth First Search, 깊이 우선 탐색) 알고리즘

인트로 그래프의 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색)를 구현해보려 한다. 그래프라는 건 추상적인 개념이다. 0번 정점과 1번 정점이 연결되어 있다는 정보만 있을 뿐 실질적으로 그래프를 구현하는 자료구조는 배열이 될 수도 리스트가 될 수도 벡터가 될 수 있다. 어떤 자료구조를 사용할진 개발자의 선택이다. 본 포스팅에선 C# 기반 배열과 리스트(List)로 구현하는 간단한 코드를 소개하려 한다. 결론부터 말하면 재귀 함수를 사용해 DFS를 구현했다. BFS가 궁금하다면? [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 [Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘 인트로 ..

• format_list_bulleted Algorithm/탐색
• · 2021. 8. 17.
• textsms

[Algorithm] 31. 탄화수소 질량

인트로 문제 자체는 심플하지만 결과를 도출하기 위해 여러 조건을 검사해야 하는 문제를 소개하려 한다. 탄화수소 질량 구하기 문제 탄소(C)와 수소(H)로만 이루어진 화합물을 탄화수소라고 합니다. 탄소(C) 한 개의 질량은 12g, 수소(H) 한 개의 질량은 1g입니다. 에틸렌(C2H4)의 질량은 12*2+1*4=28g입니다. 메탄(CH4)의 질량은 12*1+1*4=16g입니다. 탄화수소 식이 주어지면 해당 화합물의 질량을 구하는 프로그램을 작성하세요. ※ 입력설명 첫 줄에 탄화수소식이 주어집니다. 식의 형태는 CaHb 형태이며 (1 str; if (str[1] == 'H') { cCount = 1; pos = 1; } else { int i; for (i = 1; str[i] != 'H'; i++) { ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 13.
• textsms

[Algorithm] 29. 3의 개수는?(small)

인트로 1부터 N까지 숫자에서 3이 몇 개 있는지 구하는 문제이다. N의 범위가 작은 만큼 시간제한이 없는 문제이다. 시간제한이 없다면 코딩 기초 문제에 포함되는 문제이지만 시간제한이 있다면 난이도가 엄청나게 올라가니 본 문제를 풀어보고 시간제한이 있다면 어떤 방식으로 풀어야 할지 고민해보자 나중에 시간이 된다면 시간제한이 버전을 포스팅하려 한다. (링크 추가 예정) 3의 개수는? (시간제한 없음) 문제 자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다. 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다. 자연수 N이 입력..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 12.
• textsms

[Algorithm] 28. N!에서 0의 개수

인트로 본 문제는 수학적인 사고를 요구합니다. 본 문제를 해결하기 어렵다면 이전 포스팅 N!의 표현법을 풀어보시길 권장합니다. [Algorithm] level1 : N!의 표현법 인트로 꽤나 수학적인 문제이다. 문제를 풀기 전 알아야 할 한 가지 개념이 있다. 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 예를 들어 12는 2 x 2 x 3으로 표현할 수 있다. 이처럼 2 이 kangworld.tistory.com N!에서 0의 개수 문제 자연수 N이 입력되면 N! 값에서 일의 자리부터 연속적으로 ‘0’이 몇 개 있는지 구하는 프로그램을 작성하세요. [예시] 5! = 5 X 4 X 3 X 2 X 1 = 120으로 일의 자리부터 연속된 ‘0’의 개수는 1입니다. 12! = 479001600으로 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 11.
• textsms

[Algorithm] 27. N!의 표현법

인트로 꽤나 수학적인 문제이다. 문제를 풀기 전 알아야 할 한 가지 개념이 있다. 2 이상의 모든 자연수는 소수의 곱으로 표현할 수 있다. 예를 들어 12는 2 x 2 x 3으로 표현할 수 있다. 이처럼 2 이상의 자연수는 소수의 곱으로 쪼개질 수 있다. N!의 표현법 문제 임의의 N에 대하여 N!은 1부터 N까지의 곱을 의미한다. 이는 N이 커짐에 따라 급격하게 커진다. 이러한 큰 수를 표현하는 방법으로 소수들의 곱으로 표현하는 방법이 있다. 먼저 소수는 2, 3, 5, 7, 11, 13... 순으로 증가함을 알아야 한다. 예를 들면 825는 (0 1 2 0 1)로 표현이 가능한데, 이는 2는 없고 3은 1번, 5는 2번, 7은 없고, 11은 1번의 곱이라는 의미이다. 101보다 작은 임의의 N에 대하..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 10.
• textsms

[Algorithm] 26. 마라톤

인트로 이전 포스팅에서 다루었던 석차 구하기 문제와 유사하다. 본 문제에서 다룰 전수조사에 관한 내용은 해당 포스팅을 참조하길 바랍니다. [Algorithm] level1 : 석차 구하기 (Brute force 브루트 포스) 인트로 브루트 포스 알고리즘이 적용될 문제를 소개하려 한다. 브루트 포스 Brute force, 브루트 포스는 완전 탐색 알고리즘이다. 완전 탐색 알고리즘이란 모든 경우의 수를 조사하는 방법이다. 자 kangworld.tistory.com 마라톤 문제 KSEA 장거리 달리기 대회가 진행되어 모든 선수가 반환점을 넘었다. 각 선수의 입장에서 자기보다 앞에 달리고 있는 선수들 중 평소 실력이 자기보다 좋은 선수를 남은 거리 동안 앞지르는 것은 불가능하다. 반대로, 평소 실력이 자기보다 ..

• format_list_bulleted Algorithm/it 취업을 위한 알고리즘 문제 풀이
• · 2021. 8. 9.
• textsms