코딩하는 해맑은 거북이

해당 글은 백준 1347번 문제 '미로 만들기'을 다룬다. 문제 https://www.acmicpc.net/problem/1347 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 설명 홍준이가 적은 내용의 길이는 0보다 크고 50보다 작다. 그리고 모든 행과 열에 적어도 하나 이동할 수 있는 칸이 있다. 그러므로 행으로 최대 50칸, 열로도 최대 50칸 갈 수 있다. 그래서 임의의 지도를 100x100 생성한 후, 시작지점의 좌표를 50, 50으로 설정한 후 이동하면 된다. 그리고 이동한 최대 x, 최대 y..

해당 글은 백준 18870번 문제 '좌표 압축'을 다룬다. 문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 설명 해당 문제는 입력받은 좌표를 중복을 제거한 후, 오름차순으로 정렬한 인덱스 값을 반환하면 된다. 이때 리스트의 index 함수를 사용하면 시간초과가 뜨므로 딕셔너리 자료구조를 이용하면 쉽게 해결할 수 있다. 코드 n = int(input()) arr = list(map(int, ..

해당 글은 백준 11052번 문제 '카드 구매하기'를 다룬다. 문제 https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 설명 해당 문제는 처음엔 백트래킹으로 풀었을 때 시간초과가 떴다. 그래서 더 쉽게 해결할 수 있는 방법으로 동적 계획법이 떠올랐다. 만약 3개의 카드를 산다고 했을 때는 (2개가 든 카드 + 1개가 든 카드) or (1개가 든 카드 + 2개가 든 카드) or (3개가 든 카드)의 3가지 중 최대값을 계산할 수 있다. 즉, 점화식은 아래와..

해당 글은 아래의 2가지를 다룬다. 1. 순열(Permutation) 2. 조합(Combination) 1. 순열(Permutation) : nPr : 서로 다른 n개에서 r개를 뽑아 순서를 정해서 일렬로 나열하는 것. from itertools import permutations perm = list(permutations('n개 원소를 갖는 리스트', r)) from itertools import permutations data = [1, 2, 3, 4] perm = list(permutations(data, 2)) print(perm) perm = list(permutations(data, 3)) print(perm) [(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, ..

해당 글은 백준 14889번 문제 '스타트와 링크'를 다룬다. 문제 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 설명 해당 문제는 itertools 모듈의 combinations 함수를 통해 완전 탐색으로 풀었을 때는 시간초과가 떴다. 인터넷의 도움으로 알아본 결과 백트래킹(DFS)로 풀어야 완전 탐색보다 훨씬 빨리 해결할 수 있다고 한다. 한 팀이 n//2로 구성되면, 나머지 팀은 자동으로 구성된다. 이를 이용해서 두 팀으로 나눌 수 있다. - 완전탐색 : 모..

해당 글은 프로그래머스 Level3 문제 '거스름돈'을 다룬다. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/12907 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 설명 다이나믹 프로그래밍 알고리즘으로 풀 수 있는 문제이다. 거스름돈 금액을 동전의 숫자만큼 계속해서 누적해서 경우의 수를 구하고 n번째 dp값을 반환해주면 된다. 코드 def solution(n, money): dp = [0]*(n+1) dp[0] = 1 for coin in money: for price in range(co..