알고리즘70 [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. [BOJ] 17135. 캐슬 디펜스(Python) / DFS + BFS 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net # 1h 58m 소요 사용 알고리즘 : DFS + BFS / 자료구조 : 큐, 최소 힙(우선순위 큐) 오랜만에 이렇게 온갖 알고리즘이 섞인 문제를 풀었다. 장장 2시간여의 긴 여정이었다. 두 번째 푸는 문제라 나름 자신했지만, 처음에 코드 설계하고 다 풀고 디버깅하느라 시간이 좀 걸려서 아쉬웠다.. 한 번에 고려했어야 하는데! 일단 아래 코드는 죽일 적을 최소 힙 큐에 담으면서 가장 높은 우선순위의 적을 뽑아 사용하도록 했다. 시간, 메모리 면에서 매우 오래걸리는 코드라 또.. 2021. 4. 8. [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 하고 문자.. 2021. 4. 8. [BOJ] 6593. 상범 빌딩(Python) / BFS 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 빌딩의 상태를 3차원 배열로 받아 시작 위치부터 도착 위치까지 최단 거리로 갈 수 있는 경우의 거리를 구함 # 1시간 15분 소요 사용 알고리즘 : BFS 최단 거리 구하기 나의 비루한 코딩실력으로 인해 Input 받는 데만 28분이 걸렸다.. 별것도 아닌 것을.. 혼자 이상하게 생각ㅠ 이후로는 주어진 맵대로 3차원 배열인 것만 다르고 일반적인 BFS 문제와 같이 풀면 된다. Input 받으며 시작 좌표를 저장한다.(sl, sr, sc - 몇 층, 몇 행, 몇 열 순.. 2021. 4. 7. [BOJ] 16929. Two Dots(Python) / DFS 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문 www.acmicpc.net 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구하는 문제다. # 23분 소요 사용 알고리즘 : DFS 깊이 우선 탐색 설명할 것이 없는 듯.. 아래 코드와 같이 모든 정점에서 dfs를 돌리며 재귀로 갈 수 있는 곳으로 나아간다. 격자 밖이거나 이동할 곳의 문자가 다르다면 continue 방문할 수 있는 곳에만 방문 표시하며 재귀로 나아가고 출발지에 다다르고, 이동 횟수가 4번 이상이면 "Yes"를 출력하고 종료한다. 모든 재귀가 끝나도 사이클.. 2021. 4. 6. 이전 1 2 3 4 5 6 7 ··· 12 다음
