728x90 백준16 [백준 / C언어] 미로탐색 (2178) 📌 문제 링크 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net BFS를 통해 문제를 해결했다. 큐를 만들어서 좌표와 이동한 횟수를 관리했으며, 큐가 빌 때까지 4방향을 탐색하고, 길이 아니거나 이미 방문한 길이라면 continue를 해주고 원하는 좌표에 도착하면 return해준다. 처음과 끝을 포함하지 못했기 때문에 +2를 해주었다. 👩💻 전체코드 #include int N, M; int graph[100+10][100+10]; int visited[100+10][100+1.. 2024. 4. 1. [백준 / 파이썬] 그림 (1926) BFS DFS 문제 중 하나인 문제 BFS DFS문제가 문제 풀이 방법은 이해했는데 내 힘으로 풀기가 너무 어려워서 계속해서 연습할 예정이다 +) 최대한 DFS, BFS 두 가지로 문제 풀이 연습하기! 📌 풀이 문제 https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 🤔 DFS란 ? DFS : 깊이 우선 탐색 (Depth-FIrst Search) - 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색 - 스택 또는 재귀함수로 구현 - 검색 속도는 BFS.. 2023. 4. 13. [백준 / 파이썬] 단어 수학(1339) 어떻게 풀어야할지는 떠올랐지만 구현을 못 한 문제 딕셔너리는 왜 이렇게 적응이 안되는지 모르겠다 📌 풀이 문제 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제에서 보면 유추할 수 있 듯, 가장 높은 자리 수에 있는 알파벳에 큰 수를 부여해야한다. 또한, 중복되는 알파벳으로 계산될 수 있다는 점도 유의해야한다. 👩💻 풀이방법 0. 요소들을 입력받는다 1. 각 알파벳을 자리수에 맞게 정리한다. 예를 들어 ACDEB = A : 10000.. 2023. 4. 12. [백준/파이썬] 30 (10610) 처음 본 풀이 방식이라 기억할라고 정리하는 문제~ 📌 풀이 문제 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 👩💻 풀이방법 1 (틀린 풀이) : 메모리 초과 처음에는 input 받은 숫자를 순열을 사용하여 만들 수 있는 모든 경우의 수로 숫자를 하나하나 만들었다. 그 다음에 만든 숫자를 30으로 나눠보며 나누어 떨어진다면 바로 break 후, 출력 시켰다 from itertools import permutations #순열 사용을 위한 im.. 2023. 4. 11. [python] 단계별로 풀어보기 - 12단계 계수 정렬 / 카운팅 정렬 시간 복잡도 : O(n+k) (k는 데이터의 최댓값) => 속도가 엄청 빠름. 퀵 정렬, 힙 정렬, 합병 정렬의 평균 시간 복잡도 => O(nlogn) 정렬 방법: 데이터가 몇번 나왔는지 count -> 받은 수가 몇 번 들어왔는지 빈도 계산 -> 등장 횟수를 누적 합으로 바꾸기 -> 입력받았던 정렬할 배열을 뒤에서 앞으로 순회하면서 정렬된 배열에 넣기. (넣어준 뒤에는 누적합 -1 해주기) 정리: 시간 복잡도는 훨씬 유리하지만, 엄청난 메모리 낭비를 야기할 수 있음. (배열에 포함된 최댓값 만큼 메모리가 필요함) 따라서, k가 엄청 크다면 차라리 퀵정렬, 힙 정렬, 합병 정렬을 쓰는 것이 나음. 또한, 데이터 값이 정수라는 전제가 있어야한다. 순서대로 정렬을 해 주는데.. 2021. 5. 10. 이전 1 2 3 4 다음 728x90
