우당탕탕 개발일지

바이러스 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 128 MB 155042 71672 48258 45.774% 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨..

DFS와 BFS 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 257464 99001 58825 37.235% 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 ..

1. 개방 폐쇄 원칙(OCP: Open-Closed Principle)이란? - 기존 코드를 변경하지 않으면서, 새로운 기능을 추가할 수 있도록 설계되어야 한다는 원칙 - 확장(새로운 기능 추가)에는 열려있고, 수정에는 닫혀있음 - 다형성과 확장이라는 객체 지향의 장점을 극대화 - * 다형성: 기능을 변경하더라도 애플리케이션 전체를 바꿀 필요는 없음 따라서 기능을 추가할 때, 1)추상화 클래스 추가 2)상속관계 맞추기 이 두가지 단계만으로 유연한 확장이 가능하다. 2. 원칙으로 무엇을 지켜야 하나? 1. 변경(확장)될 것과 변하지 않을 것을 엄격히 구분한다. 2. 이 두 모듈이 만나는 지점에 추상화(추상클래스 or 인터페이스)를 정의한다. 3. 구현체에 의존하기보다 정의한 추상화에 의존하도록 코드를 작성..

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

맨날 input(), input().split()만 쓰다가, 뭔가 더 간편하고 속도도 빠른 방법은 없을지 찾아보았다. [상황 1] 한 줄에 여러 값을 int타입으로 받고, 이를 리스트로 저장하는 상황 사용할 함수: input(), split(), map(), list() n = list(map(int, input().split())) n # [3, 6, 9, 12, 15] [상황 2] 여러 줄에 걸쳐 여러 값을 int타입으로 받고, 이를 리스트로 저장하는 상황 import sys sys.stdin.read().splitlines()로 줄별로 입력값을 읽어온다. 그리고 그 값을 리스트에 넣는다. import sys data = sys.stdin.read().splitlines() [추가] input() 대..

BFS = Breath First Search 너비 우선 탐색 가장 가까이에 있는 노드부터 우선 탐색 일반적인 경우 실제 수행시간은 DFS보다 좋다. collections 모듈의 deque 라이브러리를 사용한다. 예제 코드 from collections import deque # BFS 메서드 정의 def bfs(graph, start, visited): # 큐 구현을 위해 deque 라이브러리 사용 queue = deque([start]) # 탐색한 노드를 방문처리 visited[start] = True # 큐가 빈 상태가 될 때까지 반복 while queue: v = queue.popleft() print(v, end = ' ') # 탐색한 노드와 연결되어 있지만 아직 안 읽은 노드들을 큐에 삽입 f..