공부
-
구현공부/알고리즘 2021. 5. 29. 14:18
피지컬로 승부하기구현하기 어려운 문제 ex)알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제, 특정 소수점 자리까지 출력해야 하는 문제, 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야하는(파싱을 해야 하는)문제 등 -> 사소한 조건 설정이 많은 문제시뮬레이션 : 문제에서 제시한 알고리즘을 한 단계씩 차례대로 직접 수행 완전 탐색 : 모든 경우의 수를 주저 없이 다 계산하는 해결 방법 구현 : 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 구현 시 고려해야할 메모리 제약 사항 int 자료형 데이터의 개수에 따른 메모리 사용량데이터의 개수(리스트의 길이)메모리 사용량 1,000 약 4KB 1,000,000 약 4MB 10,000,000 약 40MB 파이썬은 자료형을 지정할 필요도..
-
그리디 알고리즘공부/알고리즘 2021. 5. 29. 14:16
그리디 알고리즘이란? 현재 상황에서 지금 당장 좋은 것만 고르는 방법->매순간 가장 좋아보이는 것을 선택, 현재 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다. 사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형 ex)가장 큰 순서대로, 가장 작은 순서대로 *다익스트라 알고리즘은 그리디 알고리즘이면서 암기가 필요한 알고리즘 그리디 알고리즘의 정당성 모든 문제에 적용할 수 있는 것은 아님->탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을때 사용! 대표적 그리디 알고리즘 문제 https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔,..