본문 바로가기

728x90

분류 전체보기

[백준알고리즘] 1525번: 퍼즐 -Python [백준알고리즘] 1525번: 퍼즐 -Python https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 보다시피 시간제한과 메모리 제한이 심한 문제이다. 처음 보고는 문제를 어떻게 풀어야 하나 캄캄했다... 일반적인 BFS방식으로는 불가능할 것 같고, 방문 유무를 체크해줌으로써 중복을 제거해야 하는데, 3x3크기의 배열을 어떻게 전체적인 모양을 가지고 방문 여부를 표시할 수 있을까 고민했다. 결국에 질문 게시판들을 보고 깨우치게 되었다. 조금만 더 쫄지않고 생각해봤으면 나왔을 수도 있지 않았을까 하는 아쉬움이 있다. 질문 게시판.. 더보기
[백준알고리즘] 9019번: DSLR -Python [백준알고리즘] 9019번: DSLR -Python https://www.acmicpc.net/problem/9019 9019번: DSLR 문제 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자) D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경 www.acmicpc.net 이번 문제도 주어진 두 값 A, B 간의 제시된 4가지 이동 방법에 따라 만날 수 있.. 더보기
[백준알고리즘] 1963번: 소수 경로 -Python [백준알고리즘] 1963번: 소수 경로 -Python https://www.acmicpc.net/problem/1963 더보기
[백준알고리즘] 1697번: 숨바꼭질 -Python [백준알고리즘] 1697번: 숨바꼭질 -Python https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 www.acmicpc.net 처음에 이번 문제를 DFS 방식으로 풀으려 했다. 백트래킹으로 여러 조건들을 추가해서 .. 더보기
[백준알고리즘] 10971번: 외판원 순회 2 -Python [백준알고리즘] 10971번: 외판원 순회 2 -Python https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 두 가지 방법으로 문제를 풀었다. 첫 번째 방법은 처음에 푼 방식으로 말 그대로 완전 탐색을 위해서 모든 경우를 탐색하도록 했고, 두 번째 방법은 찾아보니 다들 비트 마스크를 이용해서 문제를 풀었길래 공부해서 다시 .. 더보기
[백준알고리즘] 1451번: 직사각형으로 나누기 -Python [백준알고리즘] 1451번: 직사각형으로 나누기 -Python https://www.acmicpc.net/problem/1451 1451번: 직사각형으로 나누기 첫째 줄에 직사각형의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 직사각형에 들어가는 수가 가장 윗 줄부터 한 줄에 하나씩 M개의 수가 주어진다. N과 M은 100보다 작거나 같은 자연수이고, 직사각형엔 적어도 3개의 수가 있다. 또, 직사각형에 들어가는 수는 한 자리의 숫자이다. www.acmicpc.net 브루트 포스 방식으로 해결을 해야 한다. 애를 많이 먹고 다른 분들의 풀이를 살펴본 후 해결했다. 처음에 풀었던 방식으로는 각 테이블을 그룹 1, 2, 3으로 직접 나누었다. 이중 for문을 돌려가며 시작점을 설정하고, 그룹이 시.. 더보기
[백준알고리즘] 1107번: 리모컨 -Python [백준알고리즘] 1107번: 리모컨 -Python https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 브루트 포스로 해결해야 하는 건지 모르고 이상하게 풀었었다... 조건을 다 맞추려고 하다 보니 오류가 계속 발생하고 통과가 안 되는 반례가 계속 존재했다. 이 문제의 경우에는 MAX가 500000으로 depth도 얕기 때문에 recursion depth도 6으로 낮고, 0~9.. 더보기
[백준알고리즘] 1744번: 수 묶기 -Python [백준알고리즘] 1744번: 수 묶기 -Python https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 상관없이 묶을 수 있다. 하지만, 같은 위치에 있는 수(자기 자신)를 묶는 것은 불가능하다. 그리고 어떤 수를 묶게 되면, 수열의 합을 구할 때 묶은 수는 서로 곱한 후에 더한다. 예를 들면, 어떤 수열이 {0, 1, 2, 4, 3, 5}일 때, 그냥 이 수열 www.acmicpc.net 주어진 조건은 아래와 같다. 수열에서 임의의 두 수를 곱할 수 있다. 한 번 묶여서 .. 더보기

728x90