softeer, 장애물 인식 프로그램
softeer, 장애물 인식 프로그램 문제 https://softeer.ai/practice/info.do?idx=1&eid=409 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 풀이 pass 풀이 일단 방문했으면 방문여부를 표시해야 재방문하는 일이 없을 것이다. 2차원 region이 주어졌으면 index범위를 벗어나지 않는지도 체크해 봐야 한다. 대각선 방향은 고려하지 않아도 되므로 북동남서를 탐색했을 때, '1'이고 방문한 적 없을 경우에만 탐색한다. 우리가 원하는 값은 방문가능한 범위 카운트한 값이다. 그래서 이를 global 변수로 둔다. # 북동남서 dr = [-1, 0, 1, 0] dc = [0, 1, 0, -1] def dfs(r,c): global cn..
2.2 알고리즘 분석
2.2 알고리즘 분석 알고리즘을 실행 시, 필요한 자원 예측 메모리 통신대역 하드웨어 계산시간 RAM 모델 단일 프로세서 + RAM 캐시나 가상메모리는 고려하지 않는다. 명령어는 동시에 수행되지 않고 차례로 하나씩 실행된다. 명령어 한 행당 상수시간 소요 산술연산(덧셈, 뺄셈, 곱셈, 나눗셈, 나머지, 내림, 올림) 데이터이동 연산(읽기, 저장하기, 복사하기) 제어 연산(조건 분기, 무조건 분기, 함수 호출과 리턴) 입력크기는 수행시간에 비례한다. 최악의 경우 : 크기가 n인 입력 중 가장 오래걸리는 수행 시간 평균적인 경우 : n개의 숫자 무작위 하지만 무엇이 평균적인 입력인지 불확실한 경우, 랜덤화된 알고리즘을 사용한다. 연습문제 2.2-1 θ(n³) 2.2-2 for s = 1 to A.length..
