백준 | 9461 파도반 수열 Swift - DP

이전 게시글에서 다이나믹 프로그래밍을 맛볼 수 있었는데, 한 발짝 더 나아가서 효율적으로 풀 수 있는 방법을 고민하는 문제가 여기 있다. 이전 게시글 보러가기 ⬇️ 2023.07.18 - [공부하자!/알고리즘] - 백준 | 9095 1, 2, 3 더하기 Swift - DP 우선, 점화식을 구해보자! 문제에서 P(1)부터 P(10)까지 제공해주었다 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 3 4 5 7 9 그림에서 보면 알 수 있듯이, 11번째 삼각형의 한 변의 길이는 9+3, 즉 P(10)+P(6)인 12이다. 10번째 삼각형의 한 변의 길이는 P(9)+P(5)인 9이다. 즉 점화식을 구하면 다음과 같다 P(n) = P(n-1) + P(n-5) 하지만 이걸 그대로 코드로 구현하면 시간 초과..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 18.
• textsms

백준 | 9095 1, 2, 3 더하기 Swift - DP

다이나믹 프로그래밍이란? 다이나믹 프로그래밍, 동적 계획법이라고 불리는 알고리즘은 하나의 커다란 문제를 작은 문제들로 나누어 값을 구하는 방법이다. 점화식을 구하고 나면 쉽게 풀 수 있지만 이런 사고방식에는 연습이 필요하다. 이 문제에서는 1, 2, 3만을 이용해 숫자를 나타낼 때, 그 경우의 수를 구해야 한다. 작은 것부터 차례대로 생각해보자. n = 1 1 1개 n = 2 1+1 2 2개 n = 3 1+1+1 1+2 2+1 3 4개 n = 4 1+1+1+1 1+1+2 1+2+1 1+3 2+1+1 2+2 3+1 7개 n=1일 때는 1, n=2일 때는 2, n=3일 때는 4 그리고 n=4일 때는 7개의 경우의 수가 나온다. 이 때 n=4를 자세히 살펴보자. 1+3이라는 큰 틀을 구할 때, 오른쪽 피연산자..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 18.
• textsms

LeetCode | 46. Permutations (Medium) - Swift

46. Permutations Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]] Swift로 순열을 구하는 코드를 찾다가 풀게 된 문제! (Swift에서는 순열, 조합을 일일이 구해야 하기 때문에..한 번 제대로 ..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 7. 14.
• textsms

백준 21608 상어 초등학교 Swift - 구현

주변에 좋아하는 학생이 많도록 자리를 배치하는 문제 문제 자체는 이해가 쉬웠다! 그대로 구현하는 게 시간이 걸릴 뿐...🤯 사실 며칠 전에 풀다가 만 코드가 있었는데, 다시 보니까 무슨 소린지 전혀 모르겠어서 처음부터 다시 짰다 ㅋㅋ 정확하게 뭘 짜야 하는지 주석부터 달고 시작했더니 가닥이 쉽게 잡히는 것 같다 let n = Int(readLine()!)! var seats = Array(repeating: Array(repeating: 0, count: n), count: n) // 전체 좌석 만들기 우선 전체 좌석을 만들고 초기화해주었다 그리고 n * n 만큼 for문을 돌면서 한 줄씩 읽었다 한 명의 번호와 그 학생이 좋아하는 학생 번호들이 나열되기 때문에 한 줄을 읽을 때마다 실행해야할 것들이 많..

• format_list_bulleted 공부하자!/알고리즘
• · 2023. 6. 20.
• textsms

백준 2309 일곱 난쟁이 파이썬

문제 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 괜히 조합 combination 이런거 쓰려고 했다가 오히려 망한 케이스.. 그냥 쉽게 생각해서, 9명 중 2명을 제외했을 때 합이 100이면 그걸 출력하면 된다! nlist = [] for _ in range(9): nlist.append(int(input())) num1 = 0 num2 = 0 for i in range(8): for j in range(i+1, 9): if sum(nlist) - (nlist[i] + nlist[j]) == 100: num1 =..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 11. 4.
• textsms

프로그래머스 | 거리두기 확인하기

문제 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr dr = [-1, 1, 0, 0, -1, 1, -1, 1, -2, 2, 0, 0] dc = [0, 0, -1, 1, -1, -1, 1, 1, 0, 0, -2, 2] def solution..

• format_list_bulleted 공부하자!/알고리즘
• · 2021. 9. 10.
• textsms