본문 바로가기
728x90
반응형

개발공부74

[BOJ] 11726번 2xn 타일링 / 사용언어 : 파이썬(python) ※ 문제링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 해당 문제는 메모이제이션 개념과 피보나치 수열의 개념을 이해하면 풀 수 있는 문제였다. 점화식 도출을 위해 간단하게 n = 1부터 n = 5까지 결과값을 생각해봤다. 각각의 n의 값이 1, 2, 3, 4, 5일때 결과값은 1, 2, 3, 5, 8이 도출되는 것을 확인하였고, n이3이상일때부터는 f(n) = f(n-1) + f(n-2)인것을 추론하여 문제에 대입해보았더니 해결이 되었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 바탕으로 메모이제이션을 적용하여 결.. 2022. 2. 1.
[BOJ] 10282번 해킹 / 사용언어 : 파이썬(python) ※ 문제링크 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 입력받은 값들로 그래프를 구현하고 다익스트라로 최단거리를 구해준 후 이어져 있는 컴퓨터의 수와 최대 시간만 출력해주면 되었기에 생각보다 쉽게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들과 2차원 리스트를 활용하여 그래프를 구현해준다. 2. 각각의 컴퓨터들로 갈 수 있는 최단시간을 구하기 위한 다익스트라 함수를 작성해준다. 3. 입력받은 값들로 결과값을 출력해.. 2022. 1. 30.
[BOJ] 1854번 K번째 최단경로 찾기 / 사용언어 : 파이썬(python) ※ 문제링크 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해당문제는 다익스트라를 활용하여 풀 수 있는 문제였다. 가중치가 있는 최단경로를 구하는 문제에서 조금 더 나아간 문제로, 간선으로 이어져있는 도시들을 k번째 수가 구해질때까지만 반복시키는 것이 핵심인 문제였다. 해당 부분은 메모이제이션과 정렬을 반복함으로써 해결하였으며, 테스트 결과 정상적으로 작동하는 것으로 확인했다. 다만, sys를 사용하고도 3528ms가 걸리는 것으로 확인했기에 sys를.. 2022. 1. 30.
[BOJ] 2665번 미로만들기 / 사용언어 : 파이썬(python) ※ 문제링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 해당문제는 우선순위큐 자료구조와 BFS를 활용하여 풀 수 있는 문제였다. 최단거리를 구하는 것이 아닌 최대한 적게 방을 바꾸는 길을찾는 것이 문제의 조건이었기에 최소힙을 활용하여 문제를 해결하였다. 문제풀이방법에 대해 간단하게 설명하면, BFS함수를 통해 4방위를 탐색하고, 탐색할때마다 가중치도 함께 저장하여, 가장 작은 가중치부터 꺼내는 방식으로 길을 찾아서 배열의 마지막 지점에 도달하면 탐색을 종료하고, 결과값을 출력하면 문제를 해결할 수 있었다.. 2022. 1. 30.
[BOJ] 1216번 알고스팟 / 사용언어 : 파이썬(python) ※ 문제링크 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 해당 문제는 우선순위 큐와 BFS를 활용해서 풀 수 있는 문제였다. 간단하게 풀이방법에 대해서 설명하면, 자신의 위치에서 상,하,좌,우를 확인할 수 있는 BFS함수를 작성하고, 조건을 만족하면 우선순위큐에 해당 자료를 넣은 다음 가장 작은 값부터 출력하는 최소힙을 활용하여 원하는 위치로 이동하기 위해서 부숴야하는 벽의 개수를 카운팅해주고, 이동을 완료했을 때의 부순 벽의 개수를 출력해주면되었다. 자세한 풀이방법과 코드는 아래와 .. 2022. 1. 29.
[BOJ] 2293번 동전 1 / 사용언어 : 파이썬(python) ※ 문제링크 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 해당 문제는 동적 프로그래밍과 관련된 문제로 메모이제이션을 활용하여 풀 수 있는 문제였다. 대다수의 동적프로그래밍 문제와 같이조건을 찾아내고 메모이제이션을 적용할 규칙을 확인하지 못하면 풀 수가 없어서 많이 애를 먹었던 문제였다. 기본적인 개념은 입력받은 숫자들만을 가지고 우선적으로 카운트를 해준다음, 1부터 구해야 하는 범위까지 입력값들을 반복하여 갱신해주는 개념으로문제를풀었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 리스트에 .. 2022. 1. 25.
[BOJ] 16236번 아기 상어 / 사용언어 : 파이썬(python) ※ 문제링크 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 해당문제는 BFS를 활용하여 풀 수 있는 문제였다. 여러가지 상황을 고려하여 구현을 해야했기에 풀이에 대한 방향성과 방법을 떠올리는 것보다 실제 구현이 더 오래 걸린 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 완전탐색을 통해 아기상어의 위치, 아기 상어가 먹을 수 있는 먹이의 개수와 좌표값을 구하고 저장한다. 2. 상어가 각 좌표로 이동할 수 있을때, 해당 좌표까지 이동하는데 걸리는 시간을 측정할 BFS함수로 구한다. 3. 문제.. 2022. 1. 23.
[BOJ] 2583번 영역 구하기 / 사용언어 : 파이썬(python) ※ 문제링크 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 해당 문제는 BFS를 활용하여 풀 수 있는 문제였다. 주의해야할 점은 y좌표값을 입력받은값을 그대로 사용하면 안된다는 점이었는데, 문제조건상에서의 y좌표값과 배열의 인덱스번호가 반대인 것을 고려하여 y좌표값을 음수로 변경 후 -1을 해주는 방식으로 변경한 후 사용하였다.(리스트의 마지막 인덱스 값과 -1이 동일한 것을 활용하였다.) 자세한 문제풀이 방법과 코드는 아래와 같다. 1. 입력받은 값을 바탕으로 방문여부를 확인할 2차원 .. 2022. 1. 23.
[BOJ] 11403번 경로 찾기 / 사용언어 : 파이썬(python) ※ 문제링크 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net ※ 관련개념 플로이드-워셜(Floyd-Warshall) 알고리즘 이론과 파이썬 구현 플로이드-워셜(Floyd-Warshall) 알고리즘 플로이드-워셜(Floyd-Warshall) 알고리즘은 모든 정점 사이의 최단 경로를 찾는 탐색 알고리즘입니다. 최단 경로는 길이 순으로 구해집니다. 플로이드 워셜 알 it-garden.tistory.com 해당 문제는 플로이드 와샬 알고리즘을 활용하여 풀 수 있는 문제였다. 가중치자체를 갱신하고 기록하지 않아도 되는 문제로 단순하게간선여부만 확인하면 되었기에 .. 2022. 1. 22.
728x90
반응형

티스토리툴바