python8 [백준]BOJ 1726 - 로봇 - Python/BFS https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 로봇이 바라보는 방향에 따라서 갈 수 있는 노드가 달라진다 -> 3차원 그래프다 (세로 m, 가로 n, 높이가 4인) 이 발상만 빠르게 해낸다면 평범한 BFS 문제가 된다. 하나의 노드에서 최대 5개의 노드와 연결이 가능하다(회전 2방향, 전진 3방향) 하지만 2칸 이상 전진했을때, 앞선 칸이 1이면 넘어가지 못한다. (점프를 할 수 없다) 이것만 주의하고 BFS 탐색을 하면 쉽게 결과를 낼 수 있다. # .. 2022. 11. 18. [백준]BOJ 3055 - 탈출 - Python/BFS https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 입력으로 그래프가 주어지고, 어느 칸에서 BFS를 시작해야하는지 알려준다. 문제를 읽어보면 고슴도치와 물 둘 다 BFS 탐색을 해야 하는 것을 알 수 있다. 주의할 점은 예제에는 초기에 물인 칸이 1개밖에 없지만 문제를 읽어보면 1칸이라는 제약조건이 없다. 따라서 물이 여러칸일 때도 생각하고 프로그래밍을 해야 한다. 처음에 두가지 생각을 했다. A. BFS탐색을 각각 따로 하는 방법 1. 고슴도치를 먼저 BF.. 2022. 11. 17. [백준]BOJ 7576 - 토마토 - Python/BFS https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 처음엔 무난한 BFS 문제라고 생각했다. 처음부터 익어있는 토마토(루트 토마토라고 하겠다.)가 들어있는 칸을 알아낸 다음에 반복문으로 BFS를 적용하고, 루트 토마토를 할 때마다 만약 칸에 더 적은 숫자가 들어 갈 수 있다면 숫자를 업데이트 하는 식으로 문제를 풀었다. 그랬더니 시간초과가 나온다. 쓸데없는 연산이 너무 많아서 그렇다. 정확한 풀이는 BFS 큐를 처음 만들때부터 모든.. 2022. 11. 10. [백준]BOJ 1697 - 숨바꼭질 - Python/BFS https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 입력으로 수빈이와 동생의 위치, 그리고 수빈이가 이동할 수 있는 제약조건을 알려준다. 수빈이의 위치보다 동생의 위치가 더 앞에 있거나 같을때는 (n >= k) 뒤로 가는 방법이 한칸 이동하는 것 밖에 없으므로 n - k 로 쉽게 결과를 도출 할 수 있다. 그 외의 경우에는 각각의 좌표를 노드라고 생각했을 때, 이 그래프는 각 노드가 노드값이 1만큼 크거나 작은 노드와 2.. 2022. 11. 7. [백준]BOJ 2331 - 반복 수열 - Python/구현 https://www.acmicpc.net/problem/2331 2331번: 반복수열 첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다. www.acmicpc.net 1. 수열을 만드는 반복문을 만든다. 2. 도중에 기존에 있는 원소와 같은 원소가 나오면 반복문을 종료한다. 3. 처음으로 나온 같은 원소의 인덱스를 출력한다. (인덱스는 0부터 시작이기에 더하고 뺄 필요가 없다.) 너무 간단하게 풀렸는데 시간복잡도가 별로 좋아보이진 않는다. 더 좋은 방법이 있을듯 싶다. a, p = map(int, input().split()) seq = [a] while True: element = 0 for i in str(seq[-1]): element += (int(i) ** p).. 2022. 11. 7. [백준]BOJ 2667 - 단지 번호 붙이기 - Python https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 그래프가 입력으로 주어지고, 각 노드마다 탐색의 범위가 상하좌우로 제한된다. 앞서 해결했던 미로 탐색과 순열 사이클을 섞어놓은 듯 한 문제이다. 따라서 다음과 같은 과정으로 출력값을 얻었다. 1. 전체 그래프를 탐색하는 2중 반복문을 작성한다. 2. 방문하지 않은 노드가 나올 때마다 그래프 탐색(DFS, BFS)를 실시한다. 3. 각 그래프를 탐색했을때 노드의 개수를 저장하고 정렬한 다음에 출력한다.. 2022. 11. 7. [백준]BOJ 2178 - 미로 탐색 - Python/BFS https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 입력값으로 미로의 크기와 구성이 주어진다. 미로 안에서는 값이 1인 칸으로만 이동 할 수 있고, 또 각 칸에서는 상하좌우의 칸으로밖에 이동하지 못한다. -> 현재 칸에서 상하좌우의 칸을 탐색해서 1인 경우에만 Queue에 넣는다. 이 문제에서는 각 노드를 방문했는지의 여부보다 몇번째에 방문했는지의 여부가 더 중요하다. -> 이전 노드의 방문 순서에 1을 더한 값을 현재 노드의 방문 순서로 한다. (isVisited가 Bool이 .. 2022. 11. 6. [Python]여러개의 텍스트 파일을 열 단위로 엑셀 파일로 옮기기 https://github.com/kelly-chui/texcel-py GitHub - kelly-chui/texcel-py: Digital Amplifier의 hit rate 결과로 출력된 text 파일을 Excel로 옮겨주는 프로그Digital Amplifier의 hit rate 결과로 출력된 text 파일을 Excel로 옮겨주는 프로그램 - kelly-chui/texcel-pygithub.com 학부연구원을 하고 있는 친구에게 연락이 왔다. Digital Amplifier를 설계했고, 한번 시뮬레이션을 돌리면 약 40개 정도의 Text 파일이 생성되는데 이걸 엑셀에 하나하나 붙여넣기가 너무 귀찮다고 한다. Python도 복습할 겸 친구도 도와주기 위해 코드를 작성해보자.Python에서 Excel .. 2022. 11. 3. 이전 1 다음
