코딩테스트22 8. 기타 그래프 이론 안녕하세요. 😊 오늘은 기타 그래프 이론에 대해 정리해보려고 합니다. 서로소 집합 서로소 집합(Disjoint Sets)이란 공통 원소가 없는 두 집합을 의미 서로소 집합 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조는 두 종류의 연산을 지원 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조 라고 불리기도 한다. 여러 개의 합치진 연산이 주어졌을 때 서로소 집합 자료구조의 동작 과정 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. A와 B의 루트 .. 2023. 11. 17. 7. 최단 경로 알고리즘 안녕하세요. 😊 오늘은 최단 경로 알고리즘 에 대해 정리해보려고 합니다. 최단 경로 알고리즘 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드 에서 출발하여 다른 모든 노드 로 가는 최단 경로를 계산 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다. 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류됨 매 상황에서 가장 비용이 적은.. 2023. 11. 16. [Python3] 18406 - 럭키 스트레이트 문제 > 18506번 https://www.acmicpc.net/problem/18406 ✔ 문제 설명 '럭키 스트레이트'는 게임 내에서 점수가 특정 조건을 만족할 때만 사용할 수 있다. 특정조건이란 현재 캐릭터의 점수를 N이라고 할 때 자릿수를 기준으로 점수 N을 반으로 나누어 왼쪽 부분의 각 자릿수의 합과 오른쪽 부분의 각 자릿수 부분의 합을 더한 값이 동일한 상황을 의미 ✔ 예시 현재 점수가 123,402 라면 왼쪽 부분의 각 자릿수 합은 1+2+3, 오른쪽 부분의 각 자릿수 합은 4+0+2 이므로 두 합이 6으로 동일하여 럭키 스트레이트 사용 가능 ✔ 입력 조건 첫째 줄에 점수 N이 정수로 주어진다. (10≤𝑁≤99,999,999) 단, 점수 N의 자릿수는 항상 짝수 형태로만 주어진다. ex) 총.. 2023. 11. 15. [Python3] 코딩테스트 Lv.1 - 이상한 문자 만들기 코딩테스트 문제 > 모든 문제 > 난이도 : Lv.1 https://school.programmers.co.kr/learn/courses/30/lessons/12930 ✔ 문제 설명 문자열 s는 한 개 이상의 단어로 구성되어 있다. 각 단어는 하나 이상의 공백문자로 구분되어 있다. 각 단어의 짝수번째 알파벳은 대문자로, 홀수번째 알파벳은 소문자로 바꾼 문자열을 리턴하는 함수, solution을 생성 ✔제안 사항 문자열 전체의 짝/홀수 인덱스가 아니라, 단어(공백을 기준)별로 짝/홀수 인덱스를 판단해야 한다. 첫 번째 글자는0번째 인덱스로 보아 짝수 번째 알파벳으로 처리해야 한다. ✔ 입출력 예 s return "try hello world" "TrY HeLlo WoRlD" 내가 쓴 코드 (성공) def .. 2023. 11. 14. 6.다이나믹 프로그래밍 안녕하세요. 😊 오늘은 다이나믹 프로그래밍 에 대해 정리해보려고 합니다. 다이나믹 프로그래밍 다이나믹 프로그래밍은 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법입니다. 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 합니다. 다이나믹 프로그래밍 구현은 일반적으로 두 가지 방식(탑다운과 보텀업)으로 구성됩니다. 다이나믹 프로그래밍은 통계 계획법이라고도 불립니다. 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란 어떤 의미를 가질까요? 자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법' 을 의미합니다. 반면에 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사.. 2023. 11. 13. 5. 이진 탐색 알고리즘 안녕하세요. 😊 오늘은 이진 탐색 알고리즘에 대해 정리해보려고 합니다. 이진 탐색 알고리즘 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 이진 탐색의 시간 복잡도 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 log₂N에 비례 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다. 2단계를 거치면 8개 가량의 데이터만 남는다. 3단계를 거치면 4개 가량의 데이터만 남는다. 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는.. 2023. 11. 12. 이전 1 2 3 4 다음
