본문 바로가기

전체 글

 (76)
[프로그래머스] 신고 결과 받기 (카카오 문제) (Python) 문제 - 신고 결가 받기 https://programmers.co.kr/learn/courses/30/lessons/92334 코딩테스트 연습 - 신고 결과 받기 문제 설명 신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다. 무지가 개발하려는 시스템은 다음과 같습니다. 각 유저는 한 번에 한 명의 programmers.co.kr 나의 풀이 def solution(id_list, report, k): n = len(id_list) id_list_num = {} # id별 인덱스 부여 new_report = set(report) #중복 제거 new_group = [[] for _ in range(n+1)] # 연결 정보 담은 배열 counting = {} #..
[백준] 2252번_줄 세우기 (Python/파이썬) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 입력..
[알고리즘] 최단 경로 알고리즘 - 플로이드 워셜(Floyd-Warshall) 플로이드 워셜 - 모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산 - 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘 수행 - 다만 매 단계마다 방문하지 않은 노드 중 최단 거리를 갖는 노드를 찾는 과정 X - 2차원 테이블에 최단 거리 정보 저장 - 다이나믹 프로그래밍 유형에 속함 - 각 단계마다 특정한 노드 K를 거쳐 가는 경우 확인 - a에서 b로 가는 최단거리보다 a에서 k를 거쳐 b로 가는 거리가 더 짧은지 검사 플로이드 워셜 동작 과정 [초기단계] 그래프 준비하고 최단 거리 테이블 초기화 [1단계] 1번 노드를 거쳐 가는 경우를 고려하여 테이블 갱신 [2단계] 2번 노드를 거쳐 가는 경우를 고려하여 테이블 갱신 [3-4단계] 마지막으로 4번 노드를 거쳐 ..
[알고리즘] 최단 경로 알고리즘 - 다익스트라(Dijkstra) 최단경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘 - 다양한 문제 상황들 1 ) 한 지점에서 다른 한 지점까지의 최단경로 2 ) 한 지점에서 다른 모든 지점까지의 최단경로 3 ) 모든 지점에서 다른 모든 지점까지의 최단경로 - 각 지점은 그래프에서 노드로 표현 - 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로 - 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작 - 현실 세계의 도로(간선)은 음의 간선으로 표현 X - 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류(다이나믹 프로그래밍 원리도 이용됨) - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정 반복 다익스트라 최단 경로 ..
[알고리즘] 위상 정렬 알고리즘 위상 정렬 - 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열 - 예시 ) 선수과목을 고려한 학습 순서 설정 진입차수(Indegree) - 특정 노드로 들어오는 간선의 개수 진출차수(Outdegree) - 특정 노드에서 나가는 간선의 개수 위상 정렬 알고리즘 [큐를 이용한 위상 정렬 알고리즘 동작 과정] 1. 진입차수가 0인 모든 노드를 큐에 넣음 2. 큐가 빌 때까지 다음의 과정을 반복 1 ) 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거 2 ) 새롭게 진입차수가 0이 된 노드를 큐에 넣음 -> 결과적으로 각 노드가 큐에 들어온 순서가 위상 정렬을 수행한 결과 위상정렬 그래프 준비 -> 사이클 없는 방향 그래프(DAG) [초기단계] 진입차수가 0인 모든..
[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘 신장 트리 - 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미 - 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 함 최소 신장 트리 - 최소한의 비용으로 구성되는 신장 트리를 찾아야 하는 경우 [최소 신장 트리 문제 예시] - N개의 도시가 존재하는 상황 -> 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결될 수 있게 도로를 설치하는 경우 - 두 도시 A, B를 선택했을 때 A에서 B로 이동하는 경로가 반드시 존재하도록 도로 설치 크루스칼 알고리즘 - 대표적인 최소 신장 트리 알고리즘 - 그리디 알고리즘으로 분류 [크루스칼 알고리즘 동작과정] 1. 간선 데이터를 비용에 따라 오름차순으로 정렬 2. 간선을 하나씩 확인하며 현재의 간..
[알고리즘] 서로소 집합 (Disjoint Sets) 서로소 집합(Disjoint Sets) - 공통 원소가 없는 두 집합 - {1,2}와 {3,4}는 서로소 관계 서로소 집합 자료구조 - 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 1 ) 합집합(Union) : 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 2 ) 찾기(Find) : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - 서로소 집합 자료구조는 합치기 찾기(Union Find) 자료구조로 불림 여러 개의 합치기 연산이 주어졌을 때, 서로소 집합 자료구조의 동작 과정은 다음과 같음 1. 합집합(Union) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인 1 ) A와 B의 루트 노드 A', B' 를 각각 찾음 2 ) A'를 B'의 부모 노드로..
[자바스크립트] 브라우저 렌더링 과정 최근 프로젝트를 하면서 서버에서 받아온 HTML 파일을 어떻게 브라우저에 나타나는 지에 대해 자세하게 모르고 있다는 사실을 알게 되었다. 따라서, 브라우저 렌더링 과정에 대해 이해한 바를 정리해보았다. 1. 브라우저 - 브라우저는 인터넷에 접속할 때 사용하는 크롭, 사파리, 인터넷 익스플로어 등과 같은 것을 말한다. - 브라우저에 대해 웹에서 페이지를 찾아서 보여주고, 사용자가 하이퍼링크를 통해 다른 페이지로 이동할 수 있도록 하는 프로그램을 말한다. - 유저가 선택한 자원을 서버로부터 받아와서 유저에게 보여준다. 2. DOM(Document Object Model, 문서 객체 모델) - HTML, XML 문서의 프로그래밍 인터페이스 - 구조화된 표현을 제공하며 프로그래밍 언어가 DOM 구조에 접근할 수..

티스토리툴바