728x90 반응형 BOJ71 [BOJ] 16234번 인구 이동 / 사용언어 : 파이썬(python) ※ 문제링크 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 해당문제는 BFS의 개념을 활용하여 사방위를 확인하고, 반복문을 통해 가능한 인구이동의 경우의 수를 체크하여 풀 수 있는 문제로, BFS의 기본적인 개념만 이해하고 있으면 통과는 생각보다 쉽게 가능했다. 다만, 단순한 반복문과 BFS의 조합으로 문제를 해결하면Pypy3로만 통과 가능하였고, Python3로 해결하기 위해서는 반복문을 반복할때 완전탐색을 하는 것이 아니라 이전의 결과값에 따라다르게 탐색을 하는 방식으로 구현해야하는 문제였다.. 2022. 4. 15. [BOJ] 2493번 탑 / 사용언어 : 파이썬(python) ※ 문제링크 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 해당 문제는 자료구조인 스택과 관련된 문제로 선입후출(FILO)의 개념을 활용하여 해결할 수 있는 문제였다. 3개의 리스트를 활용해 문제를 해결하였는데, 사실상 1개는 정답기록용으로 사용하였기에 실제 사용된 리스트는 2개라고 생각하면 될 것 같다. 기본 개념은 입력받은 타워의 높이를 하나의 리스트에 저장하고, 해당 값을 왼쪽부터 하나씩 꺼내서 다른 리스트에 쌓으며 비교를 반복하는 방식으로 해결하였으며, 조건에 부합하는 타워가 나타나면 바로 값을 기.. 2022. 4. 4. [BOJ] 1197번 최소 스패닝 트리 / 사용언어 : 파이썬(python) ※ 문제링크 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net ※ 관련개념 [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 해당 문제는 최소 스패닝 트리에 대한 개념을 이해할 수 있는 문제로, 2가지 방법으로 해결이 가능했다. 최소 신장트리에 대한 내용 및 문제 해결을 위해 이해가 필요한 프림 알고.. 2022. 4. 2. [BOJ] 2252번 줄 세우기 / 사용언어 : 파이썬(python) ※ 문제링크 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net ※ 관련개념 [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 해당 문제는 위상정렬 알고리즘의 대표적인 문제로 해당 알고리즘에 대한 기본적인 이해를 했으면 쉽게 해결할 수 있는 문제였다. 위상정렬을 간단하게 설명하면 들어오는 간선수를 확인하여 정렬을 하는 알고리즘.. 2022. 3. 26. [BOJ] 2531번 회전 초밥 / 사용언어 : 파이썬(python) ※ 문제링크 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net ※ 관련개념 슬라이딩 윈도우(Sliding Window) 알아두면 유용할 알고리즘을 하나 소개해본다 !!! velog.io 해당 문제는 투 포인터에서 변형된 슬라이딩 윈도우 방식으로 해결할 수 있는 문제였다. 슬라이딩 윈도우를 간단하게 설명하면 포인터 2개를 통해 일정 구간의 범위를 유지한채로 탐색하는 방법이라고 이해하면 되겠다. 해당 개념에 대해 잘 설명해놓은 사이트가 있어서 링크를 걸어두었으니 좀 더 자세한.. 2022. 3. 26. [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. 이전 1 2 3 4 ··· 8 다음 728x90 반응형
