본문 바로가기

Algorithms63

DFS - 깊이 우선 탐색 (Java) 10월 9일 예정인 ICPC 학교 예선을 대회 약 한 달 전인 9월 초중반 즈음에 나가기로 했다... 알고리즘의 알 자도 모르는 나였지만 일단 갖다 박아보는거지!! 라는 마인드로 똑같은 마인드의 팀원들을 구해서 준비를 했다 ㅎㅎㅎ 공부할수록 어렵고 복잡함을 느끼지만 오기도 생기고 재미도 붙어서 올해는 경험삼아 도전해보고, 내년에 제대로 공부하고 해보고 싶어졌다. 공부한 것을 정리하기 위해! 포스팅을 한다. DFS(깊이 우선 탐색)은 가중치가 없는 그래프에서의 경로를 찾는 방법이다. 왜 깊이 우선이냐면 한 경로를 찍고 끝까지 내려갔다가 돌아오기 때문! 그래서 재귀적으로 움직이는 것이 특징이다. 장점은 구현하기 쉽다! 그리고 저장 공간을 적게 먹고, 목표 노드가 깊게 있다면 그를 빨리 구할 수 있다. 반대로.. 2021. 10. 7.
[Python] 여러 수의 최소공배수와 최대공약수를 구하는 프로그램 이게 무슨 제목만 봐도 끔찍한 프로그램이람? 최대공약수랑 최소공배수를 짜는 알고리즘을 구현해보자. 사실 구현해도 숫자가 커질수록, 항의 수가 많아질수록 계산시간이 기하급수적으로 길어질 것이라는 것이 빤히 예상되지만 일단 이론적으로 구멍이 없는 프로그램을 구현해 보도록 하자. 우선 첫 번째로 입력값을 받아주자. 숫자를 세 개 이상 입력하고 그 값을 리스트로 처리하면 되겠지? vals = [] while True: insert_val = input('GCD, LCM과 공약수를 찾을 수를 세 개 이상 입력하세요') if insert_val == 'start': if len(vals) < 3: print('3개 이상의 값을 넣어주세요.') continue print('입력이 완료되었습니다. {}의 최소공배수, .. 2021. 9. 19.
[Java] 로봇 문제 어쩌다보니 자바로 지역 icpc를 나가게 되어 급하게 공부하고 있다. 중간점검차 기출문제를 한 번 풀어보게 되었는데, 생각보다 자바를 엄청나게 잘 다뤄야 할 필요는 없었던 듯. 이게 문제였다. 이런 문제는 진짜 난생 처음 겪어봐서 어떻게 풀어야 할지 구상하는 데만 한참이 걸렸는데, 일단 풀기 위한 키로 보였던 요소들은 1. x나 y좌표가 nxn에서 n보다 크면 무조건 -1 반환. 2. 현재 보고 있는 방향을 변수에 저장. 3. 마지막으로 움직인 방향을 변수에 저장. 그러면 북쪽으로 갈 때는 y값을 더해주고 남쪽으로 가면 빼주고, 같은 방법으로 x를 처리해주면 될 것 같았다. 문제는 방향. 좌로 돌기, 우로 돌기가 있었는데 그것을 위해 2,3번을 고안해냈던 것. 그런데 두 값을 합쳐서, 마지막으로 본 방향.. 2021. 9. 19.