컴퓨터 전공 공부 썸네일형 리스트형 정수론 : 오일러 피 오일러 피 오일러 피 함수 P[N]의 정의는 1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 오일러 피 함수는 증명 과정을 공부해야 완벽하게 알 수 있다고하지만 실제 코딩 테스트에 사용하기 위한 구현 부분만 알아보겠다. 오일러 피의 핵심 이론 오일러 피 함수의 원리는 에라토스테네스의 체와 비슷하다. 오일러 피 함수의 원리 1 구하고자 하는 오일러 피의 범위만큼 리스트를 자기 자신의 인덱스값으로 초기화한다. 2 2부터 시작해 현재 리스트의 값과 인덱스가 같으면(= 소수일 때) 현재 선택된 숫자(K)의 배수에 해당하는 수를 리스트에 끝까지 탐색하며 P[i] = P[i] - P[i]/K 연산을 수행한다(i는 K의 배수). 3 리스트의 끝까지 과정 2 를 반복하여 오일러 피 함수를 완성한다. 수학.. 더보기 정수론 : 소수 구하기 에라토스테네스의 채 소수 소수 구하기의 핵심 이론 소수를 구하는 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체 원리는 다음과 같다. ① 구하고자 하는 소수의 범위만큼 1차원 리스트를 생성한다. ② 2부터 시작하고 현재 숫자가 지워진 상태가 아닌 경우 현재 선택된 숫자의 배수에 해당하는 수를 리스트에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. ③ 리스트의 끝까지 ②를 반복한 후 리스트에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용할 때 시간 복잡도 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N^2) 정도라고 판단할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르겠지만, 일반적으로 O(Nlo.. 더보기 그리디 알고리즘과 우선순위 큐 그리디 그리디 알고리즘은 현재 상태에서 볼 수 있는 선택지 중에 최선의 선택을 하는 알고리즘이다. 그리디 알고리즘은 동적 계획법보다 구현하기 쉽고 시간 복잡도가 우수하다. 하지만 항상 최적의 해를 보장하지 못한다... 그래서 코테에서는 그리디 알고리즘 사용 전에 항상 그리디 알고리즘을 적용할 때의 논리 유무를 충분히 살피라고 한다. 그리디 알고리즘의 핵심 이론 그리디 알고리즘 수행 과정 1. 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해 선택 2. 적정설 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사하기 3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결 가능한 지 검사 만약 전체 문제를 해결 못할거 같으면 1로 돌아가 과정 반복 문제 풀면서 익히는게 가장 좋다.. 더보기 탐색 알고리즘 정리 탐색 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말한다. 주어진 데이터의 성질(정렬 데이터 또는 비정렬 데이터)에 따라 적절한 탐색 알고리즘을 선택하는 것이 중요하고, 실제 모든 코딩 테스트 문제의 기본이 되는 알고리즘이므로 직접 구현해 원리를 완벽하게 이해하는 것이 중요하다. 탐색 영역에서는 그래프를 자주 탐색하므로 아래 저의 블로그를 참고하고 보면 좋을 것 같습니다. https://mkisos.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84%EC%9D%98-%ED%91%9C%ED%98%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0 깊이 우선 탐색 깊이 .. 더보기 그래프의 표현 (알고리즘, 자료구조) 그래프에 대해서 그래프는 노드와 에지로 구성된 집합이다. 노드는 데이터를 표현하는 단위이고 에지는 그 노드들을 연결한다. 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에서 자주 볼 수 있다. 그래프를 구현하는 3가지 방법 1. 에지 리스트 2. 인접 행렬 3. 인접 리스트 2차원 리스트 생성 0으로 초기화한 행(row) 개수 3, 열(column) 개수 4인 2차원 리스트를 생성할 때 리스트를 객체를 생성하는 방법 -> 추천!!! A = [[0 for col in range(4)] for row in range (3)] 얕은 복사를 일으켜 생성하는 방법 A = [[0]*4]*3 # 이와 같은 방식으로 선언한 후 값을 변경하면 다른 원소의 값도 함께 변경될 수 있다. A= [[0]*4].. 더보기 정렬 알고리즘 (버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 기수 정렬) 정렬 알고리즘 정의를 내가 아는가? 정렬 알고리즘 정의 버블 데이터의 인접 요소끼리 비교, swap 연산을 수행하며 정렬 선택 대상에서 가장 크거나 작은 데이터를 찾아서 선택을 반복하며 정렬 삽입 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬 퀵 pivot 값을 선정해 해당 값을 기준으로 정렬 병합 이미 정렬된 부분 집합들을 병합해 전체를 정렬 기수 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬 버블 정렬의 핵심 이론 버블 정렬 (bubble sort)은 두 인접한 데이터의 크기를 비교해 정렬하는 방법입니다. 간단하게 구현할 순 있지만, 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편입니다. 다음 그림과 같이 루프를 돌면서 인접한 데이터 간의 sw.. 더보기 프로그래밍 질문하는 법 누구나 프로그래밍을 하다보면, 모르거나 막히는 부분이 생깁니다. 문제를 어떻게 해결 할 것인가는 수많은 방법이 존재하겠지만, 그 방법조차 모를경우 우리는 타인에게 도움을 요청합니다. 다행히도 프로그래머에게 허용된 몇 안되는 커뮤니티가 아직 존재하기에 우리는 익명의 누군가에게 도움을 요청하고 그 해답을 얻을 수 있는 기회를 얻게 된겁니다. 다만, 질문의 방법을 몰라 제대로 된 답변을 얻지 못하거나 무시당하는 경우가 비일비재 하여 그 안타까움에 몇가지 적어볼까 합니다. 물론 저 역시도 아래 항목을 100% 실천하고 있다고 생각되진 않지만, 가능한 지켜준다면 누군가의 마음을 움직여 좋은 답을 얻을 수 있지 않을까요? 자, 이제 그 방법을 알아보죠! (본문에 사용된 예시는 게임코디 연구소 질답란에서 발췌, 가공.. 더보기 이전 1 2 3 4 다음
