본문 바로가기

분류 전체보기51

[백준] 1406. 에디터 - Python [Silver II] https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 원래는 Linked List를 사용하여 문제를 해결하는 방법이 정석 풀이지만, Python에서 Linked List를 구현하는 것이 클래스를 선언하고...등과 같은 절차로 귀찮은 관계로, 스택(덱 사용) 2개를 사용하여 문제를 해결하였다. 왼쪽 스택과 오른쪽 스택이 있다고 가정하고, 왼쪽 스택의 top이 현재 커서의 위치가 된다. Apple이라는 글자가 있는데 커서가 l뒤.. 2023. 9. 26.
[백준] 2667. 단지번호붙이기 - Python [Silver I] https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 2차원 배열을 통해 그래프를 생성하고, 1이 있는 곳 마다 BFS를 돌려 1번 컴퓨터와 연결된 컴퓨터의 개수를 센다. (단지별로 BFS를 돌며, 이미 방문한 곳은 visited 셋을 통해 체크하여 이미 방문한 단지를 중복방문하지 않게 한다.) from collections import deque import sys # global var n = 0 g = [] dx = [-.. 2023. 9. 18.
[백준] 2606. 바이러스 - Python [Silver III] https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 풀이 2차원 배열을 통해 네트워크(그래프)를 생성하고, BFS를 돌려 1번 컴퓨터와 연결된 컴퓨터의 개수를 센다. from collections import deque computers = [] visited = [] ans = 0 def solve(cur): global ans global visited global computers q = deque() q.append(cur.. 2023. 9. 18.
[백준] 1260. DFS와 BFS - Python [Silver II] https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 풀이 2차원 배열을 통해 네트워크(그래프)를 생성하고, BFS와 DFS를 각각 돌려 결과를 출력한다. 정점 번호가 작은 것 먼저 방문해야 하므로, 그래프를 돌면서 각 정점들을 정렬한 후 DFS와 BFS를 실행한다. DFS이후 visited 리스트를 초기화해야 BFS도 동일하게 실행할 수 있기 때문에 DFS 이후 initVar()를 통해 리.. 2023. 9. 18.
[백준] 14502. 연구소 - Python [Gold IV] https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이 백트래킹을 통해 미로에서 벽을 놓을 위치 세 곳을 선택한다. -> 나중에는 순열로 해결해도 가능 (1)을 통해 3개의 벽을 세웠으면, 해당 연구실 지도를 deepcopy(깊은 복사를 해야 원본이 변경되지 않음)를 통해 테스트 지도를 복사하고, 상, 하, 좌, 우를 번갈아가며 BFS로 지도를 탐색한다. (처음에는 방문했던 노드를 재방문 하는 것을 피하려고 visited 배열을 사용했지만,.. 2023. 9. 17.
[백준] 10808. 알파벳 개수 - Python [Bronze IV] https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 풀이 반복문을 통해 'a' ~ 'z'까지 반복하며 input으로 들어온 값에 단어가 몇개나 있는지 비교 (최대한 파이썬의 다양한 기능을 활용해서 효율적으로 코드를 짜보려고 노력했습니다.) ord()를 통해 'a' ~ 'z'를 for문을 통해 반복시킬 수 있었고, count()를 통해 input에 해당 alphabet들이 몇 개가 들어있는지 출력. inputString = input() for alphabet in range(ord('a'), ord('z') + 1): p.. 2023. 9. 4.

티스토리툴바