분류 전체보기

[백준 1948] 임계경로 (C++)

1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net 단방향 그래프(DAG)임을 유의 특정 도시에서 모두 만나는데 걸리는 시간은 시작도시에서 특정 도시까지 가는데 걸리는 모든 시간 중 최댓값이 된다. 따라서 BFS를 통해 모든 정점에 대해 걸리는 시간 값을 구할 수 있다. 도착 정점까지 쉬지 않고 달려야 하는 사람이 지나는 도로의 개수의 의미는 도착 정점을 시작점으로 해서 되돌아 갈 때, '도착 정점까지 가는데 걸리는 시간 - 도착 정점을 시작으로 특정 정점까지 가는데 걸리는 시간 = 시..

[백준 17398] 통신망 분할 (C++)

17398번: 통신망 분할 첫 번째 줄에는 통신탑의 개수인 자연수 N, 통신탑 사이의 연결의 개수인 자연수 M, 통신망 연결 분할 횟수인 자연수 Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 100,000, 1 ≤ Q www.acmicpc.net 문제를 읽어보니 통신망들의 집합을 구현해야 했다. 서로 연결이 되어있는 통신망, 즉 하나의 정점으로 귀납되는 노드들 사이의 한 간선을 끊으면 2개로 나뉠 텐데 몇 개씩으로 나눠지는지를 구하면 된다. 풀이 방법을 떠올리기까지 꽤 오래 걸렸는데 처음에 노드의 간선을 끊는 동작을 하나의 쿼리로 보고 세그먼트 트리를 구성해서 풀어야 하나?라는 말만 그럴듯한 이상한 생각을 했다. 그러다가 일단 input에 입력을 다 받고 보니 반대로 생..

[Java] 추상 클래스와 인터페이스 (abstract class & interface)

Java 추상 클래스와 인터페이스는 기능적으로 아주 유사하다.Java를 공부하면서 이 둘이 왜 나눠졌는지 이해하는건 자바 언어의 철학을 이해하는데 한 걸음 다가간다고 생각했다. 따라서 둘의 공통점 및 구분되는 특징을 조사해보고 인터페이스, 추상 클래스를 사용하는 클래스 다이어그램을 설계하고 코드로 실습을 해 보았다.인터페이스의 특징 - 동일한 기능을 가지는 객체들에 대한 기능적인 '틀'을 제공한다. A(자식) Has a B(부모) - 다중 상속이 가능하다. - 하나의 규칙으로 적용된다. - 자식 요소들과 Has a (~할 수 있는)  관계를 가진다. (자식들이 공통된 기능을 가진다.) - 즉, 상속 받는 객체들이 할 수 있는 '기능'에 대해 미리 정의한다. - 주로 '~able'로 끝나도록 명명한다. e..

[Django] ORM 쿼리 최적화 (select_related, annotate, aggregates)

Django는 처음엔 배우기 쉬웠는데 배우면 배울수록 알아야할게 많아진다... 기초만 보고 단순한 웹 사이트를 만드는데는 장고만큼 쉬운게 없을 것 같다.. 관리자 페이지도 있고, 기본적인 유저 모델이나 인증 시스템이 만들어져 있기 때문에. 그런데 객체지향을 제대로 이해해야지만 장고 프레임워크도 이해할 수 있을 것 같다. 객체지향 모델의 동작 방식이 이해가 되면 객체의 메소드들을 오버라이딩해서 커스터마이징 해야하고.. 인증 방식도 커스터마이징 해야하고.. 할게 많음 그러다 django_rest_framework를 만나면 새로운 프레임워크를 처음부터 배우는것같은 느낌이 든다.. rest_framework에서 serializer를 처음 만났을때 엄청난 거부감이 들면서 왜 써야하지 싶었는데.. 사실 아직도 정확..

[백준 1863] 스카이라인 쉬운거 (C++)

1863번: 스카이라인 쉬운거 첫째 줄에 n이 주어진다. (1≤n≤50,000) 다음 n개의 줄에는 왼쪽부터 스카이라인을 보아 갈 때 스카이라인의 고도가 바뀌는 지점의 좌표 x와 y가 주어진다. (1≤x≤1,000,000. 0≤y≤500,000) 첫 번째 지점 www.acmicpc.net 스택 높이가 바뀌는 y좌표만 저장하면 된다. 높이가 점점 증가하다가 갑자기 감소했을 때, while문을 돌면서 stack의 top에 위치한 높이가 현재 높이와 같거나 작아질 때까지 pop을 수행한다. 마지막에 stack에 남아있는 건물의 수 만큼 답에 더해준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33..

[백준 1103] 게임 (C++)

1103번: 게임 줄에 보드의 세로 크기 N과 가로 크기 M이 주어진다. 이 값은 모두 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 보드의 상태가 주어진다. 쓰여 있는 숫자는 1부터 9까지의 자연수 또는 www.acmicpc.net 백트래킹과 DP가 합쳐진 문제? 중요 - 방문처리 방문한 곳에 도달했다면 사이클을 이루므로 무한번 이동가능. -1 출력 후 exit()으로 프로그램 종료 나머지는 현재 위치좌표를 가지는 dp배열을 통해 최대 이동 횟수를 재귀적으로 메모이제이션 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 ..

[Network] 네트워크 계층 : OpenFlow 프로토콜

오픈 플로우(OpenFlow) 프로토콜 오픈플로우 프로토콜은 TCP상에서 포트번호 6653을 가지고 동작한다. 컨트롤러는 연결 설정을 하려는 스위치에 대하여 TCP 포트 6653을 리스닝하고 있어야 한다. 스위치에 오픈플로우 펌웨어를 삽입한다. 컨트롤러와 스위치간에 전달되는 메시지를 알아보자 컨트롤러 -> 스위치(라우터) 설정 : 컨트롤러가 스위치의 설정 파라미터들을 문의하거나 설정할 수 있도록 한다. 상태 수정 : 컨트롤러가 스위치 플로우 테이블의 엔트리를 추가/제거 또는 수정하거나 스위치 포트의 특성을 설정하기 위해 사용된다. 상태 읽기 : 컨트롤러가 스위치 플로우 테이블과 포트로부터 통계 정보와 카운터 값을 얻기 위해 사용한다. 패킷 전송 : 컨트롤러가 제어하는 스위치의 지정된 포트에서 특정 패킷을..

Comparison: AWS vs Azure vs GCP

클라우드 컴퓨팅이란 인터넷 기반 컴퓨팅의 일종이다. 인터넷상의 가상화된 서버에 프로그램을 두고 필요할 때마다 컴퓨터나 스마트폰 등에 불러와 사용하는 서비스이다. 클라우드(Cloud)라는 단어가 말해주듯, 인터넷 통신망 어딘가에서 구름에 싸여 보이지 않는 컴퓨팅 자원(CPU, 메모리, 디스크 등)을 원하는 대로 가져다 쓸 수 있다. 구름에 싸여 있다는 것은 그 내부를 알지 않아도 얼마든지 내가 원하는 것을 꺼내어 사용할 수 있다는 것이며, 인터넷이 연결된 어느 곳에서든 이것을 보장받을 수 있다는 뜻이다. 클라우드의 장점으로는 서버를 직접 구매할 때 고려해야 할 전력, 위치, 서버 세팅, 확장성을 고민하지 않고 서비스 운영에만 집중할 수 있다는 점이다. 이러한 장점 덕분에 클라우드 서비스 인프라 시장의 매출..

[Network] 네트워크 계층 : SDN(Software-Defined Networking)

SDN 제어평면에서의 패킷 포워딩은 목적지 기반 포워딩이 아닌 일반적인 포워딩을 사용한다. 즉 출발지/목적지의 IP주소만 가지고 패킷을 알맞게 포워딩하는것이 아니다. 네트워크 계층, 링크 계층에서의 출발지/목적지 주소에 이어서 트랜스포트, 네트워크, 링크 계층에 있는 패킷 헤더의 많은 다른 값에 기반해서 포워딩이 이루어진다. SDN 구조의 네가지 특징 플로우 기반 포워딩 : SDN으로 제어되는 패킷 스위치(라우터, 링크계층 스위치)에서 패킷 포워딩은 세그먼트, 데이터그램, 링크 프레임의 헤더의 다양한 값을 가지고 포워딩을 한다. (OpenFlow 1.0그림의 11가지 헤더 참고) 이러한 패킷 포워딩 규칙은 각 스위치의 플로우 테이블에 기록된다. 그래서 SDN 제어평면 에서는 모든 네트워크 스위치들의 플로..

[백준12762 ] 롤러코스터 (C++)

12762번: 롤러코스터 첫째 줄에 개조하고자 하는 구간의 길이 \(N\)이 주어진다. 구간의 길이는 1,000을 넘지 않는 자연수이다. 둘째 줄에 구간 내에 있는 각 기둥들의 높이가 주어진다. 기둥의 높이는 10,000 이하의 자연 www.acmicpc.net 숫자가 감소하다가 증가하는 경우, 숫자가 계속 증가하는 경우, 숫자가 계속 감소하는경우의 수를 모두 구하면 된다. 여기서 숫자가 계속 증가하는 경우의 수를 구하는 이유는 아래와 같다 1. 기둥을 마음대로 삭제할 수 있다. 2. "그리고 롤러코스터의 진행 방향은 공사가 끝난 후 결정된다." => 앞, 뒤 부터 시작해서 감소하는 수열만 찾으면 된다. 구간의 시작부분이 양 끝 모두 될 수 있다. 따라서 특정 인덱스를 시작으로하는 감소하는 수열의 길이를..