728x90 탐색 썸네일형 리스트형 [백준알고리즘] 1039번: 교환 -C++ [백준알고리즘] 1039번: 교환 -C++ 1039번: 교환 (acmicpc.net) 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 굉장히 어려웠다. 풀고 제출을 했었는데 틀렸다고 나왔고 해당 문제가 뭔지 알았는데, 고치지 못했다. 결국 다른 분의 블로그를 참고해서 문제를 푸는 법을 알았고, 이해한 내용을 바탕으로 다른 내용으로 풀고 싶었다. 아래 블로그의 얍문님의 포스팅을 보고 BFS로 푸는 방법에 대해서 알게 됐다. [ 백준 1039 ] 교환 (C++) :: 얍문's Coding World.. (tistory.com) [ 백준 1039 ] 교환 (C++) 백준의 교환(103.. 더보기 [백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python [백준알고리즘] 1620번: 나는야 포켓몬 마스터 이다솜 -Python https://www.acmicpc.net/problem/1620 1620번: 나는야 포켓몬 마스터 이다솜 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 www.acmicpc.net 문제가 굉장히 길다 ㅎㅎ;; 쭉 아래로 내려서.. 더보기 [백준알고리즘] 2512번: 예산 -Python [백준알고리즘] 2512번: 예산 -Python https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 100,000 이하이다. 그 다음 줄에는 총 예산을 나타내는 정수 M이 주어진다. M은 N 이상 1,000,000,000 이하이다. www.acmicpc.net 상한액보다 많은 예산을 요구하면 상한액까지만 지급하고 상한액보다 낮은 예산을 요구하면 모두 지급하면 된다. 이 총액이 주어진 총 예산보다 낮거나 같은 최대의 상한액을 구하면 된다. 이분 탐색으로 풀어주었다. 다양한.. 더보기 [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python [백준알고리즘] 12015번: 가장 긴 증가하는 부분 수열 2 -Python https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 가장 긴 증가하는 부분 수열 1을 풀었던 방식으로는 해결하지 못한다. 수열 A의 원소의 개수도 늘어났고, A를 이루는 원소의 범위도 넓어졌다. O(N^2)의 방법인 이중 for문으로는 시간 안에 통과하지 못한다는 것을 알 수 있다. 질문 게시판에서 이중 for문을 돌릴 때 안쪽 for문에서 세그먼트 트리나 이진 탐색으로 .. 더보기 [백준알고리즘] 2178번: 미로 탐색 -Python [백준알고리즘] 2178번: 미로 탐색 -Python https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 문제는 반드시 (1, 1)에서 (N, M)으로 가는 것이기 때문에 길만 따라가면 돼서 간단하게 해결했다. BFS로 문제를 풀었고, 이동한 각 지점에서 상하좌우를 큐에 넣어주었다. 큐에서 꺼낼 때 경곗값 검사를 진행해주었고, 해당 위치가 길이 맞는지 확인해주었다. import sys from collections import deque def bfs(): queue = d.. 더보기 [백준알고리즘] 4963번: 섬의 개수 -Python [백준알고리즘] 4963번: 섬의 개수 -Python https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러쌓여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 www.acmicpc.net 이전에 풀었던 단지번호붙이기 문제와 유사하다. 상하좌우의 값과 추가적으로 대각선만 더.. 더보기 [백준알고리즘] 2805번: 나무 자르기 -Python [백준알고리즘] 2805번: 나무 자르기 -Python https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net 20200418 아래에 새로 푼 코드를 추가했다. 이분 탐색 문제이다. 이전에.. 더보기 이전 1 다음