728x90 Python 썸네일형 리스트형 [백준알고리즘] 1300번: K번째 수 -Python [백준알고리즘] 1300번: K번째 수 -Python https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B의 인덱스는 1부터 시작한다. www.acmicpc.net 너무 어려웠다.... 아이디어가 도무지 기억이 안 나서 알고리즘 분류를 봤는데도 도저히 이분 탐색으로 할 수 있는 방법이 생각나지 않았다. 생각한 방법은 너무 시간이 오래 걸리는 것뿐이었다. 그래서 결국 여러 블로그들을 찾아봤다. 다 같은 내용인데 다 이해가 안돼서 아래의 블로그를 집중.. 더보기 [백준알고리즘] 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 .. 더보기 [백준알고리즘] 2352번: 반도체 설계 -Python [백준알고리즘] 2352번: 반도체 설계 -Python https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자. www.acmicpc.net 언뜻 봐서는 O(N^2)의 방식의 풀이도 통과할 줄 알았는데 시간 초과가 발생했다. 이 문제는 LIS문제이다. 가장 긴 증가하는 부분 수열을 만들어야 한다. 여기서는 직접 부분 수열을 출력하는 것이 아닌 길이만 출력하면 되기 때문에 간단한 lower .. 더보기 [백준알고리즘] 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가지 방법을 적용했었기 때문에 시간 초과가 발생했었다. 시간 초과가 발생한 경우에 대해서 더 설명을 하자면, 현재 위치.. 더보기 [백준알고리즘] 2252번: 줄 세우기 -Python [백준알고리즘] 2252번: 줄 세우기 -Python https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net directed graph에서 tree를 만들면 되는 것 같다. 근데 정답비율을 보고 좀 의아했다. 이렇게 쉬운 문제인가..? 아무튼 생각이 안 나서 나는 찾아보고 풀었다. 통과한 코드는 위상 정렬을 사용한 방법이다. 위상 정렬에 대해서는 아래의 글을 참고했다. https:.. 더보기 이전 1 2 3 4 5 6 ··· 22 다음