Autonomous Vehicle/Programming Skill5 코딩테스트 : 스킬트리 구현 자세히 파헤쳐보기 (Python3) 문제: 스킬트리 문제 설명: 선행 스킬이란 어떤 스킬을 배우기 전에 먼저 배워야 하는 스킬을 뜻합니다. 예를 들어 선행 스킬 순서가 스파크 → 라이트닝 볼트 → 썬더일때, 썬더를 배우려면 먼저 라이트닝 볼트를 배워야 하고, 라이트닝 볼트를 배우려면 먼저 스파크를 배워야 합니다. 위 순서에 없는 다른 스킬(힐링 등)은 순서에 상관없이 배울 수 있습니다. 따라서 스파크 → 힐링 → 라이트닝 볼트 → 썬더와 같은 스킬트리는 가능하지만, 썬더 → 스파크나 라이트닝 볼트 → 스파크 → 힐링 → 썬더와 같은 스킬트리는 불가능합니다. 선행 스킬 순서 skill과 유저들이 만든 스킬트리1를 담은 배열 skill_trees가 매개변수로 주어질 때, 가능한 스킬트리 개수를 return 하는 solution 함수를 작성해주.. 2021. 5. 18. 알고리즘 문제 해결 전략 I (4) 알고리즘 문제 해결 전략 I (4) 프로그래밍 대회에서 많이 하는 실수 : 쉬운 문제를 어렵게 푸는것 - 무식한 알고리즘 컴퓨터의 빠른 계산을 이용한 가능한 경우의수를 일일이 나열하면서 답을 찾는 방법을 의미. - > 완전 탐색 (exhaustive search) 이라고 부른다. 사실, 컴퓨터의 장점을 가장 잘 이용하는 방법. *STL 표준 템플릿 라이브러리 더보기 vector 컨테이너 클래스 : 배열을 다루기 용이한 함수 #include vector intV(5); // intV라는 int 데이터형 5개의 변수를 가진 배열을 생성 vector intV; // 0개의 변수를 가진 배열을 생성 가능 intV.push_back(value); //value 값을 배열에 마지막 원소 자리를 생성 후 대입 int.. 2020. 7. 10. 알고리즘 문제 해결 전략 I (3) 알고리즘 문제 해결 전략 I (3) 알고리즘은 객과적이어야 하며 본질적으로 모호하지 않아야 한다. 컴퓨터 공학에서의 알고리즘은 컴퓨터가 따라할 수 있도록 자세히 설명한 과정을 나타낸다. 알고리즘의 평가기준 시간과 공간 적은 시간사용 : 빠르게 동작 적은 공간사용 : 적은 메모리에도 동작 본 두 기준은 서로 상충하는 경우가 큼. 알고리즘의 시간 복잡도 반복문이 알고리즘 수행시간의 가장 큰 영향 선택정렬과 삽입정렬 1. 선택정렬 : 모든 원소들에서 가장 작은 원소를 찾고 그것을 새로운 배열에 넣는 방식 최악의 경우와 최선의 경우의 시간복잡도가 같다. 2. 삽입정렬 : 전체 배열중 정렬되어 있는 부분 배열에 새 원소를 끼워넣는 일을 반복하는 방식 입력이 임의의 순열이라고 할 때 대부분 삽입정렬이 빠름. 알고리.. 2020. 7. 9. 알고리즘 문제 해결 전략 I (2) 알고리즘 문제 해결 전략 I p.75~ 실수 자료형의 이해 컴퓨터가 사용하는 실수 표현방식과 그 장단점을 이해해야만 한다. IEE 754 표준을 가장 많은 컴퓨터와 컴파일러들에서 사용되고 있다. 특징: 이진수로 실수를 표기 부동소수점 표기 무한대 비정규수 숫자가 아님 등의 특수값 존재. 가장많이 다룰 [실수의 이진법 표기] 실수표준에서는 소수점을 고정시키지 않고 옮길 수 있도록 만들어짐 따라서 큰수도 적확한 수도 다 커버가능 실수변수에서는 3가지의 정보를 저장하게 됨 1. 부호비트 2. 지수 (소수점을 몇칸 옮겼는지) 3. 가수 (소수점을 옮긴 실수의 최상위 X비트) 64비트의 경우 53비트의 가수를 표현할 수 있게 되는데, 이는 마지막 반올림 되고 버려지는 자리의 수의 비중은 9000조 분의 1 이므로.. 2020. 7. 7. 알고리즘 문제 해결 전략 I (1) 알고리즘 문제 해결 전략 I (1) 프로그래밍은 곧 문제 해결이다. 프로그램이 사용할 수 있는 최대 메모리와 사용자가 답답해 하지 않게 하기 위한 시간제한 유의, 재사용성이 높은 간결한 코드 작성. 많은 제약조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력이 프로그래머에게 필요. 파인만 알고리즘 1. 칠판에 문제를 적는다. 2. 골똘히 생각한다. 3. 칠판에 답안을 적는다. ◆ 문제 해결 과정을 단계별로 나누는것이 point 문제를 적는 단계 = 자신의 언어를 이용하여 재정의 어떻게 문제를 풀것인가 에서 문제 해결 과정 정의 1. 문제를 이해한다. 2. 어떻게 풀지 계획을 세운다. 3. 계획을 수행해서 문제를 해결한다. 4. 어떻게 풀었는지 돌아보고 개선할 방법이 있는지 찾아본다. 프로그래밍 대회를.. 2020. 7. 6. 이전 1 다음
