서울시는 6월 1일부터 교통 혼잡을 막기 위해서 자동차 10부제를 시행한다. 자동차 10부제는 자동차 번호의 일의 자리 숫자와 날짜의 일의 자리 숫자가 일치하면 해당 자동차의 운행을 금지하는 것이다. 예를 들어, 자동차 번호의 일의 자리 숫자가 7이면 7일, 17일, 27일에 운행하지 못한다. 또한, 자동차 번호의 일의 자리 숫자가 0이면 10일, 20일, 30일에 운행하지 못한다.
여러분들은 일일 경찰관이 되어 10부제를 위반하는 자동차의 대수를 세는 봉사활동을 하려고 한다. 날짜의 일의 자리 숫자가 주어지고 5대의 자동차 번호의 일의 자리 숫자가 주어졌을 때 위반하는 자동차의 대수를 출력하면 된다.
입력
첫 줄에는 날짜의 일의 자리 숫자가 주어지고 두 번째 줄에는 5대의 자동차 번호의 일의 자리 숫자가 주어진다. 날짜와 자동차의 일의 자리 숫자는 모두 0에서 9까지의 정수 중 하나이다.
출력
주어진 날짜와 자동차의 일의 자리 숫자를 보고 10부제를 위반하는 차량의 대수를 출력한다.
소스코드 - 파이썬
import sys
input = sys.stdin.readline
d = int(input())
cars = map(int, input().split())
answer = 0
for c in cars:
if c == d:
answer += 1
print(answer)
소스코드 -C++
#include <cstdio>
using namespace std;
int main(int argc, char** argv)
{
int d, car, i;
int cnt = 0;
scanf("%d", &d);
for(i=0; i<5; i++) {
scanf("%d", &car);
if (d == car) {
cnt++;
}
}
printf("%d", cnt);
}
소스코드 -Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int i, cnt = 0;
for(i=0; i<5; i++) {
if(n == sc.nextInt()) {
cnt++;
}
}
System.out.println(cnt);
}
}
import sys
input = sys.stdin.readline
# k : star, n : max_len
def midStar(k, n):
blank = " "
star = "*"
stars = star * k
blanks = blank * ((n-k)//2)
return blanks + stars
def printStars(n):
l = 2*n-1
for k in range(1,l+1):
if k == n:
s = midStar(1, l)
elif k < n:
s = midStar((n-k)*2+1, l)
elif k > n:
s = midStar((k-n)*2+1, l)
print(s)
N = int(input())
printStars(N)
소스코드 -C++
#include <cstdio>
#include <string>
#include <iostream>
using namespace std;
string midStar(int k, int n) {
string blank = " ";
string star = "*";
string stars = "";
int blank_n = (n-k)/2;
int star_n = k;
int i;
for (i=0; i<blank_n; i++) {
stars.append(blank);
}
for (i=0; i<star_n; i++) {
stars.append(star);
}
return stars;
}
int main() {
int n, k;
string s;
scanf("%d", &n);
int l = 2*n-1;
for(k=1; k<l+1; k++) {
if (k == n) {
s = midStar(1, l);
} else if (k < n) {
s = midStar((n-k)*2+1, l);
} else if (k > n) {
s = midStar((k-n)*2+1, l);
}
cout << s << endl;
}
}
소스코드 - Java
import java.util.*;
public class Main {
public static String midStar(int k, int n) {
String blank = new String(" ");
String star = new String("*");
String stars = new String("");
int blank_n = (n-k)/2;
int star_n = k;
int i;
for (i=0; i<blank_n; i++) {
stars += blank;
}
for (i=0; i<star_n; i++) {
stars += star;
}
return stars;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int l = 2*n-1;
int k;
String s = new String("");
for (k=1; k<l+1; k++) {
if (k == n) {
s = midStar(1, l);
} else if (k < n) {
s = midStar((n-k)*2+1, l);
} else if (k > n) {
s = midStar((k-n)*2+1, l);
}
System.out.println(s);
}
}
}
흔한 수학 문제 중 하나는 주어진 점이 어느 사분면에 속하는지 알아내는 것이다. 사분면은 아래 그림처럼 1부터 4까지 번호를 갖는다. "Quadrant n"은 "제n사분면"이라는 뜻이다.
예를 들어, 좌표가 (12, 5)인 점 A는 x좌표와 y좌표가 모두 양수이므로 제1사분면에 속한다. 점 B는 x좌표가 음수이고 y좌표가 양수이므로 제2사분면에 속한다.
점의 좌표를 입력받아 그 점이 어느 사분면에 속하는지 알아내는 프로그램을 작성하시오. 단, x좌표와 y좌표는 모두 양수나 음수라고 가정한다.
입력
첫 줄에는 정수 x가 주어진다. (−1000 ≤ x ≤ 1000; x ≠ 0) 다음 줄에는 정수 y가 주어진다. (−1000 ≤ y ≤ 1000; y ≠ 0)
출력
점 (x, y)의 사분면 번호(1, 2, 3, 4 중 하나)를 출력한다.
해결방안
1. (x > 0 and y > 0) : 1사분면
2. (x < 0 and y > 0) : 2사분면
3. (x < 0 and y < 0) : 3사분면
4. (x > 0 and y < 0) : 4사분면
소스코드 - 파이썬
import sys
input = sys.stdin.readline
def Quadrant(x,y):
if x > 0:
if y > 0:
return 1
elif y < 0:
return 4
elif x < 0:
if y > 0:
return 2
elif y < 0:
return 3
return 0
x = int(input())
y = int(input())
q = Quadrant(x,y)
print(q)
소스코드 - C++
#include <cstdio>
using namespace std;
int Quadrant(int x, int y) {
int q = 0;
if (x > 0) {
if (y > 0) {
q = 1;
} else if (y < 0) {
q = 4;
}
} else if (x < 0) {
if (y > 0) {
q = 2;
} else if (y < 0) {
q = 3;
}
}
return q;
}
int main() {
int x, y, q;
scanf("%d", &x);
scanf("%d", &y);
q = Quadrant(x, y);
printf("%d", q);
}
소스코드 - Java
import java.util.*;
public class Main {
public static int Quadrant(int x, int y){
int q = 0;
if (x > 0) {
if (y > 0) {
q = 1;
} else if (y < 0) {
q = 4;
}
} else if (x < 0) {
if (y > 0) {
q = 2;
} else if (y < 0) {
q = 3;
}
}
return q;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
int y = sc.nextInt();
int q = Quadrant(x,y);
System.out.println(q);
}
}
월드전자는 노트북을 제조하고 판매하는 회사이다. 노트북 판매 대수에 상관없이 매년 임대료, 재산세, 보험료, 급여 등 A만원의 고정 비용이 들며, 한 대의 노트북을 생산하는 데에는 재료비와 인건비 등 총 B만원의 가변 비용이 든다고 한다.
예를 들어 A=1,000, B=70이라고 하자. 이 경우 노트북을 한 대 생산하는 데는 총 1,070만원이 들며, 열 대 생산하는 데는 총 1,700만원이 든다.
노트북 가격이 C만원으로 책정되었다고 한다. 일반적으로 생산 대수를 늘려 가다 보면 어느 순간 총 수입(판매비용)이 총 비용(=고정비용+가변비용)보다 많아지게 된다. 최초로 총 수입이 총 비용보다 많아져 이익이 발생하는 지점을 손익분기점(BREAK-EVEN POINT)이라고 한다.
A, B, C가 주어졌을 때, 손익분기점을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 21억 이하의 자연수이다.
출력
첫 번째 줄에 손익분기점 즉 최초로 이익이 발생하는 판매량을 출력한다. 손익분기점이 존재하지 않으면 -1을 출력한다.
해결 방안
1. 손익분기점을 구하기 위한 판매개수를 n으로 두고 수학적으로 접근한다.
생산비용 = A + (B * n)
판매비용 = C * n
손익 분기점 = (판매비용 - 생산비용 > 0)
= (C*n) - (A + (B*n)) > 0
= (C-B)*n - A > 0
= n > A / (C-B)
2. 손익 = (C-B)*n - A 에서 A,B,C는 자연수이므로 C-B가 0보다 작거나 같으면 손익은 항상 음수이므로 손익 분기점이 존재하지 않는다.(n = -1) 3. n > A / (C-B) 를 만족하는 n은 math.floor(A/(C-B) + 1)을 이용하여 구할 수 있다. 이는 다음과 같은 코드와 같은 작업을 한다.
if (A % (C-B) == 0):
n = A//(C-B) + 1
else:
n = A//(C-B) + 2
4. 2,3을 코드로 정리하면 다음과 같다.
if C - B <= 0:
n = -1
else:
n = math.floor(A/(C-B) + 1)
소스 코드
import sys, math
input = sys.stdin.readline
'''
cost = A + (B * n)
sale = C * n
BreakEventPoint = (sale - cost > 0)
sale - cost > 0
= (C*n) - (A + (B*n)) > 0
= (C-B)*n - A > 0
= n > A / (C-B)
if C - B <= 0:
n = -1
else:
n = math.floor(A/(C-B) + 1)
'''
def BreakEventPoint(A,B,C):
if C - B <= 0:
n = -1
else:
n = math.floor(A/(C-B) + 1)
return n
def main():
# input
A,B,C = list(map(float, input().split()))
n = BreakEventPoint(A,B,C)
print(n)
main()
[알고리즘] 깊이 우선 탐색(DFSDepth First Search) 과 너비 우선 탐색(Breadth First Search)
문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.
해결 방안
1. DFS, BFS의 그래프 기본 클래스를 생성한다. 2. self.graph를 collections.defaultdict(list)로 dictionary를 생성하면 self.graph의 새로운 key값을 사용할 때 따로 초기화해주지 않아도 list로 자동 생성해주므로 다음과 같이 소스 코드를 간단히 작성할 수 있다.
self.graph = dict()
if not key in self.graph:
self.graph[key] = [value]
else:
self.graph[key].append(value)
# collections.defaultdict 사용시
from collections import defaultdict
self.graph = defaultdict(list)
self.graph[key].append(value) # new key의 경우 자동으로 리스트 생성
3. self.node는 결과값으로 방문한 점을 순서대로 표시해줄 리스트 4. addEdge(u, v)함수는 연결되어 있는 정점들을 graph에 저장한다. 입력값의 간선은 양방향이므로 graph[u].append(v), graph[v].append[u] 양방향으로 저장한다. 5. sortEdge()함수는 graph의 각 정점에 연결된 정점들을 순서대로 정렬한다. 이 문제에서 한 정점에 여러개의 정점이 연결되어 있는 경우에 번호가 적은 점부터 방문하기 위해서 필요하다. 6. visited = defaultdict(lambda: False)정점을 방문했는지 확인하기 위해서 필요한 dictionary데이터로 2.설명에 첨언하면 visited[key]가 정의되지 않았을 때 visited[key] == False 값을 확인하는 순간에 visited[key]의 값을 자동으로 False로 초기화해준다. 실제 key를 방문하는 순간에 dictionary 값을 생성하여 확인하기 때문에 메모리 관리가 효율적으로 가능하다. 7. DFS는 DFSUtil 재귀함수를 사용하여 Deep First Search를 구현하고, BFS는 queue를 생성하여 Breadth First Search를 구현한다.
소스 코드
from collections import defaultdict
import sys
class GraphDFS:
def __init__(self):
self.graph = defaultdict(list)
self.node = []
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def sortEdge(self):
for i in self.graph:
self.graph[i] = list(sorted(self.graph[i]))
def DFSUtil(self, v, visited):
visited[v] = True
self.node.append(v)
for i in self.graph[v]:
if visited[i] == False:
self.DFSUtil(i, visited)
def DFS(self, s):
self.sortEdge()
self.node = []
visited = defaultdict(lambda: False)
self.DFSUtil(s, visited)
return self.node
class GraphBFS:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def sortEdge(self):
for i in self.graph:
self.graph[i] = list(sorted(self.graph[i]))
def BFS(self, s):
self.sortEdge()
self.node = []
visited = defaultdict(lambda: False)
queue = []
queue.append(s)
visited[s] = True
while queue:
s = queue.pop(0)
self.node.append(s)
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
return self.node
def main():
input = sys.stdin.readline
dfs = GraphDFS()
bfs = GraphBFS()
N, M, V = list(map(int, input().split()))
for m in range(M):
x, y = list(map(int, input().split()))
dfs.addEdge(x,y)
bfs.addEdge(x,y)
dfs_node = dfs.DFS(V)
bfs_node = bfs.BFS(V)
print(' '.join(list(map(str, dfs_node))))
print(' '.join(list(map(str, bfs_node))))
main()
