알고리즘 문제(Swift) 22

프로그래머스 - 기능 개발 (Queue 사용)

https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  아이디어1. 뒤에 있는 기능은 앞에 있는 기능보다 먼저 개발되어도 앞에 있는 기능이 배포될 때 같이 배포된다-> 앞 기능이 무조건 먼저 나간다 (FIFO) -> 큐 사용2. periods: 각 작업이 완료될 때까지 필요한 기간을 나타내는 배열 ex) progresses(작업 진도): [93, 30, 55]speeds(작업 속도): [1, 30, 5]periods(작업 완료까지의 기간): [7, 3, 9]작업 완료까지의 기간을 수식으로 나타내면..

프로그래머스: 가장 먼 노드

school.programmers.co.kr​   아이디어1. 양방향 그래프이므로 각 노드와 연결된 모든 노드를 2차원 배열 형태로 정의 ex) [[],[2, 3], [1, 4, 5] ... ]- 0번 노드는 없으니 비워둠- 1번 노드와 연결된 노드는 2, 3- 2번 노드와 연결된 노드는 1, 4, 5 (양방항 그래프이므로 1번 노드 포함) 2. 1번 노드와 떨어진 거리를 나타내는 배열 생성 (distance) 3. 큐를 생성하여 1번 노드와 연결된 노드를 큐에 넣어줌 - 큐에서 꺼내면서 꺼낸 노드와 연결된 노드를 큐에 넣어줌- 큐에서 꺼냈으면 2. 에서 만든 거리를 나타내는 배열에 거리를 더해줘야 되는데   이전 노드에 1만큼 떨어진 것이므로 튜플 형태로 큐에 넣어야 될듯 (이전 노드, 현재 노드)- ..

프로그래머스 - 프로세스

https://school.programmers.co.kr/learn/courses/30/lessons/42587 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr    간단하게 정리하면실행 대기 큐에 각각 우선순위가 있는 프로세스가 있는데프로세스를 하나 꺼냈을 때, 우선순위가 제일 높지 않다면 다시 큐에 넣고제일 높은 우선순위를 가진다면 실행한다이때, 특정 프로세스가 몇 번째로 실행되는지를 구하는 문제이다가장 먼저 든 생각은큐에서 프로세스를 꺼냈다가 다시 넣는 과정에서 처음 인덱스를 어떻게 구분할까? 라는 생각이 먼저 들었다우선순위가 담긴 배열에서 pop하고 append하는 과정을 거치면 index 번호..

프로그래머스 - 단어변환 (String.Index, Array(String) 시간 복잡도 비교 분석) + BFS

이전 포스트에서는 단어 변환 문제를 DFS와 String.Index 타입을 이용하여 문제를 해결했다이번 포스트에서는 String.Index 타입으로 subscript에 접근했지만 zip과 Array(String)을 이용하는 방법으로 문제를 해결해보고최종적으로 String.Index와 zip, Array(String)을 통한 문자 비교 방법의 시간 복잡도를 비교 분석해보려고 한다 2025.03.19 - [알고리즘 문제(Swift)] - 프로그래머스: 단어 변환(DFS + String.Index) 프로그래머스: 단어 변환(DFS + String.Index)https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육..

프로그래머스: 단어 변환(DFS + String.Index)

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr   한 번에 한 개의 알파벳만 바꿀 수 있고 target으로 변환하는 가장 짧은 변환 과정을 찾는 문제이기 때문에 DFS로 접근했다.전체적인 풀이 방법은 다음과 같다재귀함수를 이용하여 현재 단어(value)가 target과 같다면 종료한다 → DFS의 깊이가 정답 값words 를 순회하면서 현재 단어(value)와 한 글자만 다른 글자를 찾는다한 글자만 다른 단어를 찾았다면, 해당 단어를 value로 두는 재귀함수를 호출한다. 첫 번째 시도(D..

프로그래머스 - 네트워크(43162)

https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  아이디어네트워크는 최대 n개 컴퓨터간 연결을 확인하고 끊어지면 네트워크 개수 + 11번 컴퓨터 큐에 추가큐에서 하나씩 빼면서 해당 컴퓨터에 연결되어 있는 컴퓨터들을 탐색탐색한 컴퓨터는 visited 처리연결되어 있는 컴퓨터를 큐에 추가제외: 자신, 방문했던 컴퓨터, 연결되지 않은 컴퓨터큐가 비면(연결 되어 있는 컴퓨터를 모두 탐색했다면) 네트워크 + 1방문하지 않은 컴퓨터를 찾아 큐에 추가 (모든 컴퓨터를 방문할 때까지 반복)네트워크 개수 반..

2025 프로그래머스 코드챌린지 1차 예선(유연 근무제)

https://school.programmers.co.kr/learn/courses/30/lessons/388351 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 요약자신이 설정한 출근 희망 시간 + 10까지 어플로 출근 희망 시각이 9시 58분이면 10시 8분까지 출근 토, 일은 예외 매일 한 번씩 출근, 모든 시각은 시간에 100을 곱하고 분을 더한 정수로 표현 -> 10시 13분은 1013, 9시 58분은 958 실제로 늦지 않고 출근한 직원이 몇명인지 구하기schedules: 출근 희망 시각을 담은 배열 timelogs: 직원들이 일주일 동안 출근한 시각을 담은 2차원 배열 startday..

알고리즘 문제(Swift) - 프로그래머스: 여행 경로

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr  첫 번째 시도우선, tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미이므로, 출발지에서 갈 수 있는 모든 도착지를 구분하기 위해 딕셔너리로 정의했다ICN에서 출발하여 갈 수 있는 도착지 중 알파벳 순으로 이동하고, 도착한 곳은 removeFirst() 로 딕셔너리의 value에서 제거하므로써 티켓을 사용 처리했다mapValues : 딕셔너리에서 key는 유지하면서 value만 변환하는 함수방문한 곳은 v..

알고리즘 문제(Swift) - 백준 - 1932 (정수 삼각형)

https://www.acmicpc.net/problem/19321. 문제의 재귀적인 구조 파악맨 위부터 아래로 내려오면서 선택된 수의 합의 최대 값을 구하는 문제아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택→ 다음으로 갈 수 있는 곳은 동일한 인덱스 또는 인덱스 + 1 위에서 index = 1을 선택했다면다음 층에서 인덱스 1, 2 선택 가능→ 현재 층의 인덱스 2는 이전 층의 인덱스 1과 인덱스 2에서 선택 받을 수 있음 2. 수식으로 표현f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + score[i]i: 삼각형의 층j: 층 내 모든 수 3. 초기값 처리 (기저 조건)맨 왼쪽에 있는 수에서 f[i - 1][j -..

알고리즘 문제(Swift) - 백준 - 2579 (계단 오르기)

https://www.acmicpc.net/problem/2579  문제의 재귀적인 구조 파악마지막 계단은 무조건 밟아야 됨 → Top - Down 이용계단은 한 칸 또는 두 칸 이동 가능f(i, 1) (연속된 계단이 1개일 때) = max(f(i + 1, 2), f(i + 2, 1)) + score[i]f(i, 2) (연속된 계단이 2개일 때) = f(i + 2, 1) + score[i]연속된 세 개의 계단을 밟으면 안 됨수식으로 표현f(i) = max(f(i - 1), f(i - 2)) + score[i]연속된 계단의 개수 표현초기값 처리 (기저 조건)마지막 계단은 밟아야 되기 때문에, 넘어가는 계단은 Int.min으로 최소값 처리마지막 계단을 밟았을 때 얻었을 수 있는 최대 점수는 score[n] ..