본문 바로가기
반응형

분류 전체보기282

백준 1436번 영화감독 숌 - 스위프트(Swift) 풀이 먼저 브루트포스로 가능한 지부터 고려해야 한다. 1, 2, 3... 이렇게 1부터 차례로 666이라는 수를 포함하는지 체크해서 N번째로 666을 포함하는 수를 만나면 출력하고 break 해주면 간단하게 구할 수 있을 것이다. 이 방법이 제한 시간 안에 통과되는지 계산해보자. 일단 N의 최대값이 10,000이다. N = 10,000일 때 답이 몇 일지 예상해야 한다. (예상 못하겠으면 그냥 N=10,000으로 두고 위에 반복문 돌려서 기다려보면 알 수 있긴 하다.) 대충 666이 맨 끝에 오는 경우만 생각해줘 봤는데, 10,000가지가 되려면 채우려면 666 앞에 4자리가 더 붙어야 한다. _ _ _ _ 666 이렇게 되면 각 자리마다 0-9가 들어갈 수 있으니까 10,000가지가 될 것이다. 따라서 N .. 2022. 1. 13.
백준 3770번 대한민국 - C++(cpp) 풀이 + 그림 설명 1615번 문제와 똑같고, 대신 테스트 케이스가 여러 개 주어지는 문제이다. 1615번은 Swift로는 시간 초과가 나서 못 풀었어서 이 문제도 그냥 C++로 도전. 서쪽을 기준으로 작은 수부터 차례로 동쪽과 연결해준다. 1, 2가 연결 완료된 상태이고, 이제 서쪽의 3번에 2개의 고속도로(3-2와 3-5)를 설치해야 하는 상황이라고 하자. 3-2로 가는 고속도로 먼저 설치해야 하는데(이유는 나중에), 이 고속도로를 설치할 때 생기는 교차점의 개수는 동쪽에서 2 초과인 곳 [3, 4, 5]에 연결된 고속도로 개수의 합과 같다. 이미 존재하는(검은색) 고속도로들은 전부 서쪽에서는 3(빨간 선의 시작점)보다 위에 있다. 따라서 방금 설치한 빨간색 고속도로와 교차하려면 동쪽에서는 2(빨간 선의 도착점)보다 아.. 2022. 1. 12.
백준 1572번 중앙값 - 스위프트(Swift) 시간초과 해결 스위프트로 문제 풀면 절반은 TLE를 맞는.. 오늘 벌써 두 번째 TLE인데 이번엔 좀 신기한 상황이었다. 이 문제 바로 전에 1615번 문제에서 이유를 알 수 없는 TLE를 맞았는데, Swift로 맞은 사람이 없길래 포기하고 바로 C++로 풀었는데 이 문제는 Swift로 맞은 사람이 있었다...! 결국 언어 한계가 아니라 내 코드 문제라는 건데.. 코드가 길지도 않은데 대체 어디서 시간을 잡아먹는 건지 알 수가 없었다. 예전에 C++로 풀이할 때, 메모리 접근 시간 때문에 TLE를 맞은 적이 있었다. 로직은 그대로 두고 2차원 배열 행과 열만 바꿔서 저장했더니 통과가 됐었다. 그래서 설마 이것도 메모리 접근에서 시간을 잡아먹는 건가 싶어 클래스 안에 타고 들어가는 시간 줄이려고 클래스로 따로 뺐던 펜윅.. 2022. 1. 12.
백준 1615번 교차개수세기 - 스위프트(Swift) 시간초과 해결 못함 또 TLE가 났는데, 이번엔 해결을 못하겠어서 결국 C++로 제출했다ㅠㅠ 추측하고 있는 이유는 1. 튜플 정렬 때문 2. 지금까진 대부분 N=100,000이었는데 이번엔 200,000이라..? 채점 현황 가서 Swift로 맞은 사람이 있는지 봤는데 제출한 사람조차 없었다. 그래서 빠르게 포기하고 C++로ㅠㅠ 아래는 TLE 받은 Swift 코드 import Foundation class FenwickTree { var tree = Array(repeating: 0, count: 2001) func sum(to: Int) -> Int { var ret = 0 var pos = to while (pos > 0) { ret += tree[pos] pos &= (pos - 1) } return ret } func.. 2022. 1. 12.
백준 1777번 순열복원 - 스위프트(Swift) 풀이 + 그림 설명 1~N에 대해 i보다 뒤에 나오면서 더 작은 수의 개수가 주어졌다. 따라서 큰 수부터 내림차순으로 뒤에 빈자리가 inversionSequence[i]개 있게 되는 곳에 놓으면 된다. 큰 수부터 고려해주고 있기 때문에, 빈자리의 의미는 앞으로 더 작은 수가 위치할 자리이기 때문이다. 먼저 가장 큰 5부터 자리를 찾아주자. 5의 Inversion Count가 2이므로 뒤에 빈자리가 2개가 되는 곳에 놔야 한다. 그림으로 보면 3번째 자리가 되겠다. 그럼 뒤에 빈자리가 x개가 되는 곳을 어떻게 찾을까? 순차 탐색으로 뒤에서부터 하나씩 세면 당연히 O(N^2)으로 시간 초과가 난다. 세그먼트 트리로 시간문제를 해결할 수 있다. 해당 자리가 비어있는지 여부를 배열로 둬서, 맨 뒤에서부터의 index까지의 구간합이.. 2022. 1. 12.
반응형

티스토리툴바