코딩테스트/알고리즘10 JSON Parsing request와 json 패키지를 사용해서 JSON 데이터를 파싱할 때, 각 키의 데이터를 수정하려면 아래처럼 dictionary 형태로 변환시켜 value를 수정한다.data = {"key1":"value1"} data["key1"] = "value2" 전체 데이터를 스캔하여 특정 값을 가진 키를 찾으려고 한다. 아래 코드로 (for, if로) 전체를 확인하면서 원하는 값을 가진 키를 찾았다.data = { "key1":"value1", "key2":"value2", "key3":"value3", "key4":"value4", "key5":"value5", } for key in data: if "value3" == data[key]: print(key) break 간단한 데이터라면 위 방식으로도 충분.. 2023. 3. 19. [알고리즘] 순열과 조합 순열 (Permutation) 먼저 위키피디아에서 순열의 정의를 찾아봤다. 수학에서의 순열은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이라고 설명한다. 순열은 Permutation 의 앞글자 P로 표현한다. n개의 원소를 가진 집합을 임의의 다른 순서로 섞는 연산의 경우의 수는 n! 과 같고, n개의 원소 중 r개의 원소를 선택하여 순열하는 경우의 수는 P(n, r)과 같다. 아래 이미지는 위키피디아에서 P(n, r) 연산하는 방법을 설명한 부분이다. C++ 코드로 구현해보자. #include #include #include using namespace std; void func(){ vector v = {1, 2, 3}; do{ for(int i = 0; i < v.size(); i++){ .. 2022. 4. 21. [알고리즘] 다익스트라(Dijkstra) 최단 거리 알고리즘 그래프에서 간선들 사이의 가중치와 방향이 있을 때, 한 정점에서 다른 정점들까지의 최단 거리를 구할 수 있는 알고리즘은 다익스트라, 벨만포드, A* 등이 있고, 모든 정점에서 모든 정점의 최단 거리를 구하는 알고리즘에는 플로이드 워셜 알고리즘이 있다. 해당 알고리즘들을 응용하여 최단 거리를 가지는 경로를 구하는 방법도 있지만, 이 글에서는 다익스트라 알고리즘을 활용하여 최단 거리만 구해보겠다. 먼저 우선순위 큐를 사용하지 않는 최초의 다익스트라 알고리즘은 아래 과정과 같고 O(V2) 의 시간 복잡도를 갖는다. (2중 for 문 구조) 시작 노드 결정 현재 노드를 기준으로 각 노드의 최소 비용을 계산 방문 하지 않은 노드 중 최소 비용의 노드를 선택 선택된 노드를 기준으로 거리 비용을 .. 2022. 4. 11. [자료구조] 우선순위 큐 - 작성 중 큐는 FIFO, 우선순위 큐는 우선순위가 높은거 먼저 나옴 구현 1. 리스트를 이용한 구현 (큐로도 가능?) 2. 힙을 이용한 구현 시간 복잡도 1 -> 0(1), 삭제 시는 O(N) // 찾아서 삭제해야됨 2. -> O(log N) / O(log N) -> 삽입 삭제가 시간복잡도 동일하고 데이터의 입출력 과정이 힙정렬과 동일, 이때는 O(N log N) 힙은 완전 이진트리의 일종, 항상 루트 노드 제거 최소 힙은 루트 노드가 가장 작은 값을 가짐, 값이 작은 데이터가 우선 제거됨 ㄴ 넣었다 빼면 걍 오름차순 최대 힙은 루트 노드가 가장 큰 값이고 값이 가장 큰 데이터가 우선 제거됨, 내림차순 완전이진트리 : 루트부터 왼쪽, 오른쪽으로 순서대로 데이터가 삽입되는 트리 최소힙 구성함수 (min-heapif.. 2022. 4. 11. [알고리즘] 하노이의 탑 목적 하노이의 탑 알고리즘을 가시화하여 이해를 쉽게함 가시화된 알고리즘을 재귀 함수로 구현함 구현할 함수는 아래 2개임 ( A탑에 위치한 원반 개수는 N) int count_hanoi(int n) : A에서 C까지 N개의 원판을 이동시키는데 필요한 전체 개수 void hanoi(int n, int from, int to) : n번째 원판을 From에서 To로 이동시킴 탑 이동 알고리즘 (Hanoi Function) 하노이 탑의 이동을 재귀로 구현할 땐 아래 이미지의 이동 방식을 알면 됨 N이 2보다 더 큰 경우도 가장 밑에 있는 N번째 원판과 그위의 나머지 원판으로 부분을 나누면, 위와 같은 방식으로 이동이 가능함 hanoi(2, A, B)와 hanoi(2, B, C)의 이동을 직접 나열해보면 아래와 같.. 2022. 3. 9. [알고리즘] DFS/ BFS 목적 탐색 알고리즘에서 사용되는 표현 방식을 이해하고 직접 구현 탐색 알고리즘인 DFS(Depth First Search, 깊이 우선 탐색) 알고리즘에 대해 이해하고 직접 구현 탐색 알고리즘인 BFS(Breadth First Search, 너비 우선 탐색) 알고리즘에 대해 이해하고 직접 구현 인접리스트와 인접 행렬 위 와 같은 그래프가 있을 때, 이 그래프를 표현하는 방식은 크게 2가지(인접리스트, 인접행렬)가 있다. 각 표현 방식을 구현해보면 다음 코드와 같다. 1) 간선을 인접리스트로 변환 #include #include #include #include using namespace std; // 만들어진 그래프를 출력 void print_adjacency_list(map graph) { for (au.. 2022. 2. 5. [알고리즘] 달팽이 배열 채우기 1. 달팽이 배열 - 외곽부터 정사각형을 채우고 대각선 아래로 이동하여 반복 2. 방법별 코드 정리 2-1) 코드 - 외부부터 한바퀴씩 작성 - 시계방향으로 회전하는 달팽이 배열을 이동 좌표를 미리 계산하는 방식으로 작성 # 범위내 좌표이동 def add_direction(x, y, arr_direction, int_direction, int_k): a, b = 0, 0 # x 좌표 이동 next_x = x + arr_direction[int_direction][0] if next_x >= 0 and next_x = 0 and next_y < int_k.. 2021. 11. 6. [알고리즘] 함수 1. 가설 적용 코드 (C++) typedef unsigned long long ll; /* * input : ll input (정수) * output : int (1 or 0) * unsigned long long 형태의 정수를 넣으면 해당 수가 소수인지 여부를 알려준다. * 소수 판별 custom 버전 */ int is_prime_number_custom(ll input) { if (input < 2) { return 0; } for (ll j = 2; j 2021. 10. 11. [알고리즘] 0 ~ N 사이의 소수 개수 구하기 코드 1 - i(2 ~ N)를 j(2 ~ i)로 나누기 N을 입력받고 i를 2~N까지 1씩 더한다. j가 2부터 i에 도달할때까지 1씩 더하면서 i와 나누어 떨어지면 (1과 자기 자신을 제외한 인수가 있으므로) 소수가 아님. 위 연산을 반복해서 0~N 까지 소수의 개수를 하나하나 판단하여 카운팅한다. 각 범위를 계산하며 시간을 측정해본 결과는 아래 표와 같다. #include #include int main() { int i, j, cnt=0, flag=1; unsigned int min, max; // 범위 입력 printf("min : "); scanf_s("%d", &min); printf("max : "); scanf_s("%d", &max); // 2보다 작은 최소 범위가 입력되면 2로 고정 i.. 2020. 5. 19. [알고리즘] RSA 암복호화 알고리즘 C로 구현하기? ** 아래 코드는 검증되지 않았음(개인 학습용), 문제점 발견 시 댓글로 적어주시면 감사하겠습니다. 1. 이론 찾아보기 이론과 원리에 대해서 설명 https://kevin0960.tistory.com/entry/RSA-%EC%95%94%ED%98%B8%EC%99%80-%EA%B7%B8-%ED%95%B4%EB%8F%85 RSA 암호와 그 원리 RSA 암호와 그 원리 '암호학(Cryptography)의 모든 것' 에서 RSA 암호에 대해 간략하게 설명한 바 있다. RSA 암호는 공개키 암호(Public-key cryptography) 의 한 종류로 '큰 정수의 소인수분해의 난해성' 을 기.. kevin0960.tistory.com 구글링 중 찾은 사이트. RSA뿐만 아니라 ECC, 디피헬만 등 다양한 알고리.. 2020. 5. 17. 이전 1 다음
