전체태그 보기

#알고리즘 (245개의 포스트)

underlier12

알고리즘 학습 #12

약 8시간 전0개의 댓글
알고리즘 12. 프림 알고리즘 최소 신장 트리 - 신장 트리란 특정한 그래프에서 모든 정점을 포함하는 그래프 - 최소 신장 트리는 스패닝 트리 중에서 간선의 가중치 합이 가장 작은 트리 image.png image.png 프림 알고리즘의 순서 1. 그래프에서 정점 하나를 선택하여 트리 T에 포함 2. T에 포함된 노드와 T...
sa833591

Roman to Integer(leetcode Easy)

약 14시간 전0개의 댓글
문제: https://leetcode.com/problems/roman-to-integer/ 문제 === Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. 이렇게 푸니 문제는 풀 수 있었지만 소스가 너무 길어져 가독성이 떨어졌다. - 현재 풀이 ...
sa833591
문제: https://programmers.co.kr/learn/courses/30/lessons/49189 문제 === 문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 ...
underlier12
알고리즘 11.AVL 트리 AVL 트리의 정의 - 균형이 갖춰진 이진트리 - 완전 이진 트리는 검색 시 O(log N)의 시간 복잡도 유지 - AVL 트리는 간단한 구현으로 완전 이진 트리에 가까운 형태가 되도록 함 AVL은 해당 논문을 발표한 G.M. Adelson-Velskii와 E.M. Landis의 이름을 따서 지은 이름 AV...
알고리즘? 그거 재귀로 풀면 되는 거 아니야?
worjd2
시작 알고리즘 공부를 조금씩 하기 시작하고 나면 재귀 함수을 통해 문제를 해결하는 방법을 접하게 됩니다. 재귀 함수를 배우고 나서 코드가 간결해지는 것을 느꼈고 재귀 함수를 너무 사용하는 부작용🤪이 나타났습니다. 대게 일반적인 반복문으로 문제를 해결하고 난 뒤 재귀로 해결하면 코드가 간결해지는 경우가 많았기 때문에 알고리즘 문제를 보고 고민을 하다 ...
underlier12
알고리즘 10. 이진 탐색 트리 이진 탐색 트리의 정의 - Binary Search가 항상 동작하도록 구현한 이진 트리 - 탐색 속도 극대화 시킨 자료구조 - 항상 부모 노드가 왼쪽 자식보다 크고 오른쪽 자식보다 작음 이진 탐색 트리의 탐색 - 한번 확인 할 떄마다 확인할 원소의 개수가 절반씩 줄어든다는 점에서 효율적 - 완전 ...
hyeon930
SWEA 5658 보물상자 비밀번호 첫 인상에 비해서 쉬운 문제였지만 놓친 것이 몇 가지 있었던 아쉬운 문제였다. 문제를 잘 읽자, 정리를 잘 하자 문제 풀이 1. 자물쇠 각 변의 16진수를 10진수로 변환시켜 TreeSet에 삽입한다. 2. 시계 방향으로 회전한다. 3. N-1 번 회전하며 1~2를 반복한다. 4. TreeSet 을 배열로 바...
hyeon930
SWEA 5656 벽돌 깨기 시뮬레이션 문제로 구현해야하는 것이 많아서 까다로웠다. 하지만 특별히 신경써야하는 부분 없이 문제에 주어진 사항만 구현하면 통과할 수 있는 문제였다. 내 구현력이 얼마나 부족한지도 느낄 수 있었다. 문제 풀이 어떻게 풀이를 할지에 대한 생각은 문제를 보고 바로 떠올랐다. 1. 구슬을 N번 떨어뜨릴 때 선택할 수 있는...
underlier12
알고리즘 09. 너비 우선 탐색 너비 우선 탐색의 정의 - Breadth First Search는 너비를 우선으로 하여 탐색하는 알고리즘 - 맹목적으로 전체 노드를 탐색할 때 사용 - 큐 자료구조에 기초 고급 그래프 탐색 알고리즘에 자주 활용 너비 우선 탐색의 과정 1. 탐색 시작 노드를 큐에 삽입하고 방문 처리 2. 큐에서...
dltlsgh5
문제 : https://www.acmicpc.net/problem/2169 처음 문제를 접했을 때, 메모이제이션과 백트래킹 방식을 이용해서 접근했었다. code설명 친구에게 물어봤더니 전형적인 dp문제라고 한다. 위에서는 한 좌표를 기준으로 3가지 경로가 있다고 생각해서 bfs적으로 접근했지만 조건을 쪼개보니 다음과 같은 규칙을 찾을 수 있...
underlier12
알고리즘 08. 깊이 우선 탐색 깊이 우선 탐색의 정의 - Depth First Search는 깊이를 우선적으로 탐색하는 알고리즘 - 전체 노드를 맹목적으로 탐색하고자 할 때 사용 - 스택 자료구조에 기초 깊이 우선 탐색은 모든 경우의 수를 탐색하고자 할 때 쉽게 사용 깊이 우선 탐색의 순서 1. 탐색 시작 노드를 스택에 삽...
underlier12
알고리즘 07. 순차 탐색과 이진 탐색 순차 탐색의 방법 - Sequential Search는 특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색하는 방법 - 찾은 뒤 해당 인덱스를 반환 image.png image.png image.png ![image.png](https://images.velog.io/post-images/...
sik2

[TIL]2020-01-19 (일)

4일 전0개의 댓글
알고리즘 - C언어 강좌를 활용해 포인터와 구조체, 동적 메모리 할당을 공부했다. - 대학때는 포인터까지 수업을 하고 뒷부분은 흐지부지 되었던 걸로 기억한다. 그리고 그 포인터도 딱히 큰 관심이 없어서 그냥 시험 볼 정도만 보고 제대로 공부하지 않았다. - 이번엔 정말 궁금해서 공부하는 것이여서 포인터가 왜 쓰이는지 어떨때 유용한지 공부했다. - 구조체 ...
underlier12
알고리즘 06. 우선순위 큐 우선순위 큐의 필요성 - 우선 순위를 가진 데이터들을 저장하는 큐 - 데이터를 꺼낼 때 우선 순위가 높은 데이터가 가장 먼저 나오는 특징 - 운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등에서 적용 우선순위 큐와 큐의 차이점 - 일반적인 형태의 큐는 선형 - 우선 순위 큐는 트리 구조(최대 힙으로...
underlier12
알고리즘 05. 이진 트리의 구현 및 순회 이진 트리의 순회 image.png 전위 순회 - 자기 자신 출력 - 왼쪽 자식 출력 - 오른쪽 자식 출력 전위 순회 결과 : 30 - 17 - 5 - 23 - 48 - 37 - 50 중위 순회 - 왼쪽 자식 출력 - 자기 자신 출력 - 오른쪽 자식 출력 중위 순회...
underlier12
알고리즘 04. 기수 정렬 기수 정렬의 정의 - Radix Sort는 자릿수를 기준으로 차례대로 데이터를 정렬 - 각 자릿수를 기준으로 분류하여 가장 큰 자릿수가 D일 때 O(DN)의 시간 복잡도 기수 정렬의 과정 image.png image.png image.png ![image.png](https://images.ve...
프로그래머스 - 위장
giraffelim
오늘 오랜만에 알고리즘 사이트에 접속해 알고리즘을 풀어보았고 내가 풀었던 해답을 포스팅 하려고 합니다. 다른 좋은 방법이 있다면 댓글로 소통을 할 수 있으면 좋을거 같습니다!. 위장 - 프로그래머스 - 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경,...
sa833591
문제: https://leetcode.com/problems/add-two-numbers/ 문제 === You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nod...
underlier12
알고리즘 03. 계수 정렬 계수 정렬의 정의 - Counting Sort는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘 - 각 데이터를 바로 크기 기준으로 분류함 O(N)의 시간 복잡도 계수 정렬의 과정 계수 정렬에서는 숫자 자체가 인덱스가 됨 image.png image.png image.png ![image...
underlier12
알고리즘 02. 퀵 정렬 퀵 정렬의 정의 - 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법 - 교체하는데에 N번, 교체 이후 원소가 반으로 나누어져 전체 원소를 나누는데 평균 log N번 소요 O(NlogN)의 시간 복잡도 퀵 정렬의 과정 image.png image.png image.png ![image...