[백준 #13335 파이썬] 트럭
2022. 12. 21. 11:15
Algorithm
n,w,l = map(int,input().split()) truck = list(map(int,input().split())) bridge = [0]*w cnt = 0 while bridge: cnt += 1 bridge.pop(0) if truck: if sum(bridge) + truck[0] > l: bridge.append(0) else: bridge.append(truck.pop(0)) print(cnt) 예전에 프로그래머스에서 풀어본 경험이 있어서 복습 겸 다시 풀어보게 되었다. 생각한 방법 1. 비어있는가? => 무조건 추가 2. 비어있지 않은가? 2-1 다리위에 새로운 걸 추가해도 되는가? yes : 추가한다. no : 패스 이 생각을 가지고 구현을 시작했다. 여기서 더 고려되어야 하는 ..
[백준 #16234 파이썬] 인구 이동
2022. 12. 19. 11:39
Algorithm
생각한 방법 전형적인 그래프 탐색이나 bfs 문제라고 생각했다. 바이러스 처럼 퍼지는 유형의 경우 dfs로 활용해서 푸는 것은 뎁스가 너무 깊어지기 때문에 이부분은 미리 배제하고 시작했다. 전형적인 bfs 풀이 방식으로 계획해야겠다고 생각한 이후 더 생각해야 하는 부분을 고려했다. 1. 전체 탐색 그래프에 있는 모든 값과 그를 중심으로 한 주변 값의 차이를 조사해야 한다. 어디에서 인구 이동이 일어날 지는 예측할 수 없으므로 모든 값에 대한 bfs 탐색이 필요하다. 2. 전체 탐색의 반복 인구 이동은 2일 이상 소요될 수 있다. 인구 이동이 일어난 이후 인구 이동이 일어난 지역과 일어나지 않았던 지역끼리 다시 비교해보면 새로운 인구 이동의 가능성이 있을 수 있다. 그러므로 bfs는 반복되어야 한다. 3...

[백준 #2178 파이썬] 미로 탐색
2022. 10. 8. 00:50
Algorithm
2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net DFS로는 시간초과가 나는 이유 : 전체 탐색 문제를 보면 처음에는 이건 무조건 그래프 탐색이다 라는 감이 됩니다. 다만, dfs로 풀지, bfs로 풀 지 고민을 하게 됩니다. 체감상 bfs로 푸는 게 조금 더 쉬운 느낌이 드는데, 사실 명확한 이유가 있습니다. dfs 방식으로 푼다면, 모든 노드를 탐색해야 하는 결과가 나타날 수 있습니다. 그러한 방식으로 탐색을 하면 결과를 확인할 수 는 있지만, 최단거리임을 확인하기 위해서 더 많은 연산이 필요합니다. 따라서 이 경우에는 bfs를 통해 가장..

[백준 #2667 파이썬] 단지 번호 붙이기
2022. 10. 8. 00:49
Algorithm
2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net from collections import deque n = int(input()) apt = [list(map(int,input())) for _ in range(n)] def bfs(x,y): queue = deque() queue.append((x,y)) apt[x][y] = 0 cnt = 1 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] while queue: x,y = queue.popleft() for i in range(4): n..

[백준 #1260 파이썬] DFS BFS
2022. 7. 25. 13:33
Algorithm
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 혼자서 아무것도 모르고 풀어보려다 많이 거꾸러졌던 문제 지금도 DFS BFS를 다시 기억하기 위해서 계속해서 다시 풀어보고 있는 문제다 풀어볼 때마다 여전히 새롭고 괴롭다 ㅎㅎ 그래도 재귀가 조금씩 더욱 익숙해지고 있는 느-낌! 그렇다면 한번 풀어보자 우선은 기본적으로 생각해야 할 것들을 생각해보자 정점의 개수 N, 간선의 개수 M, 탐색을 시작할 정점의 번호 V가 주어진다. 이 문제를 처음 볼 때는 정점이 1로 시작해야 풀..
[백준 #1747 파이썬] 재귀, 완전탐색
2022. 7. 20. 12:25
Algorithm
소수를 판정하는 것과 팰린드롬을 판정해주는 함수를 각각 만든다. 그리고 시간복잡도를 따져 둘 중에 무엇을 먼저 해주어야 시간 복잡도가 낮을 지 고민을 해야한다. 처음에는 소수를 판정하는 것이 더 적을 것이라고 생각했지만, 팰린드롬이 탐색에 있어서 더 효율적이었다.. 그리고 꼭 고민해주어야 할것은 n의 범위였다. n이 1인 경우도 고려하고 있으므로 이것에 대한 별도의 처리가 필요하다. 다만, 인터넷 사이트의 결과들을 보면 다른 사람들은 100만 이상의 소수를 따로 처리를 해주었는데 나는 그럴 필요는 없었다! 리턴값을 너무 마음대로 num으로 하긴 했는데 전혀 그럴 필요는 없어보인다 ㅎㅎ def is_palindrome(num): if str(num) != str(num)[::-1]: return False..
[백준 #10974 파이썬] 모든 순열
2022. 7. 17. 23:30
Algorithm
완전 탐색 알고리즘 의미 그대로 전체를 탐색할 수 있도록 고안하는 알고리즘입니다. 문제를 해결함에 있어 어떻게 탐색을 해야할 지 다양하게 고민해보는 것이 중요합니다. 단순히 순차열적으로 해결할 수도 있고, 탐색에 어떤 조건이나 기준을 세워 전체를 바라보는 방법도 있습니다. 여러 방법으로 해결할 수는 있겠지만, 메모리 사용을 줄이고 탐색의 시간을 감소시키기 위해 더 효율적인 방법에 대해 고민하는 방법이 알고리즘 해결에 있어 가장 중요한 부분입니다. 10974 모든 순열 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net N!줄..