[백준] 1260번 - 음식물 피하기 (파이썬)

백준 1260번 음식물 피하기 문제 "💡 문제 해결 아이디어 " 해당 문제는 BFS를 통해 해결할 수 있었다. 음식물 피하기는 어떤 가장 큰 음식물 쓰레기의 사이즈를 구하는 문제이다. 음식물 쓰레기는 근처(상,하,좌,우)에 붙어있으면 더 큰 크기로 변하는데 가장 많이 붙어있는 음식물 쓰레기의 범위를 구하면 되는 문제이다. 이러한 힌트가 문제에 주어지는데 이처럼 그래프를 형성하여 BFS를 통해 가장 많이 연결되어있는 '#'의 count를 구해 답을 유추했다. 0,0 ~ n-1,m-1 범위를 이중 반복문으로 모두 방문하며 그래프의 값이 '#'이면 bfs를 통해 연결되어있는 음식물 쓰레기의 갯수를 구해 return한다. 여기서 return 받은 값들 중 가장 큰 값이 답이기 때문에 max라는 변수를 -1로 초..

• format_list_bulleted 코딩테스트/백준
• · 2023. 1. 19.
• textsms

[백준] 1260번 - DFS와 BFS(파이썬)

백준 1260번 DFS와 BFS DFS와 BFS를 사용하여 정렬한 값을 출력하는 문제이다. 💡 문제 해결 아이디어 정답 비율이 낮아 재밌어보여 풀어보았는데 그냥 단순히 DFS와 BFS 알고리즘을 통해 해결할 수 있는 문제였다. 아마 낮은 정답률의 원인이 정점 번호가 작은 것을 먼저 방문하는 것 때문인 거 같다. 방향이 주어지지 않았기 때문에 노드가 서로 바라보도록 연결하면 되겠다고 생각하여 연결되는 두 노드(node1, node2)를 입력받으면 그래프의 node1 위치에 node2를 추가하고 node2 위치에 node1을 추가하여 서로 연결시켰다. 여기서 중요한 점은 graph에 등록하고 등록된 그래프를 오름차순 정렬 시켜주는 코드이다. 정렬은 list의 기본 메서드인 sort()를 통하여 해결하였다. ..

• format_list_bulleted 코딩테스트/백준
• · 2023. 1. 17.
• textsms

[백준] 2583번 - 영역 구하기 (파이썬)

백준 2583번 영역 구하기 문제 영역 구하기 문제는 빈 공간의 넓이와 갯수를 계산하여 출력하는 문제이다. 이번 문제는 BFS를 사용하면 간단히 해결할 수 있을 것 같아 BFS방식을 채택하여 해결하였다. "💡 문제 해결 아이디어 " 벽과 벽이 아닌 곳의 구분을 하기 위해 벽:1, 벽이 아닌 곳:0으로 구현하기로 정하고 문제 해결에 들어갔다. 우선 입력받은 가로, 세로의 길이를 통해 높이가 M, 너비가 N인 직사각형을 만든다. 반복문을 통한 2차원 배열 생성 방식으로 그래프를 생성하였고 각 1차원 배열의 값은 모두 0으로 채운다. 그럼 [[0,0,0,0,0,0], [0,0,0,0,0,0], ...] 과 같은 형태의 그래프가 그려진다. 그 다음 좌표 x1,y1,x2,y2값을 K번 입력받는데, 입력 받을 때마..

• format_list_bulleted 코딩테스트/백준
• · 2023. 1. 16.
• textsms

[백준] 1012번 - 유기농 배추 (파이썬 Recursion Error 해결)

백준 1012번 문제 파이썬 "💡 문제 해결 아이디어" 유기농 배추 문제는 완전 탐색을 통해 해결해야하는 문제이다. 본인은 dfs를 통해 해결하였다. 0,0부터 n-1,m-1 까지 모두 돌며 값이 1인 곳(배추가 심어진 곳)을 찾는다. 지렁이는 상하좌우로 퍼져나갈 수 있기 때문에, 배추가 심어진 곳을 발견하면 그 구간에서 dfs를 돌려 인접해있는 1들을 모두 0으로 변경하고 1을 카운트한다. 이렇게 하면 인접해 있는 배추 그룹의 갯수를 전부 파악할 수 있어 지렁이가 총 몇 마리 필요한 지 구할 수 있다. "❗ 런타임 에러(RecursionError) 해결" dfs를 사용하면 편리하지만 벡준에서 지정한 기본 재귀 depth 때문에 런타임에러가 발생한다. 때문에 sys.setrecursionlimit()을 ..

• format_list_bulleted 코딩테스트/백준
• · 2023. 1. 15.
• textsms

[백준] 1181번 - 단어 정렬

백준 1181번 단어 정렬 문제입니다. https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 💡 문제 해결 아이디어 1181번 문제는 n개의 문자열을 입력받아 길이 순서대로 오름차순 정렬 후, 같은 길이의 문자열는 문자열 알파벳 순서대로 오름차순 정렬한 결과를 출력하는 문제입니다. 1. 이 문제는 같은 데이터를 받으면 안 되기 때문에 set으로 데이터를 입력받은 후 정렬을 위해 list로 변환시켜 word_list에 저장하고, 오름차순으로..

• format_list_bulleted 코딩테스트/백준
• · 2022. 10. 1.
• textsms

1. Grid & Implementation - 그리드 & 구현 알고리즘

그리디 알고리즘 - 현재 상황에서 지금 당장 좋은 것만 고르는 방법 - 일반적으로 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 요구 ★ 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 즉, 그리디 알고리즘으로 최적의 해가 나오는 상황에서만 사용해야 한다. 그리디 알고리즘 예시 1. 거스름 돈 문제 # 거스름 돈 문제 # 거스름 돈을 500 , 100 , 50 , 10 원으로 줄 때 각 동전의 갯수 money_list = [500, 100, 50, 10] change = int(input()) result = [0, 0, 0, 0] for i in range(len(money_list)): result[i] = (change // m..

• format_list_bulleted 코딩테스트
• · 2022. 8. 17.
• textsms