Algorithm/Baekjoon

Algorithm/Baekjoon
[백준] 주몽 / 1940번 / 파이썬 / Python
💡solutions ) 💬 처음에 문제 풀 때 별 생각없이 풀어서,, 주어진 재료들 중 두 재료씩 묶을 수 있는 모든 경우의 수를 itertools의 combinations을 통해 구했다가 시간초과가 났다. 주어진 재료 개수의 범위가 N(1 ≤ N ≤ 15,000)인 것을 감안하면 시간 초과가 나는 게 당연하다. 참고로 파이썬의 초당 2,000만번의 연산이 가능하다고 한다. 💬 두 번째 시도 -> 해당 문제는 투포인터 문제 유형이다. 먼저 정렬을 한 후 두 가지 인덱스 값(left는 맨 처음, right는 맨 끝 재료를 나타내기 위함)을 정의한다. 💬 left, right가 가리키는 두 재료의 합이 m과 같으면 answer += 1, m보다 작으면 left += 1, m보다 크면 right -= 1을 해..
→2021.10.31
Algorithm/Baekjoon
[백준] 20055번 / 컨베이어 벨트 위의 로봇 / 파이썬 / Python
💡solutions ) 💬 시뮬레이션 유형으로 문제에서 주어진 조건들을 차례대로 구현하면 되는 문제 💬 deque 자료형과 rotate() 메소드 사용하여 컨베이어가 한칸씩 이동하는 것을 나타냄 👨‍💻code ) import sys from collections import deque input = sys.stdin.readline n, k = map(int, input().split()) conveyor_belt = deque(list(map(int, input().split()))) robot = deque([0]*n) answer = 0 while True: robot.rotate(1) conveyor_belt.rotate(1) robot[-1] = 0 for i in range(n-2, -1, -..
→2021.10.23
Algorithm/Baekjoon
[백준] 1244번 / 스위치 켜고 끄기 / 파이썬 / python
💡solutions ) 💬 문제 설명에서 주어진 정보를 코드로 구현하면 되는 시뮬레이션 문제 💬 남학생인 경우, 여학생인 경우 나눠서 처리하기 위해 if_boy, if_girl 함수 구현함 💬 마지막 출력에서 스위치 상태 출력이 20개가 넘는 경우 20개씩 끊어서 출력해야 하는 것을 주의해야 함 👨‍💻code ) import sys def if_boy(num, switch_state): for i in range(1, len(switch_state)+1): if i % num == 0: if switch_state[i-1]: switch_state[i-1] = 0 else: switch_state[i-1] = 1 def if_girl(num, switch_state): front = num-2 back ..
→2021.10.14
Algorithm/Baekjoon
[백준] 10815번 / 숫자 카드 / 파이썬 / python
💡solutions ) 💬 딕셔너리 자료형 사용하여 문제를 해결함 💬 상근이가 가지고 있는 카드 리스트를 가지고 딕셔너리 형태로 만든다. key를 카드 번호, value에 몇장인지 값을 저장 💬 주어진 m개의 카드 리스트로 for 반복문을 돌며 위에서 만든 딕셔너리 key값으로 존재하는지 확인 후 존재하면 해당 value값을 answer 리스트에 저장하여 마지막에 출력한다. 👨‍💻code ) import sys input = sys.stdin.readline n = int(input()) n_list = sorted(list(map(int, input().split()))) m = int(input()) m_list = list(map(int, input().split())) n_dict = {} for..
→2021.10.13
Algorithm/Baekjoon
[백준] 2979번 / 트럭 주차 / 파이썬 / Python
👨‍💻code ) from abc import ABCMeta import sys input = sys.stdin.readline a, b, c = map(int, input().rstrip().split(' ')) time_table = [0]*101 for i in range(3): arrive, depart = map(int, input().rstrip().split(' ')) for j in range(arrive-1,depart-1): time_table[j] += 1 answer = 0 for k in time_table: if k == 1: answer += a*k elif k == 2: answer += b*k elif k == 3: answer += c*k print(answer) 📌des..
→2021.10.07
Algorithm/Baekjoon
[백준] 1173번 / 운동 / 파이썬 / Python
👨‍💻code ) import sys input = sys.stdin.readline N, m, M, T, R = map(int, input().split()) pulse = m time = 0 exercise = 0 while exercise M: time = -1 break time += 1 if pulse + T
→2021.10.06
Algorithm/Baekjoon
[백준] 알고스팟 / 1261번 / 파이썬 / Python / Dijkstra 알고리즘
💡solutions ) 💬 단순 다익스트라(Dijkstra) 알고리즘으로 해결한 문제, 해당 문제에서 노드의 비용에 해당하는 것은 벽을 부순 횟수(cnt) 💬 BFS로도 방문 중복으로 하여 해결할 수 있는 문제 🎫code ) import sys import heapq def dijkstra(): heap = [] heapq.heappush(heap, [0, 0, 0]) # 시작점 visit[0][0] = 1 while heap: cnt, x, y = heapq.heappop(heap) # 벽 부순 횟수가 최소인 경우가 나옴 for k in range(4): nx, ny = x + dx[k], y + dy[k] if x == n - 1 and y == m - 1: # 종료조건 print(cnt) break..
→2020.12.06
Algorithm/Baekjoon
[백준] 최소비용 구하기 / 1916번 / 파이썬 / python
💡solutions ) 💬 dijkstra(다익스트라) 알고리즘 유형의 기본 문제 🎫code ) import sys import heapq def dijkstra(n, s, e): dist = [INF] * (n + 1) dist[s] = 0 heap = [] heapq.heappush(heap, [0, s]) while heap: cost, node = heapq.heappop(heap) for n, c in adj[node]: c += cost if c < dist[n]: dist[n] = c heapq.heappush(heap, [c, n]) return dist[e] input = sys.stdin.readline n = int(input()) m = int(input()) adj = [[] fo..
→2020.12.05
Algorithm/Baekjoon
[백준] 숨바꼭질 / 1697번 / 파이썬 / python
🎫code ) from collections import deque # 너비 우선 탐색 n, k = map(int, input().split(' ')) arr = [0] * (k + 1) max_v = 100001 visit = [0] * max_v q = deque([n]) da = [-1, 1, 2] while q: a = q.popleft() if a == k: print(visit[a]) break for i in range(3): if i == 2: na = a * da[i] else: na = a + da[i] # a가 기존, na는 다시 돌아왔을 때 비교 if (0
→2020.12.04
Algorithm/Baekjoon
[백준] 1로 만들기 / 1463번 / 파이썬 / Python
🎫code ) n = int(input()) dp = [0 for _ in range(n + 1)] for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 print(dp, '0') if i % 2 == 0 and dp[i] > dp[i // 2] + 1: dp[i] = dp[i // 2] + 1 print(dp, '1') if i % 3 == 0 and dp[i] > dp[i // 3] + 1: dp[i] = dp[i // 3] + 1 print(dp, '2') print(dp[n]) 📌 description ) 문제출처 : www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진..
→2020.12.03
Algorithm/Baekjoon
[백준] 효율적인 해킹 / 1325번 / 파이썬 / Python
🎫code ) import sys from collections import deque input = sys.stdin.readline def bfs(lst): q = deque(lst) while q: x = q.popleft() visit[x] = 1 for i in adj[x]: if not visit[i]: q.append(i) visit[i] = 1 return visit.count(1) n, m = map(int, input().split(' ')) adj = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split(' ')) adj[b].append(a) res = [] max_v = 0 for i in range..
→2020.12.01
Algorithm/Baekjoon
[백준] 차이를 최대로 / 10819번 / 파이썬 / Python
💡solutions ) 💬 n값이 크지 않으니까, permutations 써서 모든 경우를 찾는 브루트포스 알고리즘 구현 🎫code ) import sys from itertools import permutations as permu input = sys.stdin.readline n = int(input()) arr = list(map(int, input().rstrip().split(' '))) max_v = 0 for p in permu(arr, n): sum = 0 n_list = list(p) for i in range(1, len(n_list)): tmp = abs(n_list[i - 1] - n_list[i]) sum += tmp max_v = max(max_v, sum) print(max_..
→2020.11.30

• 이전
• 1
• 2
• 3
• 4
• 5
• 다음