728x90 분류 전체보기 썸네일형 리스트형 [백준알고리즘] 2003번: 수들의 합 2 -Python [백준알고리즘] 2003번: 수들의 합 2 -Python https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1≤N≤10,000), M(1≤M≤300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 두 가지 방법으로 문제를 해결했다. 쉽게 봤다가 시간제한이 0.5 임을 나중에 보고 Python으로 포기하기도 했었다.. 결국 Python으로도 통과하긴 했다. 연속합을 직접 구해준 방법 더블 포인터를 사용해 값을 찾아간 방법 1번 방법 처음에는 1부터 I까지의 합에서 1부터 J까지의 합을 빼서 J부터 K까지의 값.. 더보기 [백준알고리즘] 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 .. 더보기 [백준알고리즘] 1987번: 알파벳 -Python [백준알고리즘] 1987번: 알파벳 -Python https://www.acmicpc.net/problem/1987 1987번: 알파벳 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 www.acmicpc.net 20200404. 새로 풀었다. 이번에도 PyPy로만 통과가 가능했다. 처음에는 모양이 달.. 더보기 [백준알고리즘] 1759번: 암호 만들기 -Python [백준알고리즘] 1759번: 암호 만들기 -Python https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net itertools 모듈의 combinations 메서드를 사용해서 쉽게 주어진 알파벳의 조합 쌍을 만들 수 있었다. combinations를 사용하지 않는 경우 조합을 만들기 위해서는 DFS방식처럼 하나씩 조합의 길이만큼 원소를 추가해 나가면 된다. combinations에 넣기 전에 정렬해줌으로써 정렬된 조합의 결과들은 모두 각각 정렬된 상태로 .. 더보기 [백준알고리즘] 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 형식으.. 더보기 [백준알고리즘] 2186번: 문자판 -Python [백준알고리즘] 2186번: 문자판 -Python https://www.acmicpc.net/problem/2186 2186번: 문자판 첫째 줄에 N(1 ≤ N ≤ 100), M(1 ≤ M ≤ 100), K(1 ≤ K ≤ 5)가 주어진다. 다음 N개의 줄에는 M개의 알파벳 대문자가 주어지는데, 이는 N×M 크기의 문자판을 나타낸다. 다음 줄에는 1자 이상 80자 이하의 영단어가 주어진다. 모든 문자들은 알파벳 대문자이며, 공백 없이 주어진다. www.acmicpc.net 일단 파이썬보다는 PyPy로 통과할 확률이 높다. 이번 문제에서도 BFS 혹은 DFS를 통해서 주어진 문자열을 모두 완성할 수 있는 경우의 수를 구해주면 된다고 생각했다. 처음에는 이전에 몇 번 풀었던 것처럼 방문 여부를 확인하는 vis.. 더보기 [백준알고리즘] 2251번: 물통 -Python [백준알고리즘] 2251번: 물통 -Python https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다. 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. www.acmicpc.net 이번 문제에서도 visit을 딕셔너리로 사용했다. 그리고 (A, B, C)에 존재하는 물의 양.. 더보기 이전 1 ··· 28 29 30 31 32 33 34 ··· 50 다음