본문 바로가기
반응형

알고리즘207

백준 11054번 가장 긴 바이토닉 부분 수열 - 스위프트(Swift) 풀이 + 그림 설명 1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다. 2. 모든 i에 대해 i번째 원소를 첫 번째로 하는 가장 긴 감소하는 부분 수열의 길이 reverseLIS[i]를 구한다. 3. i번째 원소를 기준으로 좌측은 증가하고 우측은 감소하는 가장 긴 바이토닉 부분 수열의 길이는 LIS[i] + reverseLIS[i] - 1이다. 1. 모든 i에 대해 i번째 원소를 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이 LIS[i]를 구한다. 일단 앞 부분에서는 증가를 해야 되기 때문에 LIS를 구해준다. DP를 사용해서 구하면 저절로 모든 i에 대해 i번째 원소를 마지막으로 하는 LIS 길이를 얻을 수 있다. 2. 모든 i에 대해 i번째 원소를 첫번째로.. 2022. 1. 25.
백준 10993번 별 찍기 - 18 - 스위프트(Swift) 풀이 + 그림 설명 1. N-1 크기의 삼각형을 감싸고 있는 테두리 삼각형을 그린다. 2. 안쪽 중앙에 N-1 크기의 삼각형을 그린다. 3. N이 짝수일 때, 홀수일 때 모양을 구분해준다. 1. N-1 크기의 삼각형을 감싸고 있는 테두리 삼각형을 그린다. 출력 예시를 보고 규칙을 찾아보면, N일 때의 출력은 N-1일 때의 출력 결과를 품고 있는 삼각형이다. N=3일 때를 보면 안에 N=2일 때의 결과를 더 큰 삼각형이 감싸고 있다. 따라서 바깥 테두리 삼각형을 그린 뒤, 적절한 내부 위치를 찾아 재귀적으로 N-1 삼각형을 그리는 함수를 호출하면 된다. 2차원 배열을 선언해주고, 함수 파라미터에 그려야 하는 위치(행, 열)를 넘겨주면 재귀 호출로 내부의 원하는 위치에 그릴 수가 있다. 출력을 보고 규칙을 찾으면, N일 때 테.. 2022. 1. 24.
백준 2448번 별 찍기 - 11 - 스위프트(Swift) 시간초과 해결 못함 시간초과ㅠㅠㅠㅠㅠㅠㅠㅠㅠ k=10일 때 넣어보니까 출력이 진짜 오래 걸리던데 문자열 출력 때문인 것 같다. 여러 방법 다해봤는데 joined() 쓰는 게 그나마 제일 빨랐다. 그래도 한참 느린가 보다. 이 문제는 Swift로 맞은 사람 많던데 어떻게 한 건지 끝까지 못 찾아내서 결국 C++로 제출했다. Swift로 AC 받은 코드 보고 싶다. 진짜 너무 궁금해ㅠㅠ import Foundation var arr = [[String]]() func fillStar(row: Int, col: Int, size: Int) { if size == 3 { arr[row][col+2] = "*" arr[row+1][col+1] = "*"; arr[row+1][col+3] = "*" for i in 0.. 2022. 1. 24.
백준 7511번 소셜 네트워킹 어플리케이션 - 스위프트(Swift) 시간초과 해결 오랜만에 원인모를 TLE가 났다. 심지어 이번에는 100%에서 시간 초과가 났다...! 채점 현황을 보니까 Swift로 맞은 분이 딱 한 분 있었다. 그럼 또 내 코드 문제란 건데..ㅠㅠ 결론은 삼항 연산자를 if-else문으로 고쳐서 AC를 받았다. 여러 가지 실험을 해봤는데 삼항 연산자를 쓰는 것보다 if-else로 하는 것이 아주 조금 더 빨랐다. 이 미세한 차이로 TLE가 AC로 바뀌었다...... PS에서는 삼항 연산자도 맘대로 못쓰다니 아래는 실험해본 코드 import Foundation func check(_ n: Int) -> Bool { return n % 2 == 0 } // 삼항연산자 let start = CFAbsoluteTimeGetCurrent() var resultString .. 2022. 1. 24.
백준 1043번 거짓말 - 스위프트(Swift) 풀이 1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다. 2. 진실을 아는 사람들을 한 집합으로 묶는다. 3. 각 파티의 참석자들이 진실을 알아야 하는 집단인지 체크한다. 1. 같은 파티에 참석하는 사람들끼리는 같은 종류(진실/거짓)를 들어야 하므로 한 집합으로 묶는다. 같은 종류를 들어야 하는 사람들을 한 집합으로 묶어 취급할 것이다. Union-Find 알고리즘을 사용해서 구현하면 된다. 같은 파티에 참석하는 사람들은 무조건 같은 종류를 들어야 한다. 따라서 한 파티 내의 참석자들을 한 집합으로 묶는다. 2. 진실을 아는 사람들을 한 집합으로 묶는다. 이제 진실을 아는 사람들도 모두 진실을 들어야 하므로 한 집합으로 묶어준다. 이렇게 되면 만약 파티 참석자 .. 2022. 1. 24.
반응형

티스토리툴바