원조맛집

문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수..

단순한 한 점이 아니라 방향성을 가지고 있는 점(좌표),혹은 그 방향 자체(크기)라고 봐도 될듯하다 위에서는 3차원까지만 예시를 했지만 이를 n차원까지 늘리면 n개의 원소를 요소로 가지는 리스트 또는 배열로 생각해볼 수 있다 같은 모양의 벡터끼리는 +- 그리고 성분곱(*)이 가능함 두 벡터의 경로를 이어 시작과 끝을 잇는 벡터가 두 벡터의 합이다 벡터의 차원에 상관없이 계산이 가능하다 여러가지 노름 방법이 있다 L1 노름은 각 성분의 절대값 크기를 모두 더한 것이다, 즉 요소의 경로를 하나하나 따라가며 크기를 잰것 L2노름은 피타고라스 정리를 이용해서 계산을 통해 거리를 구하는 느낌이다 기계학습의 목적에 따라 다른 노름이 사용된다 두 벡터 사이의 거리를 구할때는 뺄셈을 이용한다 두 벡터의 각도를 구할때는..

numpy 리스트는 데이터형이 같아야함 numpy 리스트와 python 리스트의 차이점 numpy리스트는 바로 숫자가 들어가고 python 리스트는 메모리가 할당되고 한번 더 타고 들어가서 값이 나오는 구조 이 때문에 numpy는 계산이 빠르고 python은 변동이 자유로움 또한 같은 데이터형을 넣기 때문에 메모리 크기가 일정하게 관리할 수 있음 파이썬에서는 -5 ~ 256까지는 메모리에 미리 할당되어 있기 때문에 위와 같은 일이 일어남 numpy는 새로운 공간에 순차적으로 할당하기 때문에 위와 같은 결과가 나옴 rank는 차원을 의미 스칼라는 0차원, 벡터는 1차원, 3차원부터는 텐서라고 함 ndim은 차원 즉 rank를 의미 size는 데이터의 갯수 여기서는 48개가 됨 shape의 표기는 (열) =..

재귀함수는 내부적으로 스택을 쓰므로 사실 스택 = 재귀이다 DFS는 완전탐색이라 모든 경우를 도는데 그 순서가 중요한 것이다 0 -> 1 -> 2 -> 3 -> 2 -> 4 -> 2 -> 1 -> 5 -> 6 -> 5 -> 1 -> 0 -> 7 ... 이 순서대로 감(깊이 우선 탐색) DFS를 코드로 나타내면 위와 같다 완전탐색이다 DFS와 탐색 순서가 다르다 0 -> 1 0 -> 2 1 -> 3 1 -> 4 2 -> 5 2 -> 6 ... 순서대로 탐색 큐를 사용한 BFS의 동작원리를 그림으로 나타내면 아래와 같다 BFS를 코드로 구현하면 다음과 같다 DFS & BFS 공통점 완전탐색, 무조건 답을 찾을 수 있지만 느리다 차이점 최단거리를 구하는 문제에서 BFS(너비우선탐색)은 목표 지점을 찾는 즉시 ..

그래프의 종류중에서 순환성 없는 무방향 그래프를 트리라고 함 (수학적, 이론상 트리) 트리의 개념 위 트리는 실제 전산학, 자료구조에서 많이 쓰이는 트리임(이론적 트리와 다름) 스택,큐 등등은 구현해주는 라이브러리가 대부분의 언어에서 있지만 그래프는 따로 없어 직접 구현해줘야함 1번째 방법 인접행렬 방향성이 있을 경우 행은 시작 index, 열은 도착 index 두 노드를 잇는 간선이 있을 경우에는 1 없으면 0 방향성이 없을 경우 무방향은 양방향과 같은 의미임 즉 간선이 연결되어 있으면 양쪽으로 출발과 도착이 가능하다는 의미 2번째 방법 인접리스트(연결리스트) 방향성이 있을 경우 행렬과의 차이 행렬은 연결이 없으면 0으로 자리를 차지했지만 리스트는 연결이 있는 부분만 공간을 차지함 엄밀히 따지면 연결리..

SNS에서 서로 연결되어 있는 상황이 그래프의 개념임 그래프는 Vertex(node, 한국말로 정점)와 이들을 연결하는 edge(한국말로 간선)으로 이루어져있음 방향 그래프는 방향대로만 이동 가능 전체 그래프 중에 한군데라도 순환 사이클이 있으면 순환 그래프라고 칭함 방향성이면서 비순환인 그래프를 DAG라고 함 이 때는 그래프가 3개가 아니라 1개임,그리고 이를 연결 요소라 부름 (연결요소가 3개인 그림)

문제 더보기 문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 입력 첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로..

더보기 문제 항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다. 파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다. 항승이는 길이가 L인 테이프를 무한개 가지고 있다. 항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다. 물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다. 입력 첫째 줄에 물이 새는 곳의 개수 N과 테이프의..

문제 더보기 문제 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 출력 첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다. 설명 Ai 가 Ai-1의 배수이기 때문에 그리디로 풀 수 있는 문제 큰 금액의 동전부터 나눠가면 되는 문제 코드 import sys N, M = map(..

모든 문제에 적용할 수 없다 초반에는 최악의 선택지로 보이지만 결국에는 더 나은 결과로 이어지는 선택지인 경우가 있는 문제에는 그리디를 적용할 수 없다 이 문제는 그리디 문제로 풀 수 있지만 이 문제는 그리디로 풀 수 없다 두 문제의 차이점은 숫자의 배수가 그 다음으로 큰 숫자가 될 수 있는지의 유무이다 10,50,100,500은 모두 작은 수의 배수로 구성이 가능하니 500을 가장 많이주고 그다음 100을 주는 방식이 가능하지만 400,500의 경우에는 배수가 안되고 그 말은 1200원처럼 400으로만 가능한 경우가 발생한다는 것이다 즉 그리디의 문제는 다음과 같다