# Problem Solving
[PS] 백준 11404번 플로이드
https://www.acmicpc.net/problem/11404정점 n(n <= 100)개, 간선 m(m <= 100,000)개인 가중 그래프에서 모든 정점 간의 최단 거리를 출력하는 문제이다. 단, 가중치는 100,000이하의 자연수이고 도달하
[PS] 백준 1727번 커플만들기
https://www.acmicpc.net/problem/1727남자 n명, 여자 m명이 있을 때, 최대한 많이 짝지어 준 후에 짝끼리의 성격 차의 합이 최소가 되게 하려 한다. 이 때 최소를 구하는 문제이다.도저히 풀 수 없어 풀이를 보고 말았다. 다이나믹
[PS] 백준 4195번 친구 네트워크
https://www.acmicpc.net/problem/4195 문제 설명 > 어떤 사이트의 친구 관계가 생긴 순서대로 주어졌을 때, 두 사람의 친구 네트워크에 몇 명이 있는지 구하는 프로그램을 작성하는 문제이다. '친구1 친구2' 이런 관계가 주어지면 친구1의 친
[PS] 백준 1766번 문제집
https://www.acmicpc.net/problem/17661번 부터 N번까지의 문제가 있다. 문제의 난이도는 1번이 제일 쉽고 그 다음이 2번, 3번, ..., N번이다. 다음 조건을 만족하는 문제 풀이 순서를 구하는 문제이다. N개의 문제는 모두 풀어
[PS] 백준 2042번 구간 합 구하기
https://www.acmicpc.net/problem/2042N(N <= 1000,000)개의 수가 순서대로 주어진다. 이 때 p ~ q번째 수 까지의 합을 구하는 연산과 x번째 수를 변경하는 연산이 있다. 이 떄, M + K (M <= 10,0
세상에서 가장 쉬운 알고리즘 정리 2. 알고리즘의 기초
비유 : 요리 - 식재료 → 일련의 단계적인 조리과정(레시피) → 음식알고리즘 - 일련의 단계적인 처리과정 → 결과(정보) 알고리즘(algorithm) : 주어진 문제의 결과를 생성하기 위해 모호하지 않고 간단하며 컴퓨터가 수행 가능한 유한개의 일련의 명령을 순서적으
[PS] 백준 2234번 성곽
https://www.acmicpc.net/status?user_id=rhqjatn2398&problem_id=2234&from_mine=1그리드가 주어지고 각 칸의 네 방향에 벽이 있을 수 있다. 벽으로 둘러싸인 칸들이 하나의 방이 된다. 이 때, 이 성에
[PS] 백준 2812번 크게 만들기
https://www.acmicpc.net/problem/2812N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하는 문제이다. 이 때, K < N <= 500,000 이고 주어지는 수는 0으
[PS] 백준 10830번 행렬 제곱
https://www.acmicpc.net/problem/10830N x N 행렬 A 가 주어졌을 때, A ^ B 의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다.이 때, B <= 100,000,000,000 이다.B가 매우 크다. 어떤 수의
세상에서 가장 쉬운 알고리즘 정리 1. 알고리즘 공부전 선행 공부(자료구조)
나는 방통대 컴퓨터과학과 3학년에 재학중이다...이전부터 알고리즘(algorithms)이라는 단어만 막연하게 들어도 어렵고, 못 할거 같았다. 그래도 일단 남들? 다 하는거 나도 제대로 부딪혀 보자 싶어서.. 3학년 1학기 때.. 마음먹고 선택을 했다.. 이 글은 내가
[PS] 백준 16236번 아기 상어
https://www.acmicpc.net/problem/16236N x N 격자 칸에 물고기와 아기 상어 1마리가 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 가장 처음에 아기 상어의 크기는 2이다. 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동한
[PS] 백준 17471번 게리맨더링
https://www.acmicpc.net/problem/17471그래프가 주어지고, 그래프를 두 개의 그룹으로 분할해야 한다. 각 그룹에 속한 정점들은 같은 그룹에 속한 정점들끼리 간선으로 연결되어 서로 연결되어 있어야 한다. 그룹에는 하나이상의 정점이 포함
[Python] 코딩테스트 유형 - 10-3. 위상 정렬
위상 정렬 : 사이클이 없는 방향 그래프(DAG)의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것 DAG에 대해서만 수행 가능 > DAG (Directed Acyclic Graph) > 사이클이 없는 방향 그래프 ex) 선수강 과목을 고려한
[Python] 코딩테스트 유형 - 10-2. 최소 신장 트리(MST), Kruskal 알고리즘
: 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프💡 트리의 조건 : 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건: 최소한의 비용으로 구성되는 신장 트리예시 : N개의 도시가 있을 때, 두 도시 사이에 도로를 놓아 전체
[Python] 코딩테스트 유형 - 10-1. Union-Find
서로소 집합(Disjoint Sets) : 공통 원소가 없는 두 집합 Union-Find 자료구조 (서로소 집합 자료구조) : 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 두 종류의 연산을 지원함 Union(합집합) : 두 개의 원
[PS] <인프런> 코딩 테스트 ALL IN ONE : INTRO
자료구조자료구조 : 데이터를 저장하고 관리하는 방식arraydynamic arraylinked listqueuestackhash tabletreegraph특정 알고리즘을 위해 꼭 사용해야 하는 자료구조가 있을 수 있고, 어떤 자료구조를 사용하느냐에 따라 알고리즘의 구현
[PS] 백준 2250번 트리의 높이와 너비
https://www.acmicpc.net/problem/2250이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그렸을 때, 각 레벨의 너비 중 최대 너비를 갖는 레벨과 그 너비를 구하는 문제이다. 1\. 이진트리에서 같은 레벨에
[PS] 백준 2206번 벽 부수고 이동하기
https://www.acmicpc.net/problem/2206N x M 그리드로 표현되는 맵이 있고 각 칸이 이동 가능하면 0, 벽이 있어 이동이 불가능하면 1 로 이루어져 있다. (1, 1)에서 (N, M)의 위치까지 이동하는 최단 거리를 구하는 문제이다