조이의 개발 성장 다이어리

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/49994 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 틀린 풀이 def solution(dirs): answer = set() # 처음 걸어본 길 --> 중복 제거하기 위해 자료형은 set를 활용 dirs = list(dirs) x, y = 0, 0 for dir in dirs: cur_x, cur_y = x, y if dir == "U": y += 1 elif dir == "L": x -= 1 elif dir == "R": x += ..

1697 - 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 틀린 풀이 from collections import deque import sys input = sys.stdin.readline n, k = map(int, input().rstrip().split()) visited = [0] * 100001 def bfs(): global board global visited q = deque([n]) vis..

문자열/컬렉션 문자열/배열 (튜플도 문법 거의 똑같음) ✅ 배열 슬라이싱 https://dojang.io/mod/page/view.php?id=2208 - list[시작인덱스:끝인덱스:증가폭] 시작인덱스, 증가 폭 생략 시 디폴트는 0 끝 인덱스 -> 끝인덱스 -1 - 시작 인덱스와 끝 인덱스가 같으면 빈 리스트를 반환함 >>> a = [0, 10, 20, 30, 40, 50, 60, 70, 80, 90] >>> a[4:7] # 인덱스 4부터 6까지 요소 3개를 가져옴 [40, 50, 60] >>> a[1:1] # 인덱스 1부터 0까지 잘라서 새 리스트를 만듦 [] >>> a[1:2] # 인덱스 1부터 1까지 잘라서 새 리스트를 만듦 [10] >>> a[4:-1] # 인덱스 4부터 -2까지 요소 5개를 ..

문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 시간초과 코드 import Foundation let input = readLine()!.split(separator:" ").map { Int($0)! } let m = input[0], n = input[1] //m: x / n : y var board:[[Int]] = [] for _ in 0.. DP의 메모이제이션 기법 활용 예를들어 이 경우를 비교해보면 20에서 도착지점까지 가는 ..

백트래킹 문제 풀때 유형별 풀이가 너무 헷갈려서 정리하는 포스팅 1. 단순 순열(순서가 다르면 겹치는게 있어도 다른 케이스로 간주, ab != ba) - 모든 케이스를 다 돌기는 해야하는데, 현재 루프에서 이미 방문한 노드는 제외해야할 때 N과 M (1) 스도쿠 - 1부터 9를 중복없이 채운다는 전제하에 1 9 와 9 1은 다른 케이스일 수 밖에 없음. 여기에 행/열/사각형에 중복이 없는지에 대한 조건 추가하는 응용만 제외하면 아래 원리와 동일 알고리즘 틀 // 구현해놓은 Permutation 연습 func permute(_ nums: [Int], _ targetNum: Int) -> [[Int]] { var result = [[Int]]() var visited = [Bool](repeating: fa..

🥺 이번엔 백트래킹 조지기 https://github.com/tony9402/baekjoon/tree/main/backtracking 해당 링크의 문제들을 도장깨기 하듯? 풀었고 풀이는 주석으로 달아두었습니다. 10971 https://www.acmicpc.net/problem/10971 💡왜 백트래킹인가? 순회에 필요한 비용을 행렬 형태로 주어지는데, 여기서 차례로 탐색하면서 소요되는 비용을 최소화하는 경우의 수가 너~무 많다. 내 풀이 import Foundation let n = Int(readLine()!)! var board:[[Int]] = [] var answer = Int(1e9) var visited = Array(repeating: false, count: n) // "한번 갔떤 도시..

LIS 1. 11053 (가장 긴 증가하는 부분 수열) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 내 풀이 더보기 import Foundation let n = Int(readLine()!)! let arr = readLine()!.split(separator:" ").map { Int($0)! } var dp = Array(repeating:1, count:n..

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 시간초과 풀이 (백트래킹) import Foundation func solution(_ number:String, _ k:Int) -> String { var answer = 0 var visited = Array(repeating: false, count: number.count) var number = number.map { String($0) } func dfs(_ target..

문제 링크 :https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS + 백트래킹 풀이 이 문제가 백트래킹인 근거를 먼저 찾아보자. 1) 순차적으로 알파벳 1개만 바꿔서 target 까지 가야하므로, 단계를 거칠 때마다 가지치기를 통해 경우의 수가 나뉨 2) 경우의 수를 나눌 때 이미 한번 판단한 word는 다시 판단하지 않아야하므로, 방문 여부를 체크할 visited 배열이 필요함 import Foundation func isValidCompa..

문제 https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net https://www.acmicpc.net/problem/22944 22944번: 죽음의 비 가로, 세로 길이가 $N$인 정사각형 격자가 있다. 해당 격자에는 두 곳을 제외한 모든 곳에 체력을 1씩 감소시키는 죽음의 비가 내리고 있다. 죽음의 비가 안내리는 곳은 현재 있는 위치와 안전지 www.acmicpc.net 처음엔 이문제랑 비슷하다 생각했는데 아니었다. 두 유형이 ..