Swift) 백준 5430번 AC - G5

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 전형적인 구현 문제. removeFirst()같은 배열 관련 내장 함수를 사용하면 시간초과가 뜨기에 다른 방식으로 구현해야 했고 명령어의 수 + 수열의 길이의 합이 70만이 최댓값 이였길래 여러 최적화가 필요했다. 기본적으로는 투포인터 알고리즘을 사용했다. 풀이 함수 P의 길이라 10만 이하이므로 만약 함수를 일일히 다 실행하면 시간초과가 뜸. 따라서 연속되는 명령어들을 묶는 방식으로 처리. RRDDDDRD라는 함수가 입력되었을 때, 이를 RR, DDD..

• format_list_bulleted Algorithm/백준
• · 2023. 6. 7.
• textsms

조합, 순열 알고리즘

완전탐색, 부르트포스, 구현등의 유형에서 많이 나오는 알고리즘. 중요하니까 정리해보자. 조합 중복을 허용하지 않음. 123이나 231이나 321은 다 똑같음. 조합은 dfs로 구현하거나 이진법 또는 점화식을 이용하여 구현할 수 있음. dfs로 n개의 숫자에 대해 r개로 이루어진 조합을 구하는 코드는 let n = [1,2,3,4,5] let r = 3 var comb: [Int] = Array(repeating:0 ,count:r) func dfs(depth: Int, beginWith: Int) { if depth == r { print(comb) return } for i in beginWith..

• format_list_bulleted Algorithm
• · 2023. 6. 6.
• textsms

Swift) 백준 2468번 안전영역 - S1

https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 전형적인 경로 탐색 문제. 접근 방식은 for문으로 비의 높이가 지역의 높이보다 낮다면 해당 지역을 시작점으로 계속해서 탐색하고, 만약 더 탐색할 수 없다면 다음 시작점으로 이동해서 이어진 경로를 계속해서 탐색한다. 이때 BFS를 이용해서 문제를 풀었다. visited를 통해 비의 높이에 따라 방문 했는지 체크해서 푸는 방식을 택했다. 다른 사람 풀이를 보니 DFS를 이용해 푼 사람도 있던데 문제의 요점..

• format_list_bulleted Algorithm/백준
• · 2023. 6. 6.
• textsms

Swift) 백준 14500번 테트로미노 - G4

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 배열 + 최대의 합을 구하라는 시점에 완전 탐색을 써야한다는건 알았지만, 테트로미노를 어떤식으로 해야 할지 많이 고민했던 문제. 테트로미노의 모양을 모두 시작점을 기준으로 하드코딩 해서 하는 방법도 생각했지만... 그런식으로는 풀기 싫어서 다른 방법을 생각했다. 테트로미노의 모양은 ㅗ 모양을 제외하고 모두 DFS로 정의 할 수 있음. 따라서 시작점을 기준으로 dfs로 경로값을 계산 후 ㅗ 모양은 ..

• format_list_bulleted Algorithm/백준
• · 2023. 6. 5.
• textsms

Swift) 백준 2504번 괄호의 값 - S1

https://www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 X www.acmicpc.net 접근 방식 : 스택을 이용하여 접근. (X) 와 [X]는 X의 값에다가 2또는 3을 곱한 값이고 ()와 []는 2와 3을 반환한다. ()와 [] 내부에 아무것도 들어 있지 않지만 1이 들어 있다고 가정하면 결국 X값이 들어있는 괄호나 X가 들어있지 않는 값이나 계산방식은 똑같은 점을 이용해 풀었다. 풀이 과정: 인풋값은 "(([]()))"가 들어간다고 가정. 괄호가 시작되는 경우 괄호스택에 ..

• format_list_bulleted Algorithm/백준
• · 2023. 6. 5.
• textsms

Swift) 백준 17619번 개구리점프 - G3

https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 < x2) 모든 www.acmicpc.net 처음 이 문제를 봤을때 프로그래머스의 요격 시스템 문제와 비슷하다고 생각했으나 다른 방식으로 접근 해야했다. 문제의 요점은 A통나무에서 B 통나무로 이동이 가능한를 판단하는 것 만약 통나무 A → D로 이동이 가능하다면 그 중간에 있는 서로 이동 가능한 통나무들끼리는 이동이 가능하다. A → D로 이동 할 때, A → B, B→D or A→B, B→C, ..

• format_list_bulleted Algorithm/백준
• · 2023. 6. 4.
• textsms