Algorithm77 [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. [BOJ] 2933. 미네랄(Python) / Simulation + BFS 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하는 문제 # 2시간 48분 소요 사용 알고리즘 : Simulation + BFS 구현이 상당히 까다로운 문제였다. 엣지 케이스가 많다.. 질문 게시판에 나온 모든 반례를 넣으며 코드를 고쳤고, 결국 pass! pass 후 거의 1-2시간을 더 투자해 최적화했고 시간 1위를 달성했다!(248ms, PyPy3 제출) 고려할 것이 많으므로 기능화.. 2021. 4. 9. [BOJ] 10451. 순열 사이클(Python) / DFS 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하는 문제 # 23분 소요 사용 알고리즘 : DFS 실버 1 문제로 구현이 오래 걸리지 않았다. 방문 표시 배열 check과 총 사이클 갯수를 셀 cycle 변수를 만들었다. 가리키는 숫자 인덱스와 배열 인덱스를 일치시키기 위해 주어진 숫자 리스트를 받으며 앞에 [0]을 추가해줬다. 재귀로 현 숫자가 가리.. 2021. 4. 8. 이전 1 2 3 4 5 6 ··· 13 다음
