새벽 기상을 꿈꾸는 루민

안녕하세요 세기무민입니다. 이번 포스팅에서는 DFS/BFS 알고리즘에 대해 다뤄보도록 하겠습니다. DFS/BFS? DFS와 BFS 알고리즘은 코딩테스트에 거이 단골 문제 중 하나입니다. DFS는 깊이 우선 탐색 알고리즘 BFS는 너비 우선 탐색 알고리즘 대표적으로 DFS의 경우 재귀함수 또는 스택으로 문제를 해결할 수 있고 BFS의 경우 큐(덱큐)를 이용하여 문제를 해결할 수 있습니다. DFS와 BFS를 가장 쉽게 알 수 있는건 아래의 그림으로 볼 수 있습니다. [DFS]! 위의 그림처럼 깊이부터 하나씩 탐색하는 방식입니다. 1에서 가장 가까운 2를 탐색하고 2의 다음 노드인 4를 탐색합니다. 노드 4 이후로 연결된 노드가 없음으로 노드 1로 다시 이동하여 탐색을 반복해줍니다. [BFS!] BFS는 가장..

안녕하세요 세기무민입니다. 이번 포스팅은 브루트포스 알고리즘에 대해 다뤄보겠습니다. 브루트포스? 브루트 포스는 무차별 대입을 통해 값을 도출하는 방법입니다. 브루트 포스 알고리즘은 암호 해독에 유명한 알고리즘 중 하나입니다. 브루트 포스는 조합 가능한 모든 문자열을 하나씩 대입해보는 완전 탐색 기법이라고 생각하면 됩니다. 브루트포스 알고리즘 장단점? 조합 가능한 모든 문자열을 대입하기 때문에 정확도가 100%를 도출합니다. 단, 모든 경우의 수를 찾아가기 때문에 조금만 알고리즘이 복잡해져도 알고리즘의 시간 복잡성은 올라갑니다. 예시 알고리즘 문제 위의 문제는 가장 대표적인 브루트 포스 알고리즘 중 하나입니다. 3개의 숫자를 합했을 때 M의 크기와 가장 가까운 값을 찾는 문제인데 해당 문제는 순열을 통해서..

안녕하세요 세기무민입니다. 이번 포스팅에서는 그리디 알고리즘에 대해 다뤄보도록 하겠습니다. Greedy? 탐욕? 우선 그리디 알고리즘은 탐욕 알고리즘이라고도 말합니다. 그리디 알고리즘에서 가장 중요하게 생각하는 포인트는 "현재 선택지 중 가장 좋은(최적)의 방법을 선택하는 것" 그리디 알고리즘에 대한 가장 좋은 예시는 최단거리를 구하는 것이다. 아래의 그림으로 설명해보면 시작 지점으로부터 끝지점까지 최단거리를 구해보도록 하자. 시작 지점에서 4로 시작하는 경우 2가지의 경우의 수가 만들어지며 20, 23의 거리를 가진다. 시작 지점에서 4보다 큰 6으로 시작했을 경우 19의 거리를 가지게 되고 최종적으로 가장 짧은 거리를 가지게 된다. 즉 그리디 알고리즘은 여러개 중 한개를 선택해야 할 경우 그 순간에 ..

우선 시험이 끝난 후 조금 코딩연습했던 내용들을 올려볼 생각인데..... 일단 시험을 너무 망쳤지만 알고리즘 공부의 중요성을 한번 더 알게 되었다. 사실 1차 서류 합격으로도 나에게는 큰 경험이지만 일주일도 안되는 시간동안 알고리즘 공부하는 건 쉽지 않았다. 무튼 조금씩 꾸준히 공부할 예정이다. 내가 풀어본 문제는 이 문제! NYPC에서 문제들을 보면서 나름 어려웠다. 내가 이 문제를 보자마자 생각난건 바로 아스키코드! 아스키코드로 비교하면서 특수문자의 경우는 파이썬에서 isalnum()라는 매소드로 특수문자가 존재하는지 비교하여 문제를 해결했다. # 비밀번호 검사 n = str(input()) def pwCheck(x): checkL, checkS, checkN, checkP, check= 0, 0, ..

흠... 우선 서류 통과를 한 기업이 생겼는데.... 최근들어 문제가 발생했다. 서류 통과 후 알고리즘 테스트인지 아니면 시스템 설계하는 테스트인지 정확하게 알려진 건 없지만 코딩 테스트를 본다고 한다. 그래서 급하게 공부를 시작했지만 쉽지 않다는 걸 느끼게 되었구 시험을 못보더라도 꾸준히 알고리즘 공부를 해야겠다는 생각에 같이 공부할 예정이다. 우선 기본적으로 공부할 내용은 linked-list! 사실 Array와 linked-list 두개가 주로 사용되지만 때로는 두개의 성능의 차이로 사용되는 부분이 다르다. arraylist는 많은 양에 자료를 추가하거나 삭제하는 과정에서 성능이 저하되지만 그에 비해 linked-list는 데이터 추가하거나 삭제하는 과정이 효율적이다. 또 다른 차이로는 arrayl..