본문 바로가기

분류 전체보기

 (120)
[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 문제 중에 내 기준 가장 까다로운 문제였다.. 처음에 쉬운 문제라고 생각했는데 하다보니 자꾸 꼬이고 잘 안 되어서 다른 분의 블로그를 참고했다. 코드를 ..
[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..
[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라는 딕셔너리를 활용해 현재 내 번호에 해당하는 남, 동, ..
[BOJ] 2933. 미네랄(Python) / Simulation + BFS 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 동굴에 있는 미네랄의 모양과 두 사람이 던진 막대의 높이가 주어진다. 모든 막대를 던지고 난 이후에 미네랄 모양을 구하는 프로그램을 작성하는 문제 # 2시간 48분 소요 사용 알고리즘 : Simulation + BFS 구현이 상당히 까다로운 문제였다. 엣지 케이스가 많다.. 질문 게시판에 나온 모든 반례를 넣으며 코드를 고쳤고, 결국 pass! pass 후 거의 1-2시간을 더 투자해 최적화했고 시간 1위를 달성했다!(248ms, PyPy3 제출) 고려할 것이 많으므로 기능화..
[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]을 추가해줬다. 재귀로 현 숫자가 가리..
[BOJ] 17135. 캐슬 디펜스(Python) / DFS + BFS 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net # 1h 58m 소요 사용 알고리즘 : DFS + BFS / 자료구조 : 큐, 최소 힙(우선순위 큐) 오랜만에 이렇게 온갖 알고리즘이 섞인 문제를 풀었다. 장장 2시간여의 긴 여정이었다. 두 번째 푸는 문제라 나름 자신했지만, 처음에 코드 설계하고 다 풀고 디버깅하느라 시간이 좀 걸려서 아쉬웠다.. 한 번에 고려했어야 하는데! 일단 아래 코드는 죽일 적을 최소 힙 큐에 담으면서 가장 높은 우선순위의 적을 뽑아 사용하도록 했다. 시간, 메모리 면에서 매우 오래걸리는 코드라 또..
[BOJ] 12904. A와 B(Python) / Greedy 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램 작성하는 문제 사용 알고리즘 : Greedy(탐욕 알고리즘) 처음에 백트래킹 완전탐색으로 구현했는데 제출하자마자 시간초과 났다. 알고리즘 구분을 보니 Greedy 알고리즘이더라. 다른 사람의 풀이를 보고 무릎을 탁! 쳤다. 생각을 바꿔서 T에서 S로 만드는 것이다. 조건을 반대로 생각해 T의 마지막 문자가 "A"이면 pop, "B"이면 pop 하고 문자..
[BOJ] 6593. 상범 빌딩(Python) / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함 # 1시간 15분 소요 사용 알고리즘 : BFS 최단 거리 구하기 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다. Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순..

티스토리툴바