본문 바로가기

알고리즘85

[Swift] 깊이 우선 탐색(DFS)과 간선의 분류 출처: 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략, 구종만 지음, 인사이트 DFS 스패닝 트리 - 어떤 그래프를 DFS했을 때, 탐색이 따라가는 간선들만을 모아 보았을 때의 트리. DFS 스패닝 트리의 모든 간선을 네가지 중 하나로 분류할 수 있습니다. 1. 트리 간선 스패닝 트리에 포함된 간선. 2. 순방향 간선 스패닝 트리의 선조에서 자손으로 연결되지만 트리 간선이 아닌 간선. ex. 그림의 (0, 6) 간선 3. 역방향 간선 스패닝 트리의 자손에서 선조로 연결되는 간선 ex. 그림의 (2, 0) 간선 4. 교차 간선 트리에서 선조와 자손 관계가 아닌 정점들 간에 연결된 간선 ex. 그림의 (6, 3) 간선 +) 무향 그래프 무향 그래프의 모든 간선은 양방향으로 통행 가능하므로 교차 간선이 .. 2022. 7. 27.
[Swift] 프로그래머스 - 카카오 표 편집 링크: https://school.programmers.co.kr/learn/courses/30/lessons/81303 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr Node 클래스를 만들어 풀었습니다. 삭제/삽입은 연결리스트의 방식과 동일합니다. 맨 처음 노드의 prev은 nil이고 맨 마지막 노드의 next는 nil인 것만 조심하면 됩니다. import Foundation class Node { let number: Int var prev: Node? var next: Node? var isRemoved = false init(number: Int,.. 2022. 7. 18.
[Swift] 백준 16113번 시그널 링크: https://www.acmicpc.net/problem/16113 16113번: 시그널 zxcvber는 외계인을 연구하는 과학자다. 그는 지난 10년간 우주에서 오는 시그널를 연구했지만, 아무런 성과가 없었다. 그러던 어느 날, 갑자기 우주에서 이상한 시그널이 오기 시작했다. zxcvber는 www.acmicpc.net 0~9까지의 배열 모습을 numbers 딕셔너리에 저장해놓고 변수 j를 통해 시그널을 돌면서 숫자를 찾습니다. j부터 j + 3까지는 1을 제외한 0~9까지의 숫자가 있을 수 있습니다. 시그널의 맨 마지막에 1이 있을 수 있으니 j + 3 2022. 7. 10.
[Swift] 프로그래머스 - 카카오 기둥과 보 설치 링크: https://programmers.co.kr/learn/courses/30/lessons/60061 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 1. _isRightPillar, _isRightBo, _isRightAll.. 2022. 6. 27.
[Swift] 프로그래머스 - 카카오 괄호 변환 링크: https://programmers.co.kr/learn/courses/30/lessons/60058 코딩테스트 연습 - 괄호 변환 카카오에 신입 개발자로 입사한 "콘"은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 programmers.co.kr 함수 설명 1. splitUV 함수로 균형잡힌 괄호 문자열인 u와 나머지 문자열인 v를 반환합니다. 2. isCorrect 함수로 스택이 아닌 count 변수로 올바른 괄호 문자열인지 반환합니다. '문자열 v에 대해 1단계부터 다시 수행' 이 부분이 solution 함수를 재귀적으로 호출하는 것임을 알면 풀 수 있는 문제입니다. import Foundati.. 2022. 6. 27.
[Swift] 백준 1992번 쿼드트리 링크: https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 백준 2603번 색종의 만들기의 코드에서 파생되었습니다. 풀이: https://gogo-ios.tistory.com/157 색종이 만들기와 다른 점은 0과 1의 갯수를 세는 것이 아닌 String 타입의 결과에 0, 1, 괄호를 추가하는 것입니다. 이 문제의 풀이는 핵심 풀이는 '모두 같은 숫자가 아니라면 1/4씩 쪼개 4번을 더 탐색한다.' 입니다. 1. 전부 같은 숫자인 경.. 2022. 5. 11.

티스토리툴바