MuviSsum

www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 문제: 백준이가 외치는 수들의 가운데 수를 매번 구하라. 문제 이해하기!! 우선순위 큐를 이용한 가운데 수 구하기 문제입니다. 최대 우선순위 큐와 최소 우선순위 큐를 동시에 이용해서 경계 값을 찾아내면 됩니다. 그래서 푼 방법은 1. T == 1인상황과 2 이상인 상황을 분리시킵니다. 2. 2인 상황에서 최소힙이 (지금까지 부른 수들의 갯수 // 2)보다 작으면 최대힙의 팝한 숫자나 현재 숫자를..

오랜만에 bisect 함수쓰면서 bisect함수랑 이분탐색을 훑어봐야지 하는 생각이 들더라구요. 그래서 문제를 하나 내고 1부터 1000,000,000까지의 값 중 임의값 찾기라는 임시문제를 내고 코드를 만들어 봤습니다. 먼저 파이썬의 bisect 라이브러리입니다. import bisect arr = range(1, 1000000000) idx = bisect.bisect_right(arr, 11) print(arr[idx]) # output: 12 arr = range(1, 1000000000) idx = bisect.bisect(arr, 11) print(arr[idx]) # output: 12 arr = range(1, 1000000000) idx = bisect.bisect_left(arr, 11..

준비 사항 및 참고 사항 Linux 서버(AWS Ec2, GCP compute, Vultr compute 등) 프론트와 서버는 React.js와 Express.js(GraphQL)을 기준으로 작성 DB는 생략 DB(PostgresQL) 도커 설치 참고 URL https://github.com/fksk94/TIL/blob/master/web/postgreSQL/PostgreSQL.md 설치 준비 해놓은 Linux 서버에 접속한다. 접속방법은 다양하지만, 요즘은 window에서도 putty가 없어도 git bash같은 다른 shell 프로그램을 이용하면 ssh 접속이 가능해지니까 bash에서 이런 방식으로(ssh -i {keyname}.pem ubuntu@{domain or Elastic IP}, ssh r..

네 번째 주제 - 장고 튜토리얼 Django Tutorial MTV패턴 기본 Django가 아닌 DRF를 대상으로 설명한다. 코드 포매터 Black 사용, AWS EC2 사용 시작 가상환경 생성 및 실행 # 파이썬 설치 및 버전확인 python -V # 가상환경 생성 python -m venv venv # 가상환경 실행 source venv/Scripts/activate 장고 설치 및 프로젝트 생성 # 설치 pip install Django # 버전확인 python -m django --version # 프로젝트 생성 django-admin startproject mysite # 프로젝트로 이동 cd mysite # 장고 실행 확인 python manage.py runserver # http://loca..

www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제: 주어진 배열에서 인접한 부분으로 위에서 부터 내려가며 숫자를 더할 때, 최소 값과 최대 값을 구하여라 문제 이해하기!! DP문제로, 앞에서 더한 인접한 부분 것들에 최대 값과 최소 값을 구해서 더해가며 밑으로 내려가면 되는 문제입니다. 하지만 이 문제만 나온다면 골드문제가 아니라 실버 1~2 정도 문제겠죠? 이 문제는 DP로 푸는 방법만 구하는게 아니라 실제로 사용되는 메모리의 양도 중요했던 문제입니다. 이 문제를 풀..

www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제: 모든 도시에 대해서 도시 A에서 B로 가는데 필요한 비용의 최솟값을 구하라. 문제 이해하기!! 모든 도시로 가는 최소 비용을 구하면 되는 문제입니다. 한 루트의 최소비용을 구할 때는 다익스트라를 쓰지만, 모든 곳의 최소비용을 구할 때는 플로이드 와샬을 쓰면 됩니다. 다만 주의할 점은 정점의 갯수 ** 3 이므로 정점의 갯수가 작을 때 쓸 수 있습니다. 그래서 푼 방법은 1. 처음 받는 루트와 비용을 최소..

www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 해당 문제는 1167번 문제와 같은 문제입니다.문제의 설명과 풀이 방법은 이전 글을 참고하시거나 해당 링크를 따라가시면 됩니다!링크: https://txegg.tistory.com/166 [BOJ] 1167. 트리의 지름 www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저..

www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제: 주어진 트리에서 트리의 지름을 구하여라 문제 이해하기!! 트리의 지름이란 원본 문제를 보면 설명이 나와있는데요, 임의의 정점에서 임의의 정점까지의 거리가 최대인 것을 뜻합니다. 그럼 어떻게 구해야할까요? 정점의 갯수는 10만으로 플로이드-와샬 알고리즘은 못 씁니다. 그럼 다익스트라를 써도 될까요? 으음.. DP로 저장한다고 하더라도 여러 정점을 살펴봐야하기에 힘들죠. 좀 더 기본적인 방향..

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제: 최댓값과 최솟값을 뺄 수 있는 이중 우선 순위 큐를 만들어라 문제 이해하기!! 이중 우선 순위 큐면 사실 deque을 이용해서 뒤에서 빼고 앞에서 빼면 되지만, 이 문제에서는 insert까지 생각해야 합니다. 그러므로 새로운 방식으로 짜야하는데요, 그 방법은 최소, 최대 힙 두개를 사용한 방법입니다. 제가 푼 방식을 설명하자면, 1. 최소 최대 힙을 이용하여 각 Insert마다 숫자를 받고, 해당 숫..

www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제: 집들이 연결되어 있는 단지를 파악하고 총 단지의 수와 각 단지의 집이 몇개인지 파악하라. 문제 이해하기!! 해당 문제는 딱 명확한 완전탐색이었습니다. BFS, DFS든 상관은 없구요, visit 배열로 방문체크만 해준다면 바로 풀리는 문제입니다. 제가 푼 방식을 설명하자면, 1. 입력받은 배열을 for문으로 돌려, 아직 방문하지 않은 곳이고 집이 있는 곳이라면 DFS를 수행합니다. 2. DFS구현: DFS..