728x90 BFS 썸네일형 리스트형 [백준알고리즘] 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.. 더보기 [백준알고리즘] 2798번: 블랙잭 -Python, C++ [백준알고리즘] 2798번: 블랙잭 -Python, C++ 2798번: 블랙잭 (acmicpc.net) 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 저번에도 파이썬으로 풀었던 문제인데, 파이썬은 먼저 조합을 모두 구한 뒤 적절한 답을 찾았다면, 이번에 푼 C++은 약간 다르게 풀었다. BFS와 비슷하게 풀었으며, \(Queue\)를 사용했다. \(Queue\) 안에는 tuple을 사용해서 세 개의 값을 쌍으로 단위 처리했다. tuple 안에는 (카드 선택 횟수, 현재까지 선.. 더보기 [백준알고리즘] 2573번: 빙산 -Python [백준알고리즘] 2573번: 빙산 -Python https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 나타내는 M개의 정수가 한 개의 빈 칸을 사이에 두고 주어진다. 각 칸에 들어가는 값은 0 이상 10 이하이다. 배열에서 빙산이 차지하는 칸의 개수, 즉, 1 이상의 정수가 들어가는 칸의 개수는 10,000 개 이하이다. 배열의 첫 번째 행과 열, 마지 www.acmicpc.net 이 코드는 PyPy3로만 통과한 코드다. Python3로는 시간 초과가 발생한다. 사실 처음.. 더보기 [백준알고리즘] 14502번: 연구소 -Python [백준알고리즘] 14502번: 연구소 -Python https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 20200423 아래에 PyPy3로만 통과한 코드를 추가했다. PyPy로만 통과가 됐지.. 더보기 [백준알고리즘] 1261번: 알고스팟 -Python [백준알고리즘] 1261번: 알고스팟 -Python https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다. www.acmicpc.net 굉장히 난감했던 문제인데 다른 분들의 코드도 보니 별거 아니었다. 우선은 처음에는 그냥 DFS(백트래킹) 혹은 BFS 방식으로 문제를 풀려고 했다. 하지만 문제의 경우 이미 방문했던 좌표라고 할지라도 어디로부터 방문했는지에 따라서 해당 좌표까지 이동하면서 벽을 부순 횟수가 달.. 더보기 [백준알고리즘] 1182번: 부분수열의 합 -Python [백준알고리즘] 1182번: 부분수열의 합 -Python https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 뻘짓했당 부분 수열이라고만 했는데 연속된 부분 수열인 줄 알고 계속 시도했었다.. 반례도 찾아가면서... 그러다가 아래의 반례를 찾고는.. 그냥 아무렇게나 뽑아서 만든 부분 수열이란 것을 알았다. 5 0 0 0 0 0 0 output:31 바로 combinations 메서드 써서 통과했다. 1 2 3 4 .. 더보기 [백준알고리즘] 5014번: 스타트링크 -Python [백준알고리즘] 5014번: 스타트링크 -Python https://www.acmicpc.net/problem/5014 5014번: 스타트링크 문제 강호는 코딩 교육을 하는 스타트업 스타트링크에 지원했다. 오늘은 강호의 면접날이다. 하지만, 늦잠을 잔 강호는 스타트링크가 있는 건물에 늦게 도착하고 말았다. 스타트링크는 총 F층으로 이루어진 고층 건물에 사무실이 있고, 스타트링크가 있는 곳의 위치는 G층이다. 강호가 지금 있는 곳은 S층이고, 이제 엘리베이터를 타고 G층으로 이동하려고 한다. 보통 엘리베이터에는 어떤 층으로 이동할 수 있는 버튼이 있지만, 강호가 탄 엘리베이터는 버튼이 2개밖에 없 www.acmicpc.net 이번 문제는 BFS 방식으로 풀었다. 나머지는 간단했다. 방문했던 층인지 점검하고.. 더보기 [백준알고리즘] 3108번: 로고 -Python [백준알고리즘] 3108번: 로고 -Python https://www.acmicpc.net/problem/3108 3108번: 로고 문제 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 각도로 표현할 수 있다. 거북이는 입에 연필을 물고 있는데, 연필을 내리면 움직일 때 화면에 선을 그리고, 올리면 선을 그리지 않고 그냥 지나가기만 한다. 제일 처음에 거북이는 (0,0)에 있고, 거북이가 보고 있는 방향은 y축이 증가하는 방향이다. 또한 연필은 내 www.acmicpc.net 한 번도 들어본 적 없는 로고라는 언어가 있다고 한다. 이 문제는 Union-Find 형식으.. 더보기 이전 1 2 3 4 다음