분류 전체보기

[백준 4013] ATM C++

4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차 www.acmicpc.net 강한 연결 요소, 다이나믹 프로그래밍 처음 풀어보는 플레2 문제였다. 풀려서 기분이 매우 좋았음 우선 모든 정점들을 dfs로 순회하며 각 정점의 SCC를 구해줬다. SCC를 구하면서 해당 SCC에 속하는 현금의 양 + 해당 SCC에 레스토랑이 있는지 판단해 주었다. 구한 SCC를 통해서 SCC 그래프를 만들어 주었다. -> make_sccgraph() 이제 DP문제로 바뀌게 되었다. 시작점의 SCC에서 출발해, 레스토랑이 있는 SCC까지의 거리의 ..

[백준 1321] 군인 C++

1321번: 군인 첫째 줄에 부대의 개수 N(1 ≤ N ≤ 500,000)이 주어지고, 이어서 각 부대의 군사 수를 나타내는 정수가 N개 주어진다. 각 부대의 군사 수는 1000보다 작거나 같은 자연수이다. 그 다음 줄에 명령의 개 www.acmicpc.net 세그먼트 트리 10개월 만에 다시 풀어보는 세그먼트 트리문제이다. 우선 a ~ b 구간의 부대의 인원의 합을 하나의 노드로 잡고 세그먼트 트리를 만들었다. 특정 부대의 증원이나 감원을 할 때는 업데이트 쿼리를 만들어서 수행했다. ex) 2번 부대의 인원이 늘어났다면 1-5번, 1-3번, 2번 노드의 인원이 모두 같은 수 만큼 증가해야 한다. 마지막으로 군인을 배치하는 arrangement쿼리를 만들었다. 군인의 번호가 왼쪽 자식 노드의 최대 인원보..

[Docker] container, image 삭제

nginx이미지와 컨테이너를 삭제해보자 특정 이미지를 통해 만든 컨테이너가 존재한다면 해당 이미지는 삭제할 수 없다. 삭제 순서 구동 중인 컨테이너 중지하기 컨테이너 삭제 이미지 삭제 컨테이너 중지하기 + 컨테이너 시작, 재시작 docker stop webserver // docker stop {컨테이너 이름 or 컨테이너 ID} docker start {컨테이너 이름 or 컨테이너 ID} docker restart {컨테이너 이름 or 컨테이너 ID} stop : 컨테이너를 중지시킨다. start : 컨테이너를 시작한다. restart : OS를 재부팅하듯이 컨테이너를 재시작한다. 컨테이너 삭제 docker rm {컨테이너 이름 or 컨테이너 ID} // 모든 컨테이너 삭제 // docker rm $(..

[Docker] Nginx 웹서버 구동해보기

컨테이너에 대하여 [Container 시리즈] 00. Container/ Docker란 뭔가요? Container / Docker 컨테이너.. 들어봤는데 무엇인지 잘 모르겠다..라고 생각하시는 분들을 위하여 이 글을 연재합니다. 1. Container 보통 IT인이 아니라고 한다면 '컨테이너' 라는 말을 듣는다면 다음의 tech.osci.kr 이미지에 대하여 도커 컨테이너(Container)와 이미지(Image)란? 도커(Docker)는 Immutable Infrastructure Paradigm 이라는 개념을 기반으로 하기 때문에, 서비스 환경(서비스 인프라) 부분을 이미지화(실행파일화)하여 배포한 뒤 가급적 변경하지 않고 사용한다고 이전 hoon93.tistory.com Nginx 이미지를 받아와서 ..

[Docker] 계획 + 공부를 위해 참고한 사이트 모음

docker를 자유자재로 사용할 수 있다고 느낄 때까지 docker를 공부하면서 알게된 내용을 포스팅 할 예정 우선은 지금까지 docker를 공부하면서 알게 된 내용을 통해 Nginx, MariaDB, Django+gunicorn 을 container화 하여 개발 및 배포 환경을 만든것을 포스팅 모든 docker 명령어들은 실습을 해보면서 어떤식으로 쓰이는지 알아가는 방식으로 포스팅 모든 실습은 Mac OS에서 진행하였으며 Windows 분들은 Vmware 또는 Virtual Box 에 ubuntu Linux 설치 + docker 설치 후 진행해주세요! Docker 시작하기 초보를 위한 도커 안내서 - 도커란 무엇인가? 도커를 처음 접하는 시스템 관리자나 서버 개발자를 대상으로 도커 전반에 대해 얕고 넓..

[백준 1944] 복제 로봇 C++

1944번: 복제 로봇 첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어 www.acmicpc.net 최소 스패닝 트리 - MST 현재 로봇이 복제를 거듭하며 열쇠를 찾으러 다니는 이동거리를 가장 작게 해야한다. 전체 이동거리를 가장 작게 해야하므로 다익스트라가 아니라 MST알고리즘을 사용해야 한다는걸 알았다. 입력을 받으면서 시작점과 모든 열쇠들은 정점이 되므로 정점 vector에 넣어준다. 정점들 간의 거리를 BFS를 통해 모두 구하고 간선의 정보를 저장한다. BFS 매번 돌면 자신을 제외하고 시작점을 포함한(M-1+1) M번 ..

[백준 2262] 토너먼트 만들기 C++

2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 그리디 랭킹이 높은 사람이 반드시 이기기 때문에 우승자는 항상 1번이다. 부전승이 여러번 있어도 상관없기 때문에 매번 가장 랭킹이 낮은 사람(번호가 높은 사람)만 경기를 하게 했다. 랭킹이 가장 낮은 사람(자신)의 양 옆 사람 중에서 자신과 랭크 차이가 적게 나는 사람과 경기를 치러야 한다. 랭크 차이가 많이 나는 사람과 경기를 치르게 되면 그 사람은 랭크차이가 많이 나는 만큼 경기를 더 많이 치러야 하기 때문이다. 경기를 더 많이 한다면 그만큼 최솟값과는 멀어질 수..

[백준 2211] 네트워크 복구 C++

2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다 www.acmicpc.net 다익스트라 최소 스패닝 트리의 탈을 쓴 다익스트라 문제였다. 끊어진 그래프에서 최소 개수의 회선만을 복구해야 한다고 하길래 n-1개의 간선을 연결시켜서 모든 컴퓨터를 연결해 주는 MST 문제로 착각했다. 위 그래프에서 MST는 어떻게 될지 생각해보자 2-3, 2-4, 1-3 간선이 모여서 MST를 이룰 수 있다. 하지만 이 때 1 -> 2로가는 비용은 5가 되고, 1 -> 4로 가는 비용은 7이 된다. 각각 기존의 최단거리였던 4, 3..

[백준 1774] 우주신과의 교감 C++

1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소 스패닝 트리 Minimum Spanning Tree (MST) - Kruskal 크루스칼 알고리즘(Kruskal Algorithm)을 활용한 최소 스패닝 트리 구하기 모든 간선(Edge)에 대해 가중치가 가장 작은 간선부터 이어나가면서 최소 스패닝 트리를 구하는 알고리즘이다. 유니온 파인 hyeo-noo.tistory.com 통로의 개수 1000개 이미 연결이 되어있다고 입력받은 노드들끼리는 Union_Node를 수행한다. adj..

[백준 1602] 도망자 원숭이 C++

1602번: 도망자 원숭이 첫 번째 줄에는 도시의 개수 N (2 ≦ N ≦ 500) 과 도로의 개수 M (0 ≦ M ≦ 10,000), 그리고 질문의 개수 Q (0 ≦ Q ≦ 40,000) 가 주어진다. 그 다음 줄에, N개의 정수로 각 도시에서 멍멍이가 원숭이를 괴 www.acmicpc.net 플로이드-와샬 쿼리(Q)가 최대 4만개 들어온다. 출발도시와 도착도시가 주어졌을 때 플로이드 최단경로를 구하고, 경로상의 정점 중 멍멍이가 괴롭힐 수 있는 최대 시간을 구한다면 O(40000 * N^3) 으로 시간초과가 발생한다. 플로이드의 특징을 잘 생각해보자 경유하는 점은 보통 1 ~ N 번까지의 점을 순서대로 경유하도록 한다. 이는 그냥 편의를 위해서 사용하는 순서이고 경유점의 순서가 바뀌더라도 결국 A->..