YunaNote

🔷 유클리드 호제법( euclidean - algorithm ): 두 수의 최대 공약수를 구하는 알고리즘이다. 유클리드 호제법을 사용하기 위해선 MOD 연산을 알고있어야한다.  MOD ?최대 공약수를 구하는 연산으로 Modulo 나머지 연산으로도 불린다. 🔷 유클리드 호제법의 원리🔻 큰 수에서 작은 수로 나누는 MOD 연산 🔻 앞에서 진행한 작은 수와 MOD 연산 결과값과 MOD 연산 수행🔻 반복하다가 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택

🔷 오일러 피( Eluer's phi )?해당 기호를 사용하며 phi라고 읽으며 대표적으로 서로소 관련 문제에서 사용된다. 🔷P[N] ?1부터 N까지 범위에서 N과 서로소인 자연수의 개수를 뜻한다. 💡 서로소란?두 수 사이의 관계에서 공통되는 약수가 최대 1이며 1 밖에 없는 수를 뜻한다. 서로소의 예시로는 아래와 같이 확인 할 수 있다. ◾ 5의 약수 : 1 , 5◾ 6의 약수 : 1 , 2 , 3 , 6◻ 5와 6의 최대 공약수는 1이며 두 수가 일치하는 수는 1이므로 서로소라고 할 수 있다.  🔷  오일러 피의 원리🔻 구하고자 하는 오일러 피의 범위만큼 배열 초기화🔻 2부터 시작해서 인덱스가 같을 때(소수일 때) 현재 선택된 숫자의 배수에 해당되는 수(K)의 배열 끝까지 탐색 후  P[i..

🔷 소수(Prime number)?1과 자기 자신 외의 약수가 존재하지 않는 수를 의미한다. 🔷 소수를 구하는 판별법에라토스테네스의 체 ( Sieve of Eratosthenes ) : 소수들을 대량으로 빠르고 정확하게 구하는 방법 🔷 에라토스테네스의 체의 원리🔻 구하고자하는 소수의 범위만큼 1차원 배열 생성한 뒤 초기화한다.🔻 2부터 시작해서 현재 선택된 숫자의 배수의 해당되는 수를 모두 지운다. (이때 자기자신은 지우지않으며, 이미 지워진 수는 건너뛴다.)🔻 배열이 끝날 때까지 반복한 뒤 2부터 시작하여 남아 있는 수를 모두 출력한다  🔷 에라토스테네스의 체의 시간 복잡도이중 for문을 이용하여 O(N^2) 으로 판단될 수 있지만 배수를 삭제하여 생략하는 경우도 있기 때문에 O(n * l..

https://www.acmicpc.net/problem/1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 문제 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 ..

삽입 정렬(Insertion Sort)이란? 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입해 정렬하는 방식 시간 복잡도는 O(n^2)로 느린 편 매 순서마다 해당 원소를 삽입할 수 있는 위치를 찾아 해당 위치에 삽입 삽입 정렬 수행과정 🔹현재 Index에 있는 데이터 값을 선택 🔹현재 선택한 데이터가 정렬된 데이터 범위에 삽입된 위치를 탐색 🔹삽입 위치부터 index에 있는 위치까지 shift 연산 수행 🔹삽입 위치에 현재 선택한 데이터를 삽입하고 index++ 연산 수행 🔹전체 데이터의 크기만큼 index가 커질 때까지 수행 ( 선택할 데이터가 없을 때까지 반복 수행 ) 탐색하는 부분에서 이진 탐색과 같은 탐색 알고리즘을 통해 시간 복잡도를 줄일 수 있다. 관련 문제 [ 백준 ]..

해당 포스팅은 " Do it! 알고리즘 코딩 테스트 " 기반으로 정리 하였습니다 💡디버깅(Debugging) : 오류를 찾아 바로잡는 과정 디버깅은 개발자로써 많이 사용하고 중요한 기술이고, 코딩 테스트 문제를 풀면서도 잘 활용해야한다. 💡디버깅을 하는 법 🔶 디버깅 방법 🔸 디버깅 하고 싶은 줄에 중단점을 설정, 중단점의 경우 여러 개를 설정 할 수 있다. 🔸 디버깅을 실행하면 중담점부터 1줄씩 실행하거나 다음 중단점까지 실행할 수 있어 값이 의도대로 바뀌는지 확인 가능하다. 🔸 원하는 수식을 입력해 논리 오류를 파악 할 수 있다. 🔹디버깅을 하고자 하는 줄에 중단점(Break Poing)을 설정 🔹디버그창 확인, 로컬, 자동, 조사식 창 활용 🔹단축키를 이용하여 디버그 실행 한 단계씩 코드 실행 : ..

스파르타코딩 클럽의 1시간 만에 정복하는 코딩테스트 합격법의 최지웅 선생님의 강의를 듣고 작성하였습니다. 코딩테스트 란? 취업을 위한 필수 관문으로 기술역량, 문제해결능력, 코드 구현 능력을 파악하기 위한 테스트이다. 최근 채용 공고를 확인해 본 결과 1. 서류 심사 > 코딩테스트 2. 코딩 테스트 > 서류 심사 의 과정을 거쳐 채용을 하고 있으며 좋은 회사를 가기 위해선 코딩테스트를 꼭 준비해야한다. 그럼 코딩 테스트는 왜 보는가 ?? 기술 역량 : 프로그래밍 문법, 알고리즘, 자료구조 등 평가 문제 해결 능력 : 주어진 제시문을 이해, 문제 분석, 해결책을 찾기 코드 구현 능력 : 코드 구현 파악, 스타일 가이드, 주석 등 코드를 통한 협업 파악 코딩 테스트를 진행하기 위해선 2가지의 방법으로 진행합..