728x90 Algorithm 썸네일형 리스트형 [백준알고리즘] 2098번: 외판원 순회 -Python [백준알고리즘] 2098번: 외판원 순회 -Python https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 전에 외판원 순회 2를 푼 적이 있었는데, 그 이전 문제인 것 같다. 풀이는 여기에 썼었다. 외판원 순회 2와 같은 방법으로 문제를 풀면 된다. 전에 비트 마스크로 풀었던 기억이 인상 깊게 남아있었어서, 그렇게 풀까 하다가 브루.. 더보기 [백준알고리즘] 10164번: 격자상의 경로 -Python [백준알고리즘] 10164번: 격자상의 경로 -Python https://www.acmicpc.net/problem/10164 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으로 구분된다. K의 값이 0인 경우도 있는데, 이는 ○로 표시된 칸이 없음을 의미한다. N과 M이 동시에 1인 경우는 없다. www.acmicpc.net 경우의 수를 구해주는 문제이다. DP를 사용해 모든 경우의 수를 구해주면 된다. O표시가 없는 경우(k=0인 경우)에는 시작점에서 끝점까지 이동할 수 있는 모든 경우의 수를 구해주.. 더보기 [백준알고리즘] 5557번: 1학년 -Python [백준알고리즘] 5557번: 1학년 -Python https://www.acmicpc.net/problem/5557 5557번: 1학년 문제 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 상근이는 올바른 등식을 만들려고 한다. 상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. www.acmicpc.net 별생각 없이 딕셔너리를 이용해서 풀었다. 현재까지의 누적 계산량과 인덱스를 쌍으로 하는 튜.. 더보기 [백준알고리즘] 1138번: 한 줄로 서기 -Python [백준알고리즘] 1138번: 한 줄로 서기 -Python https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i보다 작거나 같다. www.acmicpc.net 키가 1인 사람부터 차례대로 세워주었다. 주어진 입력에 따라서 자신보다 키가 큰 인원의 수만큼 왼쪽에 빈자리를 놔두고 자리를 잡으면 된다. 예를 들어 주어진 2 1 1 0 에 대해서는 1보다 키가 큰 사람이 왼쪽에 두 명이 있어야 하기 때문에 왼쪽에 빈자리를 두 개 두고 위치하면 된다. 0 0 .. 더보기 [백준알고리즘] 1080번: 행렬 -Python [백준알고리즘] 1080번: 행렬 -Python https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 코드가 조금 지저분해보이기는 하지만 그리디 알고리즘을 사용했다. 반복문을 사용하지 않고 재귀를 통해서 문제를 해결했다. DFS방식의 재귀 깊이 때문에 런타임에러가 발생했었고, 모든 경우에 대해서 3x3을 변환시키고, 다시 원상태로도 진행을 하는 2가지 방법을 적용했었기 때문에 시간 초과가 발생했었다. 시간 초과가 발생한 경우에 대해서 더 설명을 하자면, 현재 위치.. 더보기 [백준알고리즘] 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 상한액보다 많은 예산을 요구하면 상한액까지만 지급하고 상한액보다 낮은 예산을 요구하면 모두 지급하면 된다. 이 총액이 주어진 총 예산보다 낮거나 같은 최대의 상한액을 구하면 된다. 이분 탐색으로 풀어주었다. 다양한.. 더보기 [백준알고리즘] 10830번: 행렬 제곱 -Python [백준알고리즘] 10830번: 행렬 제곱 -Python https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 빠른 모듈로 거듭제곱을 개념을 이용해 행렬 곱셈을 수행했다. 분할 정복의 개념을 사용했고 아래와 같은 방식에 각 원소마다 모듈로를 해주는 것으로 수행했다. A^11 = A^10 * A^10 * A^1 A^8 = A^4 * A^4 코드 내용은 거의 같으나 @iknoom1107 님의 코드를 보니 for문으로 작성했던 부분을 sum()을 이용해 원소의 값을 구해.. 더보기 이전 1 ··· 8 9 10 11 12 13 14 ··· 27 다음