data = input()
result = int(data[0])
for i in range(1, len(data)):
num = int(data[i])
if result <= 1 or num <= 1:
result += num
else:
result *= num
print(result)
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0
f = 0.0
# 인원수가 가장 낮은 공포도보다 적으면 안됨
while len(data) > data[0]:
f += 1.0/float(data[0]) # 1/공포도 만큼을 인원수만큼 더해서 1이 넘으면 그룹 결성
data.pop(0) # 인원을 빼줌
if f >= 1.0:
result += 1
f = 0.0
print(result)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
x, y = 1, 1
n = int(input())
plans = list(map(str, input().split()))
for plan in plans:
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i] # 반복문 안에서 선언된 변수도 외부에서 사용할 수 있는듯 하다
ny = y + dy[i] # c/c++이랑 다른 문법인것 같음
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
x, y = nx, ny
print(x, y)
- 시각
범위가 하루로 잡혀있고 하루는 86400초이기 때문에 복잡하게 생각할 것 없이 단순하게 모든 초를 조사하면 된다
n = int(input())
three = 15 # 0~60 사이 3이 포함된 숫자의 개수
result = 0
for i in range(n+1):
if i==3 or i==13 or i==23: # 시간에 3이 포함되면 1시간 전체가 포함됨
result += 3600
else: # 분에 3이 포함되면 60초가 모두 포함되어야 하고 그 외엔 초에 포함된 3의 경우만 고려하면 됨
result += three * 60 + (60-three) * three
print(result)
평소처럼 단순하게 생각했으면 더 쉽게 풀수 있었을텐데 경우의 수를 계산하느라 시간제한 15분이 넘어버렸다
s = list(input())
s.sort() # 리스트로 입력 받고 정렬
result = 0
while True:
# 오름차순 정렬 시 맨 앞에는 숫자가 오므로 숫자인지 판별
if s[0].isdigit():
result += int(s[0])
# 다음 문자 확인을 위해 리스트에서 제거
s.remove(s[0])
else:
break
print(''.join(s)+str(result))
이코테에서는 입력받은 문자열을 모두 순회하면서 문자는 리스트에, 숫자는 합산해서 따로 관리 후 마지막에 숫자 합을 리스트에 추가시켜서 출력함
다만 이런경우는 문자열 관련 기능이 강력한 파이썬에서나 가능한거고 c/c++ 환경에서는 완전 탐색으로 구현해야 할 것 같다
- 게임 개발
문제 이해하는게 가장 어려움. dx, dy라는 별도의 벡터를 이용하여 구현하면 어렵지 않음
# # 0:북 1:동 2:남 3:서
# # 0:육지 1:바다
n, m = map(int, input().split())
x, y, direction = map(int, input().split())
# 이동 벡터
dx = [0, 1, 0, -1]
dy = [-1, 0, 1, 0]
d = [[0] * m for _ in range(n)]
d[x][y] = 1 # 첫 위치는 방문한걸로 기록
map_list = []
for i in range(n):
map_list.append(list(map(int, input().split())))
def turn_left():
global direction
direction -= 1
if direction < 0:
direction = 3
turn_time = 0
count = 1
while True:
turn_left()
nx = x + dx[direction]
ny = y + dy[direction]
# 방문한적이 있거나 바다인 경우
if d[nx][ny] == 1 or map_list[nx][ny] == 1:
turn_time += 1
else:
d[nx][ny] = 1
x = nx
y = ny
count += 1
turn_time = 0
continue
# 4번의 회전을 모두 한 경우
if turn_time == 4:
nx = x - dx[direction]
ny = y - dy[direction]
# 뒤가 바다라면 시뮬레이션 종료
if map_list[nx][ny] == 1:
break
else:
x = nx
y = ny
turn_time = 0
print(count)
[DFS/BFS]
- 음료수 얼려 먹기
주어진 노드들을 따로 관리할 필요가 없으므로 visited를 별도로 관리하지 않아도 되고 DFS로 구현하면 된다
# N x M 얼음틀
# 구멍이 뚫린 부분은 0, 칸막이가 존재하는 부분은 1
# 구멍이 뚫린 부분끼리 상, 하, 좌, 우가 붙어있는 경우 서로 붙은것으로 간주
n, m = map(int, input().split())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
def dfs(x, y):
# 범위를 벗어나는 경우 즉시 종료
if x <= -1 or x >= n or y <= -1 or y >= m:
return False
# 아직 방문하지 않은 곳일 때
if graph[x][y] == 0:
# 방문처리 후 상하좌우 모두 탐색
graph[x][y] = 1
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
return True
return False
count = 0
# 모든 노드에 대하여 조사
for i in range(n):
for j in range(m):
if dfs(i, j) == True:
count += 1
print(count)
- 미로 탈출
노드간의 간선 값이 모두 1이므로 목표지점까지의 최단거리를 보장할 수 있다. BFS로 구현
# 미로의 크기는 NxM이고 출구는 좌표는 (N, M)
from collections import deque
n, m = map(int, input().split())
# 상, 하, 좌, 우
dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
maze = []
for i in range(n):
maze.append(list(map(int, input())))
def bfs(x, y):
queue = deque()
# 최초 시작노드 큐에 삽입
queue.append((x, y))
while queue:
x, y = queue.popleft()
# 각 노드에 연결된 최대 4방향에 대해 확인
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx <= -1 or nx >= n or ny <= -1 or ny >= m:
continue
if maze[nx][ny] == 0:
continue
if maze[nx][ny] == 1:
maze[nx][ny] = maze[x][y] + 1
queue.append((nx, ny))
return maze[n-1][m-1]
print(bfs(0, 0))
# 두 배열을 각각 오름차순, 내림차순 정렬 후 k만큼 앞에서 부터 바꿔주면 됨
n, k = map(int, input().split())
aArr = list(map(int, input().split()))
bArr = list(map(int, input().split()))
aArr.sort() # 오름차순
bArr.sort(reverse=True) # 내림차순
for i in range(k):
if aArr[i] < bArr[i]: # a보다 b가 큰 경우 서로 값을 바꿔줌
aArr[i], bArr[i] = bArr[i], aArr[i]
# 더이상 a보다 큰 수는 없으면 루프 탈출
else:
break
print(sum(aArr))
n, m = map(int, input().split())
hlist = list(map(int, input().split()))
start = 0
end = max(hlist)
result = 0
while start <= end:
total = 0
mid = (start + end) // 2
for x in hlist:
# 잘랐을 때 떡의 양 계산
if x > mid:
total += x - mid
# 떡의 양이 작으면 자르는 높이를 줄인다
if total < m:
end = mid - 1
# 떡의 양이 많으면 자르는 높이를 늘린다
# 최대한 덜 자르는게 목표이므로 이때 결과값을 보관해둔다
else:
start = mid + 1
result = mid
print(result)
이 문제의 경우 이진 탐색을 이용한다고 해서 데이터의 정렬이 반드시 필요한 것은 아니다
찾아야 하는 해가 계속 바뀌기 때문에 탐색 과정에 이진 탐색의 개념만 도입하여 파라메트릭 서치로 바꾼것이다
- 정렬된 배열에서 특정 수의 개수 구하기
bisect(C++에서는 lower_bound, upper_bound) 사용시 매우 쉽게 구할 수 있다
def bisect_left(array, x):
start = 0
end = len(array) - 1
result = 0
while start <= end:
mid = (start + end) // 2
# 값을 찾았다면 루프 종료가 아니라 mid 값을 보관하고 중복된 값을 찾으러 범위를 좁혀준다
# 왼쪽을 찾아야 하므로 끝점을 땡겨준다
if array[mid] == x:
result = mid
end = mid - 1
elif array[mid] > x:
end = mid - 1
else:
start = mid + 1
# 값 삽입시 현재 인덱스의 위치에 삽입하고 밀어내면 된다
return result
def bisect_right(array, x):
start = 0
end = len(array) - 1
# 마지막에 1을 더해주기 때문에 0을 만들어주기 위해 -1 대입
result = -1
while start <= end:
mid = (start + end) // 2
# 값을 찾았다면 루프 종료가 아니라 mid 값을 보관하고 중복된 값을 찾으러 범위를 좁혀준다
# 오른쪽을 찾아야 하므로 시작점을 끌어올려준다
if array[mid] == x:
result = mid
start = mid + 1
elif array[mid] > x:
end = mid - 1
else:
start = mid + 1
# 값 삽입시 현재 인덱스보다 오른쪽에 삽입해야 하기때문에 1을 더해준다
return result + 1
n, x = map(int, input().split())
array = list(map(int, input().split()))
result = bisect_right(array, x) - bisect_left(array, x)
if result == 0:
print(-1)
else:
print(result)
아래처럼 bisect 라이브러리를 이용해서 쉽고 간단하게 구현할 수 있지만 연습을 위해 직접 구현
실제 bisect는 값을 찾지 못하면 정렬이 깨지지 않는 적절한 인덱스를 반환한다
그것에 맞춰서 수정한건 아래와 같다
def bisect_left(array, x):
start = 0
end = len(array) - 1
# 찾는 값이 리스트 안의 모든 값보다 클때 result값이 변하는 일이 없으므로 미리 삽입될 끝 인덱스 지정
result = len(array)
while start <= end:
mid = (start + end) // 2
# 값을 찾았다면 루프 종료가 아니라 mid 값을 보관하고 중복된 값을 찾으러 범위를 좁혀준다
# 왼쪽을 찾아야 하므로 끝점을 땡겨준다
# 값을 찾지 못한경우 적절한 위치를 찾기 위해 부등호 >= 를 사용해준다
if array[mid] >= x:
result = mid
end = mid - 1
elif array[mid] > x:
end = mid - 1
else:
start = mid + 1
# 값 삽입시 현재 인덱스의 위치에 삽입하고 밀어내면 된다
return result
def bisect_right(array, x):
start = 0
end = len(array) - 1
# 마지막에 1을 더해주기 때문에 0을 만들어주기 위해 -1 대입
result = -1
while start <= end:
mid = (start + end) // 2
# 값을 찾았다면 루프 종료가 아니라 mid 값을 보관하고 중복된 값을 찾으러 범위를 좁혀준다
# 오른쪽을 찾아야 하므로 시작점을 끌어올려준다
# 값을 찾지 못한경우 적절한 위치를 찾기 위해 부등호 <= 를 사용해준다
if array[mid] <= x:
result = mid
start = mid + 1
elif array[mid] > x:
end = mid - 1
else:
start = mid + 1
# 값 삽입시 현재 인덱스보다 오른쪽에 삽입해야 하기때문에 1을 더해준다
return result + 1
값을 찾지 못한경우 두 함수의 반환값은 모두 같다. 실제 bisect_left, bisect_right와 동일한 반환값을 가진다
따로 구현하지 않고 사용시에는 최상단에 from bisect import bisect_left, bisect_right 를 선언해주고 동일하게 쓰면 된다
x = int(input())
dp = [0] * 30001
# Bottom-up
# dp[1]은 0이라서 2부터 수행이 가능하다
for i in range(2, x + 1):
# 현재 수에서 1을 빼는경우. 연산횟수 1회가 증가된다
dp[i] = dp[i - 1] + 1
if i % 2 == 0:
# 현재 수가 2로 나누어 떨어지는 경우, 1을 뺀 현재 연산횟수보다
# 2로 나누었을때의 연산횟수가 더 적은지 확인한다.
# 2로 나누는 과정 자체도 한번의 연산횟수이기 때문에 1을 더해준 값을 비교한다.
# 좌항은 연산횟수 1을 안더하는 이유는 이미 위에서 더해줬기 때문이다.
dp[i] = min(dp[i], dp[i // 2] + 1)
# 3으로 나누어 떨어지는 경우
if i % 3 == 0:
dp[i] = min(dp[i], dp[i // 3] + 1)
# 5로 나누어 떨어지는 경우
if i % 5 == 0:
dp[i] = min(dp[i], dp[i // 5] + 1)
# dp에 저장된 값만 꺼내오면 된다
print(dp[x])
그리디처럼 큰 수인 5로 먼저 나누는것이 항상 능사가 아닌것을 알아야한다.
예를들어 27인경우 5로 먼저 나누려고 하면 26-25-5-1 총 4번의 연산이 이루어지지만 3으로 나눈다면 9-3-1 총 3번의 연산만으로 1을 만들수 있다. 그렇기에 그리디로는 풀 수 없다.
n, m = map(int, input().split())
dp = [10001] * (m + 1)
money = []
for i in range(n):
money.append(int(input()))
dp[0] = 0
for i in money:
for j in range(i, m + 1):
# (i-k)원을 만드는 방법이 존재하는 경우
if dp[j - i] != 10001:
# 1을 더해주는 이유는 화폐 장수 한장이 추가되기 때문
dp[j] = min(dp[j], dp[j - i] + 1)
if dp[m] == 10001:
print(-1)
else:
print(dp[m])
문제를 잘못 이해해서 30분정도 삽질을 했었다. 심플하게 잘 풀었다고 생각했는데 조건 자체가 잘못됐었음
from sys import stdin
input = stdin.readline
# 무한 값
INF = int(1e9)
n, m = map(int, input().split())
# 최단 거리 테이블 값을 무한으로 초기화
table = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 자신에서 자기 자신으로 가는 거리는 0
for i in range(1, n+1):
table[i][i] = 0
for i in range(m):
x1, x2 = map(int, input().split())
# 양방향이면서 거리가 모두 1
table[x1][x2] = 1
table[x2][x1] = 1
# 목적지 x와 경유지k
x, k = map(int, input().split())
# 정점 개수만큼 순회 O(N)
for i in range(1, n + 1):
# 2차원 최단 거리 테이블 갱신 O(N²)
for x1 in range(1, n + 1):
for x2 in range(1, n + 1):
table[x1][x2] = min(table[x1][x2], table[x1][i] + table[i][x2])
# 1부터 경유지까지의 거리 + 경유지부터 목적지까지의 거리
distance = table[1][k] + table[k][x]
# INF가 넘는다면 경로가 없음
if distance >= INF:
print(-1)
else:
print (distance)
from sys import stdin
import heapq
input = stdin.readline
# 무한 값
INF = int(1e9)
n, m, c = map(int, input().split())
graph = [[] for _ in range(n + 1)]
distance = [INF] * (n + 1)
for _ in range(m):
x, y, z = map(int, input().split())
graph[x].append((y, z))
def dijkstra(start):
q = []
heapq.heappush(q, (0, start))
distance[start] = 0
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]:
continue
for x in graph[now]:
cost = dist + x[1]
if cost < distance[x[0]]:
distance[x[0]] = cost
heapq.heappush(q, (cost, x[0]))
dijkstra(c)
count = 0
max_distance = 0
# 도달할 수 있는 노드중 가장 멀리있는 노드와의 최단거리
for x in distance:
if x != INF:
count += 1
max_distance = max(max_distance, x)
# 시작 노드는 제외해야 하므로 -1
print(count - 1, max_distance)
from sys import stdin
input = stdin.readline
# 부모 리스트, 찾을값
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
n, m = map(int, input().split())
parent = [x for x in range(n + 1)] # 부모 리스트 초기화
for i in range(m):
x, a, b = map(int, input().split())
# union
if x == 0:
union_parent(parent, a, b)
# find
else:
if find_parent(parent, a) == find_parent(parent, b): # 서로의 루트가 같다면
print("YES")
else:
print("NO")
from sys import stdin
input = stdin.readline
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
def union_parent(parent, a, b):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
# 노드n 간선m. a,b,c : a-b의 연결비용 c
n, m = map(int, input().split())
parent = [x for x in range(n + 1)]
edges = [] # 간선 저장 리스트
for i in range(m):
a, b, c = map(int, input().split())
edges.append((c, a, b))
edges.sort()
answer = 0
max_cost = 0
for edge in edges:
cost, a, b = edge
# 사이클이 아닌 경우만 수행
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
answer += cost
max_cost = cost # 비용순으로 정렬되어서 가장 마지막에 들어온 값이 클수밖에 없음
# 가장 높은 비용을 빼서 트리를 2개로 분리
print(answer - max_cost)
