https://codeup.kr/problem.php?id=3004 데이터 재정렬 50 23 54 24 123 에서 23, 24, 50, 54, 123 순서로 0, 1, 2, 3, 4 가 된다. 그리고 원래의 위치대로 출력한다. codeup.kr 1. 문제 데이터를 오름차순으로 정렬했을 때의 순위를 각 원소 순위에 맞게 출력하라. 2. 알고리즘 데이터를 정렬하여 순위를 찾고 해당 순위를 각 원소에 부여한다. 3. 주의할 점 python에서 제공하는 index()함수는 시간복잡도가 O(N)이므로 이 함수를 이용했을 경우에는 시간초과가 발생한다. 따라서 binary search를 구현하고 해당 알고리즘을 사용해서 index를 찾아야한다. 4. 소스코드 n = int(input()) # 입력 처리 data =..

https://codeup.kr/problem.php?id=3006 완전 제곱수 찾기 $n \times n = n^2$을 만족하는 $n^2$을 완전 제곱수라고 한다. $k$개의 숫자 $a_1, a_2, a_3, ... , a_k$가 제시되면, 각각의 수보다 같거나 작은 가장 큰 완전 제곱수를 구하여라. 단 이 문제는 코드에 sqrt라는 텍스트가 나와서는 안 된다. 금지 키워드 : sqrt codeup.kr 1. 문제 주어진 값보다 크지 않으며 가장 큰 완전 제곱수를 구하라. 2. 알고리즘 주어진 값의 제곱근을 구한 뒤, 소수점을 버린 후에 다시 제곱한다. 3. 주의할 점 sqrt를 사용하면 안된다. **는 써도 되겠지만 그러면 sqrt를 쓰지않는 의미가 없다. 따라서 제곱근을 수행하는 함수를 만들어야한다..

1. 파이썬 문법다지기 2. 알고리즘 개념 3. 알고리즘 유형별 문제풀이 4. 기출문제 대상 : 파이썬으로 알고리즘을 시작하는 사람 조건 : 파이썬 문법, 스터디 내용 정리 파이썬 알고리즘 세션은 크게 4가지의 순서로 진행이 됩니다. 파이썬을 언어로 진행하기 때문에 파이썬 문법에 대해서 어느정도 알고있어야 합니다. 어느정도 알고있다. 1. 입출력을 할 수 있다. 2. 함수를 구현할 수 있다. 3. 시퀀스 자료형을 반복문으로 다룰 수 있다. 4. 슬라이싱을 쓸 수 있다. 5. 튜플과 람다를 사용할 수 있다. 그리고 본인이 공부한 내용을 반드시 어떠한 형태(블로그, 깃허브 등)로 정리해야합니다.양이 많으며 기간도 길게 생각하고 있습니다. 1. 파이썬 문법 다지기 해당 1주차는 파이썬 문법을 다집니다. 입출력..

실수 표현 방법 부동소수점 소수점 위치를 왼쪽의 가장 유효한 숫자 다음으로 고정시키고 밑수의 지수승으로 표현한다. 1001.0011 -> 1.00100111 * 2^3 컴퓨터에서 실수 저장 방식 단정도 실수(32비트) vs 배정도 실수(64비트) 모두 부호, 가수부, 지수부로 구분하여 저장한다. 가수부 : 실수의 유효 자릿수들을 부호화된 고정 소수점으로 표현한것 지수부 : 실제 소수점의 위치를 지수 승으로 표현한것 파이썬에서는 8byte 배정도 실수로만 저장한다. 컴퓨터는 실수를 근사적으로 표현 근사로 저장하기 때문에 근사값으로 저장될 때 생기는 작은 오차가 다른 결과를 가져온다. 유효자릿수 32비트 실수형 유효자릿수(십진수) => 6 64비트 실수형 유효자릿수(십진수) => 15

진법(진수) 변환 10진수를 타진수로 변환하는 방법 > 원하는 타진법의 수로 나눈뒤 나머지를 거꾸로 읽는다. > 나눌때 마지막으로 나오는 비트가 MSB(most significant bit, 최상위비트)가 된다. 타진수를 10진수로 변환하는 방법 > 각 자릿값에 해당 진수의 값을 곱해서 구한다. 예) 135(8) = 1 * 8^2 + 3 * 8^1 + 5 * 8^0 = 93(10) 2진수, 8진수, 16진수간 변환 2진법 8진법 : 3자리씩 나열 또는 묶음 2진법 16진법 : 4자리씩 음의 정수 표현 1의 보수 : 부호 비트를 제외한 나머지 비트들을 반전 2의 보수 : 1의 보수 방법으로 표현된 값의 최하위 비트에 1을 더한다.

연산자 기능 & 비트단위 and | 비트단위 or ^ 비트단위 xor (같으면 0, 다르면 1) ~ 모든 비트 반전 비트 열을 오른쪽으로 이동 비트연산은 다른 연산에 비해 속도가 빠르다. 예) 홀짝비교 => n % 2이용 또는 n & 1을 이용하여 가능 비트연산 1 > i) print(end=" ") 16진수 하나는 2진수 4개로 표현된다. 1byte는 16진수 2개로 이루어지며, 2진수 8개로 표현된다. 엔디안(Endianness) > 컴퓨터 메모리와 같은 1차원의 공간에 여러개의 연속된 대상을 배열하는 방법. h/w아키텍처마다 다르다. > 주의사항 : 속도향상을 위해 바이트 단위와 워듣 단위로 변환하여 연산할 때 잘못 이해하면 오류를 발생할 수 있다. 빅인디안(big-endian) 보통 큰 단위가 앞..

1. 알고리즘 유한한 단계를 통해 문제해결 절차 및 방법 예) 1~100 합 1. 1 + 2 + 3 + ... 2. 100 * (1 + 100) / 2 = 5050 => 이런 해결 방법을 절차적으로 정리한것. 알고리즘을 효율적이어야 한다. > 입력이 커질 수록 효율에 따라 실행시간 차이 발생 알고리즘 설계 -> 실행 필요한 지원분석 -> 효율성 제시 효율성 -> 복잡도. 복잡도가 높을 수록 효율성 저하. 1. 공간 복잡도 2. 시간 복잡도 시간 복잡도 입력 크기에 대한 함수로 표기. 점근적 표기를 사용한다. 입력 n이 무한대로 커질 때를 가정. 1. 빅오, 2. 오메가, 3. 세타 빅오표기법 - worst case 점근적 상한을 의미한다. O(g(n)) = f(n)이라는 것은 g(n)이 모든 n에 대해서..

코딩은 중요하다. 이하 생략. 프로그래밍 문제해결을 위한 조건 1. 프로그램이 언어의 특성 2. 프로그램이 동작할 h/w와 os에 관한 지식 3. 라이브러리들의 유의사항 4. 프로그램이 사용할 수 있는 최대메모리 5. 사용자 대응 시간 제한 6. 재사용성이 높은 간결한 코드 문제 해결 역량은 추상적인 기술 -> 암기는 큰 도움이 안된다. 언어, 프레임워크, 개발방법론들의 조합 방법을 배워야한다. 해결 과정 단계 1. 문제를 꼼꼼히 읽고 이해하기 2. 문제를 익숙한 용어로 재정의하기 3. 해결 계획 세우기 4. 문제에서 제시된 테스트 케이스로 계획 검증하기 5. 프로그램으로 구현하기 6. 풀이를 돌아보고 개선방법 찾기 문제 해결 전략 > 직관과 체계적인 접근 1. 비슷한 문제를 풀어본적이 있는가? 2. 단..

1. 정렬 2개 이상의 자료를 특정 기준에 의해 오름차순 또는 내림차순하는 것이다. Key : 자료를 정렬하는 기준이 되는 특정 값 예) 서류 번호대로 정렬하기 -> 키는 서류 번호가 된다. 2. 버블 정렬(Bubble Sort) 인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다. 한 패스가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다. 시간복잡도 = O(n^2) 예시) 55, 7, 78, 12, 42 1. 첫번째 패스 55 7 78 12 42 7 55 78 12 42 7 55 78 12 42 7 55 12 78 42 7 55 12 42 [78] 이렇게 한 패스가 끝나면 가장 큰 원소가 마..

1. 탐욕 알고리즘(Greedy Algorithm) 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식 최적 해를 구하는데 사용되는 근시안적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다. 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 된다. 2. 탐욕 알고리즘 수행 과정 1. 해 선택 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가한다. 2. 실행 가능성 검사 새로운 부분..