나다김강니

11689 : GCD(n, k)문제자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 자연수 n (1 ≤ n ≤ 1012)이 주어진다. 출력GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 출력한다.입력출력11544524 문제 풀이오일러피로 푸는 문젠데 강의에 나온 이론으로 풀면 자꾸 런타임에러나는거;; 💡 오일러 피 구하는 다른 방법 - 소인수분해 사용 N 에서 소인수를 찾아내고 𝝓(n) 값을 갱신한다.소인수의 배수를 제거하여 N을 점점 작게 만든다.N이 소수로 남아잇다면, 𝝓(n) 값을 최종적으로 갱신한다.(예시)N = 36, res = 36소인수 확인 및 처리(N%i==0 확인, N..

DP(Dynamic Programming)복잡한 문제를 간단한 여러 개의 문제로 분리하여 부분의 문제들을 해결해 최종적으로 복잡한 문제의 답을 구한다. 💡 동적 계획법(DP)의 핵심 이론1️⃣  동적 계획법의 원리와 구현 방식 큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결과값은 항상 같아야 한다.모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다.-> 메모이제이션 기법동적 계획법은 톱-다운 방식(top-down)과 바텀-업(bottom-up) 방식으로 구현할 수 있다. 2️⃣  피보나치 수열(동적 계획법의 가장 대표적인 문제)피보나치 수열 공식D[N] = D[N-1] + D[N-2] 동적 계..

조합조합은 nCr로 표현되고, n개의 숫자 중 r개를 뽑는 경우의 수를 뜻한다.순열은 nPr로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 말한다. 💡 순열과 조합의 핵심 이론🔍  순열예를 들어, 5개중 순열을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)의 결과값이 나온다.  🔍  조합예를 들어, 5개중 조합을 이용해 3개를 뽑으면 (5*4*3*2*1)/(2*1)/(3*2*1)의 결과값이 나온다.(2*1) -> 순서가 다른 경우의 수를 제거하는 역할  ☝🏻  조합 점화식 세우기1️⃣ 특정 문제를 가정하기5개의 데이터에서 3개를 선택하는 조합의 경우의 수 구하기 2️⃣ 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제 생각하기먼저 5개의 데이터 중 4개는 ..

LCA(최소 공통 조상)트리 그래프에서 임의의 두 노드를 선택했을 때 각각 자신을 포함해 거슬러 올라가다 처음 공통으로 만나게 되는 부모 노드 💡 최소 공통 조상의 핵심 이론ⓐ 일반적인 최소 공통 조상 구하기트리의 높이가 크지 않을 때는 일반적인 방법으로 구한다. 1️⃣ 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장한다. 2️⃣ 만약, 선택된 두 노드의 깊이가 다른 경우 더 깊은 노드의 노드를 부모 노드로 1개씩 올려주면서 depth를 맞춰준다. 3️⃣ 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복한다.     이때 처음 만나는 노드가 최소 공통 조상이 된다.  ⓑ 최소 공통 조상 빠르게 구하기트리의 높이가 매우 커질 경우, 시간 제약 문..

세그먼트 트리주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조이다.더 큰 범위로 '인덱스 트리'라고 불린다. 💡 세그먼트 트리의 핵심 이론세그먼트 트리의 종류는 구간 합, 최대 · 최소 구하기로 나눌 수 있다. 1. 트리 초기화하기리프 노드의 개수가 데이터의 개수(N)이상이 되도록 트리 배열을 만든다.트리 배열 크기 구하기 : 2k ≥ N을 만족하는 k의 최솟값을 구하고 2k x 2를 트리 배열의 크기로 정의한다.그리고 주어진 데이터들을 2k에 해당하는 인덱스부터 채운다. 만약, 8개의 데이터가 주어졌을 때는 {5, 8, 4, 3, 7, 2, 1, 6}2의 제곱수 중 처음으로 8보다 크거나 같아지는 제곱수를 구한다 -> k=3배열의 크기는 23 x 2 = 16배열을 채..

이진 트리이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 말한다. 💡 트리의 핵심 이론이진 트리의 종류데이터를 트리 자료구조에 저장할 때 편향 이진 트리의 형태로 저장하면 탐색 속도가 저하되고 공간이 많이 낭비 된다.일반적으로 코테에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태를 떠올린다.  이진 트리의 순차 표현이진 트리는 아래와 같이 1차원 배열의 형태로 표현할 수 있다.자식 노드 인덱스 = 부모 노드 인덱스 x 2, 부모 노드 인덱스 x 2 + 1 구성 요소인덱스 연산제약 조건(N = 노드 개수)루트 노드index = 1 부모 노드index = 자식 노드 인덱스 / 2현재 노드가 루트 노드가 아님왼쪽 자식 노드index = 부모 노드 인덱스 x 2index * ..

트리트리는 노드와 에지로 연결된 그래프의 특수한 형태이다.순환 구조(사이클)를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 가진다.트리의 부분 트리 역시 트리의 모든 특징을 따른다. 💡 트리의 핵심 이론구성 요소설명노드데이터의 index와 value를 표현하는 요소에지노드와 노드의 연결 관계를 나타내는 선루트 노드트리에서 가장 상위에 존재하는 노드부모 노드두 노드 사이의 관계에서 상위 노드에 해당하는 노드자식 노드두 노드 사이의 관계에서 하위 노드에 해당하는 노드리프 노드트리에서 가장 하위에 존재하는 노드(자식 노드가 없는 노드)서브 트리전체 트리에 속한 작은 트리  💡 코딩테스트에서 트리가 나오는 유형① 그래프로 푸는 트리(DFS, BFS)② 트..

RESTREST는 Representational State Transfer의 약자로, HTTP 통신을 활용하기 위해 고안된 아키텍처이다.Representational인터넷상의 자원을 URI로 나타낼 수 있음을 의미URI로 표현된 자우너을 HTTP메서드를 이용해 CRUD 연산을 할 수 있다.State Transfer자원의 상태를 주고받는 것, 요청받은 자원의 상태를 전달하는 것💡 REST의 6가지 특징일관된 인터페이스자원을 나타내는 URI를 HTTP 메서드로 조작하는 일관된 인터페이스를 사용한다. HTTP를 따르는 모든 플랫폼에서 REST를 사용할 수 있다.클라이언트-서버 구조클라이언트와 서버 간에 요청-응답의 독립적인 구조를 가진다.클라이언트 : 서버에 요청을 보내고 응답을 대기서버 : 자원을 가지며 ..

HTTPHTTP는 인터넷상에서 데이터를 전송하기 위한 프로토콜로, TCP/IP 4계층에서 응용 계층에 속한다. HTTP의 특징 1️⃣ 비연결성(connectionless)비연결성이란 클라이언트에서 요청을 보낸 후 서버로부터 응답을 받으면 연결을 끊는 것을 의미한다.불특정 다수를 대상으로 하는 서비스에 유리하다.서버에서 응답은 받고 연결을 유지하려면 자원이 필요한데 비연결성으로 자원을 아낄 수 있다.하지만 연결을 유지하지 않기 때문에 서버가 클라이언트를 기억할 수 없다.동일한 클라이언트에서 연속적으로 요청이 오면 연결, 연결 해제를 반복해 자원을 낭비하게 된다. ☝🏻 위에서 말한 단점을 보완하기 위해 HTTP Keep Alive를 사용한다.HTTP Keep AliveHTTP 연결 시 일정 시간 동안 요..

TCPTCP는 전송 계층에 해당하는 네트워크 프로토콜로, 연결형 서비스를 지원하고 데이터의 신뢰성을 보장한다.송신부와 수신부의 연결을 확인하는 연결형 서비스패킷 교환 방식 : 패킷이 전달되는 회선이 정해져 있는 가상 회선 방식패킷 전송 순서가 보장된다.패킷의 수신 여부를 확인한다.송신부와 수신부가 1 : 1 통신을 한다.데이터 손실이 없음을 보장하므로 신뢰성이 높다.느리다☝🏻 패킷 교환 방식 2가지· 가상 회선 방식데이터를 주고받기 전에 패킷을 전송할 경로인 가상 회선을 설정해서 모든 패킷을 같은 경로로 전송 · 데이터그램 방식패킷마다 최적의 경로로 전송한다. 때문에 송신부에서 보낸 패킷 순서와 수신부에서 받는 패킷의 순서가 다를 수 있다. TCP 핸드셰이킹TCP에서는 연결형 서비스를 지원하기에 송신부..