파이썬62 [BOJ] 1938. 통나무 옮기기(Python) / BFS 1938번: 통나무 옮기기 첫째 줄에 주어진 평지의 한 변의 길이 N이 주어진다. (4 2021. 4. 11. [BOJ] 1525. 퍼즐(Python) / BFS 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 신박한 느낌의 BFS 문제였다. 처음 문제 봤을 때 감조차 잡히지 않았다. 이게 어떻게 BFS 인지 이해가 되지 않아, 코드 말고 아이디어 만이라도 얻어야겠다 싶어 구글링 해보니.. 3*3 맵에 있는 숫자들을 문자열로 변환해서 0이 있는 곳 기준으로 숫자 바꿀 수 있는 위치로 바꿔주고 BFS로 뻗어나가며 타겟 문자열을 찾는 방식으로 접근해야 한다는 것을 깨달았다. 이 아이디어를 바탕으로 코드를 짜봤다. # 아이디어 참고까지 30분, 문제 pass까지 1시간 30분/ 총 2시간 소요 사용 알고리즘 : BFS 최단 시간 알고리즘 3*3 맵의 .. 2021. 4. 11. [BOJ] 14425. 문자열 집합(Python) / Trie 자료구조 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사해야 하는 문자열들이 주어 www.acmicpc.net 총 N개의 문자열로 이루어진 집합 S가 주어진다. 입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오. 매주 알고리즘 코딩 & 컴공 전공 스터디를 진행하는데, BFS, DFS, 백트래킹, Brute Force, Greedy 등은 자주 푸니까 매주 한 개씩 새로운 알고리즘을 공부해보자 하여 지난 주 이분탐색에 이어 이번 주는 트라이 자료구조에 대해 한번 공부해보기로 했다. .. 2021. 4. 10. [BOJ] 11967. 불 켜기(Python) / BFS 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 각 방에서 불을 켤 수 있는 곳의 위치가 주어지면 불이 켜져있는 방으로만 들어갈 수 있고, 각 방에서는 상하좌우에 인접한 방으로 움직일 수 있다. 불을 켤 수 있는 방의 최대 개수를 구하는 문제이다. 사용 알고리즘 : BFS 너비 우선 탐색 근래 풀어본 BFS 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 .. 2021. 4. 9. [BOJ] 10815. 숫자 카드(Python) / Binary Search 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. # 38분 소요 사용 알고리즘 : Binary Search(이분 탐색) 풀 수 있는 방법이 많겠지만, 이분 탐색에 취약한 나는 코드 연습 겸 이분 탐색으로 코드를 짰다. numLst, chkLst 각 리스트를 Input 받고 c.. 2021. 4. 9. [BOJ] 2234. 성곽(Python) / BFS 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net # 1시간 40분 소요 사용 알고리즘 : BFS 너비 우선 탐색 문제 푸는 흐름은 아래 코드에 주석으로 잘 적어놨고, makeBinInfo() 함수 binInfo 딕셔너리에 0~16 숫자를 4자리 이진수로 변환한 정보를 담아줬다.(0: 나갈 수 있음, 1: 벽. 나갈 수 없음) checkRooms() 함수 visited 배열에 방의 번호를 적으며 bfs를 퍼트렸다. 이 때, 방 번호를 binInfo라는 딕셔너리를 활용해 현재 내 번호에 해당하는 남, 동, .. 2021. 4. 9. 이전 1 2 3 4 5 6 ··· 11 다음
