728x90 반응형 개발공부74 [BOJ] 1012번 유기농 배추 / 사용언어 : 파이썬(python) ※ 문제링크 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해당문제는 DFS와 BFS를 사용하여 해결할 수 있는 문제였다. 단순하게 상, 하, 좌, 우에 연결되어 있는 배추의 위치들을 활용하여 연결된 그래프의 수가 몇개인지 구하면 되는 문제였기에 크게 어렵지 않게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 2차원 배열로 배추밭을 구현한다. 2. DFS 또는 BFS를 사용하여 연결된 배추들을 확인할 함수를 작성한다. 3. 2중 반복문을 활용하여 배추밭의 모든 위치를 확인하고, .. 2022. 1. 6. [BOJ] 2667번 단지번호 붙이기 / 사용언어 : 파이썬(python) ※ 문제링크 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당문제는 DFS와 BFS를 활용하여 풀 수 있는 문제였다. 조건은 간단하여 풀이방법을 떠올리는 것은 그리 어렵지 않았으나, 구현하는난이도가 생각보다 어려워서 꽤나 시간이 걸린 문제였다. 풀이방법에 대해 간단하게 이야기하면, 입력받은 문자열을 2차원 배열로 변환한 후, 배열 상 값이 1인 경우에 한하여 DFS 또는 BFS를 활용하여 해당 점을 기준으로 상, 하, 좌, 우를 확인하여 조건 충족하면 계속 탐색하여 결과를 작성하는 방식으로 해결하였다. 자세.. 2022. 1. 6. [BOJ] 2606번 바이러스 / 사용언어 : 파이썬(python) ※ 문제링크 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 해당문제는 DFS 또는 BFS로 해결할 수 있는 문제였다. 두가지방법 모두 사용하는 방법을 숙달하기 위해서 두가지 방법을 모두 이용해서 코드를 작성해보았고, 그래프는 딕셔너리를 이용하여 구현하였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 반복문과 딕셔너리를 활용하여 그래프 형태로 변환한다. 2. dfs와 bfs함수를 작성하여 연결되어 있는 노드의 개수를 확인하고 결과값을 출력한다. + 처음에 작성한 코드는 dfs는 통과가 되었으나 bfs가 .. 2022. 1. 5. [BOJ] 1260번 DFS와 BFS / 사용언어 : 파이썬(python) ※ 문제링크 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ※ 관련개념 및 참고사이트 [Daily PS] 파이썬으로 구현하는 BFS와 DFS 파이썬으로 BFS와 DFS를 구현하는 내용입니다. cyc1am3n.github.io 해당 문제는 BFS와 DFS를 구현하는 문제였다. 문제를 풀기 전 개념에 대한 이해를 위해 구글링을 하던 중 설명이 잘 되어 있는 사이트가 있어서 해당 사이트를 참고하여 구현해보았다. 문제해결을 위해서는 먼저 입력값을 그래프 형태로 만들어주는 것이 .. 2022. 1. 5. [BOJ] 1759번 암호만들기 / 사용언어 : 파이썬(python) ※ 문제링크 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 해당문제는 DFS와 백트래킹을 일부 변형해서 풀 수 있는 문제였다. 문제 조건중 모음(1개이상)과 자음(2개이상) 최소개수가 주어졌기에 해당 조건을 추가시켜서 풀었더니 금방 풀 수 있었고, 정상적으로 작동하는 것을 확인했다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 변수로 할당해주고, 알파벳은 리스트로 변환 후 내장함수를 활용하여 정렬해준다. 2. 알파벳의 모음, 자음여부를 판단할 변수들을 만들고 값을 할당한다. 3. 시작값과 모음갯수.. 2022. 1. 4. [BOJ] 6603번 로또 / 사용언어 : 파이썬(python) ※ 문제링크 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 해당 문제는 DFS와 백트래킹을 활용하여 푸는 문제였다. 주어진 숫자에 대해 알고리즘을 활용하여 조합수를 구하고 그 중 만족하는 수만 구하면 되는 문제라 어렵지않게 풀 수 있는 문제였다. 자세한 문제풀이 방법과 코드는 아래와 같다. 1. 입력받은 숫자를 리스트로 만들고, 첫번째 요소가 0이고, 리스트의 길이가 1이면 반복문을 중지하도록 조건을 건다. 2. 첫번째 숫자를 k로 그 뒤의 숫자는 n-list로 분할하여 저장한 후 dfs와 백트래.. 2022. 1. 3. [BOJ] 2110번 공유기 설치 / 사용언어 : 파이썬(python) ※ 문제링크 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net ※ 관련문제 [BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python) ※ 문제링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고,. data-is-power.tistory.com 해당문제는 이분탐색과.. 2022. 1. 1. [BOJ] 2805번 나무 자르기 / 사용언어 : 파이썬(python) ※ 문제링크 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ※ 관련문제 [BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python) ※ 문제링크 : https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고,. data-is-power.tistory.com 해당문제는 이분탐색과 매개변수탐색.. 2021. 12. 30. [BOJ] 1654번 랜선 자르기 / 사용언어 : 파이썬(python) ※ 문제링크 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net ※ 관련개념 및 참고사이트 [알고리즘] 이분 탐색 / 이진 탐색 (Binary Search) 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 velog.io [알고리즘] 매개변수 탐색(Parametric Search) 이번시간에는 매개변수탐색에 대해서 알아보겠습니다. 매개변수탐색이라는 단어.. 2021. 12. 30. 이전 1 ··· 5 6 7 8 9 다음 728x90 반응형
