728x90 반응형 개발공부74 [BOJ] 1743번 음식물 피하기 / 사용언어 : 파이썬(python) ※ 문제링크 1743번: 음식물 피하기 첫째 줄에 통로의 세로 길이 N(1 ≤ N ≤ 100)과 가로 길이 M(1 ≤ M ≤ 100) 그리고 음식물 쓰레기의 개수 K(1 ≤ K ≤ N×M)이 주어진다. 그리고 다음 K개의 줄에 음식물이 떨어진 좌표 (r, c)가 주어진다 www.acmicpc.net 해당문제는 탐색과 관련된 문제로 DFS나 BFS를 통해 해결할 수 있는 문제였다. 이번 풀이에서는 BFS를 통해 문제를 해결했는데, 문제해결의 핵심은 쓰레기들의 위치를 기록 및 표기하고, 인접해있는 쓰레기들의 수의 최댓값을 출력하는 것이었다. 문제를 해결하면서 방문여부는 따로 배열을 만들지 않고, 쓰레기들의 위치를 기록한 기본테이블을 약간 변형하였으며, 해당 문제는 최단거리를 찾는 것이 아니라 인접한 쓰레기들.. 2022. 3. 19. [BOJ] 1520번 내리막 길 / 사용언어 : 파이썬(python) ※ 문제링크 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 해당문제는 DFS와 DP를 활용해서 해결할 수 있는 문제로, 단순히 답만 출력하는 것은 DFS 또는 BFS코드만으로도 가능하나, 문제에서 요구하는 시간 및 메모리 조건을 충족시키기 위해서는 DP까지 활용하여 해결해야하는 문제였다. 주의해야할 점은 DP를 통해 방문한 경로들에 대해 따로 탐색을 하지 않게 조건을 작성할때 DP의 초기값을 0이 아닌 다른 값으로 주어야 한다는 것인데, 0으로 초기값을 주게되면 그 경로를 방문했으나 그 값이 0으로 저장될 수도 .. 2022. 3. 13. [BOJ] 13424번 비밀 모임 / 사용언어 : 파이썬(python) ※ 문제링크 13424번: 비밀 모임 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 방 www.acmicpc.net 해당 문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 파이썬에서는 heapq로 최소힙을 지원해주고 있기에 해당 라이브러리를 사용해서 문제를 해결하였다. 다익스트라 알고리즘으로 각 방에서 다른 방으로의 최소 거리를 구한 후에 해당 값들을 하나의 리스트에 저장해주고, 종료 후에 가장 작은 거리값을 가지는 방의 이름을 출력해주면 되는 문제로, 다익스트라 알고리즘을 구현할 수 있다면 크게 어렵지 않은 문제였다. 자세한 문제풀이방법과 코드는 아래와.. 2022. 3. 12. [BOJ] 2467번 용액 / 사용언어 : 파이썬(python) ※ 문제링크 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 해당 문제는 투 포인터를 이용해서 해결할 수 있는 문제였다. 리스트의 양 끝단부터 조건에 따라 탐색하고, 탐색 종료 후 결과값을 출력하면 되는 문제였다. 조건 중에 입력값이 오름차순으로 정렬되어 들어온다는 조건이 있기에 정렬을 따로 수행하지 않아도 통과가 가능하였다. 주의해야할 점은 두 용액의 특성값이 음수일 수도 있다는 점인데, 반드시 비교를 하고 값을 저장할때는 절댓값을 사용해야했다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은.. 2022. 3. 12. [BOJ] 1946번 신입 사원 / 사용언어 : 파이썬(python) ※ 문제링크 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 해당 문제는 그리디 알고리즘과 관련된 문제로, 브루스포트 알고리즘을 접목해서 해결할 수 있는 문제였다. 문제에서 제시된 조건은 서류와 면접성적 중 1가지는 반드시 다른 지원자들보다 높은 성적이어야 합격이 가능하다는 점이었다. 서류심사 성적 또는 면접성적을 오름차순으로 정렬하여 반복문을 돌리면 1가지 성적만 가지고도 비교가 가능했기에 서류심사 성적을 오름차순으로 정렬한 후 그리디 알고리즘을 활용하여 모든 경우의 수를 비교하며 문제.. 2022. 3. 12. [BOJ] 9663번 N-Queen / 사용언어 : 파이썬(python) ※ 문제링크 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 해당문제는 백트래킹 알고리즘의 대표적인 문제로 DFS, 브루스포트 알고리즘을 추가로 활용하여 해결할 수 있는 문제였다. 처음에는 2차원 배열을 활용하여 문제를 해결하려고 하였으나, N의 값에 따라 탐색할 경우의 수가 급격하게 증가하기 때문에 문제 해결방안으로 부적절한 것을 알게되었다. 다른 방법의 풀이를 생각하던 중 퀸의 동작원리 상 한개의 행에는 1개의 퀸밖에 들어갈 수 없고, N x N 체스판에 N개의 퀸을 놓기위해서는 각 행에 퀸이 하나씩 반드시 들어가야한다는.. 2022. 3. 12. [BOJ] 15654번 N과 M(5) / 사용언어 : 파이썬(python) ※ 문제링크 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 해당 문제는 백트래킹과 관련된 문제로 DFS를 활용한 재귀를 통해 해결할 수 있는 문제였다. 백트래킹의 기본적인 원리를 구현할 수 있다면 쉽게 해결할 수 있었고, 중복을 허용하지 않고, 숫자가 같아도 순서가 다르면 다르다는 점을 고려하여 해결하면 되는 문제였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 리스트에 저장하고, 오름차순으로 정렬해준다. 2. 숫자들의 순열조합을 작성할 DFS함수를 백트래킹을 적용해서 작성하고, 조.. 2022. 3. 9. [BOJ] 2539번 보물섬 / 사용언어 : 파이썬(python) ※ 문제링크 2589번: 보물섬 첫째 줄에는 보물 지도의 세로의 크기와 가로의 크기가 빈칸을 사이에 두고 주어진다. 이어 L과 W로 표시된 보물 지도가 아래의 예와 같이 주어지며, 각 문자 사이에는 빈 칸이 없다. 보물 지도의 www.acmicpc.net 해당 문제는 브루스포트 알고리즘과 BFS를 활용하여 푸는 문제였다. 간단하게 말해서 그냥 BFS로 탐색할 수 있는 함수를 구현하고, 모든 좌표에서 모든 경우의 수를 찾아서 비교한 후 결과값을 출력하면 되는 문제였다. 문제 조건에서 보물은 서로 가장 멀리 떨어져있고, 최단거리로 이동하라고 나와있는데, 해당 조건은 그냥 가장 먼 좌표 2개의 거리를 구하면 된다는 걸 두번 말하고 있는 것이니 가장 거리가 먼 육지좌표 2개의 거리를 출력할 수 있게 하면 된다... 2022. 3. 7. [BOJ] 1339번 단어 수학 / 사용언어 : 파이썬(python) ※ 문제링크 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해당 문제는 그리디 알고리즘과 브루스포트 알고리즘과 관련된 문제로 둘 중 1개만 활용해도 풀 수 있는 문제였다. 브루스 포트 알고리즘은 모든 경우의 수를 탐색해야하기에 시간제한이 빠듯할 것 같다 생각하여 그리디 알고리즘 쪽에 초점을 맞춰 논리성을 찾는데 보다 주안점을 두고 해결하였다. 해결을 위해 사용한 논리적 조건은 아래와 같다. 1. 입력받은 알파벳별로 자릿수를 분류하고, 알파벳들이 등장할 때마다 자릿수를 기록하여 더해준다. 2. 입력값들에.. 2022. 3. 6. 이전 1 2 3 4 5 ··· 9 다음 728x90 반응형
