탈출경로를 문자열로 나타넀을 때, 사전 순으로 가장 빠른 경로 반환 (d : 아래 1칸, l: 왼쪽 1칸, r: 오른쪽 1칸, u: 위로 1칸)
미로탈출 경로를 반환하되, 탈출 못하면 ‘impossible’반환
입력
2 ≤ n ≤ 50
2 ≤ m ≤ 50
1 ≤ x ≤ n
1 ≤ y ≤ m
(x, y) ≠ (r, c)
1≤ k ≤ 5^2*10^2
출력
return str
어떻게 풀까?
시간복잡도 : 최대 50x50 크기의 격자이고 한 칸 당 최대 4방향으로 이동이 가능하며, k의 최대 값도 5^2*10^2인데다, 여러 경로가 나올 수 있고 그 중에서 사전 순으로 가장 빠른 경로를 반환해야함 ⇒ 단순 BFS로 모든 경우를 산출한 뒤 그 중에서 사전 순으로 가장 빠른 답 반환하면 시간초과 발생
사전 순으로 가장 빠르다 ⇒ 매번 결정마다 가장 빠른 경로를 큐의 가장 앞에 넣어서 최단경로를 도출 필요 ⇒ 다익스트라 활용 가능
다익스트라를 활용하더라도, 이 문제의 경우 최단거리가 아닌 k 번 이내 방문에 대한 경로를 도출해내야하고 같은 격자를 여러번 방문할 수 있기 때문에, 이러한 조건들에 대해 별도 처리를 해줌으로써 최대한 시간복잡도를 다익스트라의 시간복잡도에 가깝도록 조치해줄 필요가 있음 - 도착지점에 도착했을 때, 남은 이동가능 횟수가 2의 배수여야함(갔다 돌아오기 (예: d→u, l→r등)) - 다음 지점을 탐색할 때, 해당 지점과 도착지점의 거리가 k보다 크면 어차피 탈출 불가능한 경로임(모두 거리가 1칸이기 때문에 지점 간 거리가 이동거리와 동일함)
내 코드
import heapq
def solution(n, m, x, y, r, c, k):
q = []
dr = ['d', 'l', 'r', 'u']
dx = [1, 0, 0, -1]
dy = [0, -1, 1, 0]
heapq.heappush(q, ('', x, y))
while q:
path, x, y = heapq.heappop(q)
if x == r and y == c:
if len(path) == k:
return path
elif (k - len(path)) % 2:
return 'impossible'
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if next_x <= 0 or next_x > n or next_y <= 0 or next_y > m:
continue
if abs(next_x - r) + abs(next_y - c) + len(path) > k:
continue
heapq.heappush(q, (path+dr[i], next_x, next_y))
return 'impossible'
총 지역 수 n, 두 지역 왕복길 정보 roads, 각 부대원 위치 정보 sources, 지역 destination → sources 순서대로 복귀 가능한 최단 시간 배열을 구하고 복귀가 불가능하면 -1로 표기하라
입력
3≤ n ≤ 10^5
(각 지역 : 정수 1부터 n까지 번호로 구분)
2≤roads [[a,b], …] 2차원 배열 ≤ 5*10^5
([a,b] : a, b가 왕복가능)
1≤sources≤5*10^2
1≤destination≤n
출력
return int[]
어떻게 풀까?
다른 지역에 있는 부대원들이 모두 부대가 있는 한 지역으로 최단 시간 내에 가야함 ⇒ 거꾸로 생각해보면, 한 지점에서 모든 지점으로 가야함 ⇒ 다익스트라 문제 ⇒ 다익스트라의 시간복잡도는 O(nlogn)이므로 가능
다익스트라로 모든 지역에서 부대 복귀하는 최단distance 구한 뒤, sources를 돌아가면서 해당하는 distance 값을 answer 배열에 넣기 (단, 무한대(불가능)일 경우, -1 넣기)
지역번호는 1부터 n인 점 유의!
내 코드
import heapq
def solution(n, roads, sources, destination):
answer = []
INF = int(1e9)
graph = [[] for _ in range(n + 1)]
for road in roads:
a, b = road
graph[a].append(b)
graph[b].append(a)
distance = [INF]*(n+1)
distance[destination] = 0
q = []
heapq.heappush(q, (0, destination))
while q:
dist, now = heapq.heappop(q)
if dist > distance[now]:
continue
if not graph[now]:
continue
for next in graph[now]:
cost = dist + 1
if cost < distance[next]:
distance[next] = cost
heapq.heappush(q, (cost, next))
for region in sources:
if distance[region] == INF:
answer.append(-1)
else:
answer.append(distance[region])
return answer
칸토어 집합이란, [0,1] 부터 시작해서 각 구간을 3등분 한 후에 가운데 구간을 반복적으로 제외하는 방식
다음과 같이 유사칸토어 비트열을 생성함
0 번째 유사칸토어 비트열 : 1
n 번째 유사칸토어 비트열 : n-1 번째 비트열에서 1을 ‘11011’로 치환하고 0을 ‘00000’로 치환
n 번째 유사칸토어 비트열에서 특정 구간 내의 1의 개수가 몇개인지 return하라
입력
1≤ n ≤ 20
1≤ l, r ≤ 5^n
l ≤ r < l + 10^7
ㅣ과 r은 비트열에서 인덱스(1-base)이며, 폐구간 [l, r]을 나타냄
출력
return int
어떻게 풀까?
주의할 점 : l, r 이 1로 시작하는 인덱스이며 l과 r을 포함하는 구간으로 구해야 함
1≤ l, r ≤ 5^n 및 l ≤ r < l + 10^7 조건으로 인하여, 시간복잡도를 고려한 알고리즘 구현 필요
칸토어 집합 자체가 규칙이 있음 ⇒ 손으로 풀어보며 규칙을 찾아보자
⇒ 길이에 따라서 일정한 유사성을 가진 비트열이 생성되고 길이에 따라서 4의 배수로 1의 개수를 구할 수 있음
⇒ r-1번(index-0)까지의 1의 개수에서 l-2번(index-0)까지 1의 개수를 제외해주면 될 것
⇒ 이 때, 1의 개수는 해당 길이를 통해서 n번째 비트열에 속하는 지를 구한 후에 n-1번째 비트열의 길이로 그룹을 구하고 그 그룹의 개수만큼 4의 n-1승을 활용하여 구하면 됨
(단, 그룹의 수가 3개 이상일 때는 0이 5^(n-1)개 있는 그룹이 3번째 구간에 있으므로 그만큼을 제외해주어야함)
나머지의 경우, 재귀를 활용하여 처리
⇒ 현재, n을 5로 나누어주는 것으로 계속 진행을 하고 있기 때문에, 재귀의 종료조건은 n이 5이하가 될 때로 설정
(이 때는, '11011’[:길이]에서의 1의 개수를 반환하면 될 것)
내 코드
def get_power_of_base5(num):
power = 1
while 5**(power+1) < num:
power += 1
return power
def get_1_cnt(num):
res = 0
if num <= 5:
return '11011'[:num].count('1')
power = get_power_of_base5(num)
group = num // (5 ** power)
res += group*(4** power)
if group == 2:
return res
elif group >= 3:
res -= 4 ** power
remain = num % (5 ** power)
if remain:
return res + get_1_cnt(remain)
return res
def solution(n, l, r):
return get_1_cnt(r) - get_1_cnt(l-1)
어려웠던 점
처음에 시간복잡도를 미처 고려하지 못한 탓에 아래와 같은 코드를 작성하였고 시간초과 오류가 발생하였다.
def solution(n, l, r):
ans = 0
r -=1
l -=1
memo = []
memo.append('1')
for i in range(1, n+1):
memo.append(memo[i-1]*2+'0'*5**(i-1)+memo[i-1]*2)
r_group = (r//5**(n-1))
if r_group <= 2 :
ans += r_group*(4**(n-1))
else:
ans += (r_group-1)*(4**(n-1))
for i in range(r_group*(5**(n-1)), r+1):
if memo[n][i] == '1':
ans += 1
l_group = ((l//5**(n-1)))
if l_group <= 2:
ans -= l_group*(4**(n-1))
else:
ans -= (l_group-1)*(4**(n-1))
for i in range(l_group*(5**(n-1)), l):
if memo[n][i] == '1':
ans -= 1
return ans
답을 찾는 데, n번째라는 인자값은 굳이 필요하지 않았다. 오히려 이 n번째 인자값을 어떻게 사용할지 고민하는 과정이 혼란을 주었던 것 같다. 주어지는 모든 인자들이 문제 해결에 필요하지 않을 수 있다는 점을 명심하자.
재귀함수를 사용할 때, num이 1이 되는 조건을 처음에 걸었었는데 함수 내부에서 num을 5로 나누어 진행을 하다보니 이 조건으로 인하여 무한재귀가 발생하였다. 인자값을 어떻게 처리하는 지 잘 확인하고 해당 처리를 거치지 못하는 값에 대해서 종료조건이나 예외처리를 해주어야할 것이다.
처음에 group 개수에 대한 1의 개수를 res에 반영함에 있어서 아래와 같이 처리하여 group이 1개이고 나머지가 있을 때를 제대로 처리하지 못했다.
def get_1_cnt(num):
...(중략)...
if group <= 2:
return group*(4** power)
elif group >= 3:
res -= 4 ** power
if remain:
return res + get_1_cnt(remain)
return res
전체적으로 처리를 한 후에, 일부 예외사항을 반영하는 아래와 같은 방식으로 변경하였다.
def get_1_cnt(num):
...(중략)...
res += group*(4** power)
if group == 2:
return res
elif group >= 3:
res -= 4 ** power
if remain:
return res + get_1_cnt(remain)
return res
⇒ 각 자리수 별로 0에 가까운지 10에 가까운지 구분해서 10-n/n 값 중 작은 것을 카운팅해주면 될 것!
⇒ 1의 자리에서 가장 높은 단위까지로 반복문으로 수행(10^8이지만, 9자리이므로 충분)
이 때, 10에 가깝다면 윗 자리 값에 +1을 해주기
⇒ 아래 단위에서 버튼 한 번 누르나, 윗 단위에서 한 번 누르나 버튼 누른 횟수 카운팅은 동일
⇒ 가장 높은 자리의 경우, 별도 처리 필요(10에 가깝다면 10-n을 카운팅 해주고 그 값이 올림이 되었을 때를 고려하여 +1을 추가 카운팅해주기)
단, 0이나 10에 대하여 동일하게 가까운 5의 경우는 별도 고려 필요할 것!
⇒ 이 때에는 윗자리가 5이상인지 조건을 걸어, 5이상이면 올려주고 미만이면 내려주는 방식으로 처리 필요
내 코드
def solution(storey):
storey_list = list(map(int, str(storey)))
ans = 0
for i in range(len(storey_list)-1, -1, -1):
if 10 - storey_list[i] > storey_list[i]:
ans += storey_list[i]
elif storey_list[i] == 5:
ans += 5
if storey_list[i-1] >= 5:
storey_list[i-1] += 1
else:
ans += 10 - storey_list[i]
if i == 0:
ans += 1
else:
storey_list[i-1] += 1
return ans
네트워크 패널은 자원들이 제대로 다운로드 되었는지의 여부, 캐시여부, 그리고 다운로드된 자원들의 다운로드에 걸린 시간, 세부 정보들을 보고 싶을 때 유용하게 사용할 수 있는 패널임
리소스가 실제로 업로드 또는 다운로드되고 있는지 확인
HTTP 헤더, 콘텐츠, 크기 등과 같은 개별 리소스의 속성을 검사
네트워크 활동과 관련이 없는 많은 유형의 로드 성능 문제가 있기 때문에, Lighthouse나 Performance패널을 활용하자
페이지를 더 빠르게 로드하는 방법은 Lighthouse를 참조하자.
성능패널의 런타임 성능은 페이지 로드 중이 아닌 실행 중일 때 성능
참고로 성능분석을 실시할 때는 시크릿 모드에서 수행하는 것이 좋음 (시크릿 모드는 Chrome이 깨끗한 상태로 실행되도록 함. 예를 들어 많은 확장 프로그램이 설치된 경우 해당 확장 프로그램으로 인해 성능 측정에 노이즈가 발생할 수 있음)
Performance 패널
페이지가 로드되는 것이 아니라 실행되는 동안 페이지의 성능을 분석하려는 경우 런타임 성능을 기록함
모바일 CPU 시뮬레이션
모바일 장치는 데스크톱 및 랩톱보다 CPU 성능이 훨씬 낮음
페이지를 프로파일링할 때마다 CPU 스로틀링을 사용하여 모바일 장치에서 페이지가 수행되는 방식을 시뮬레이션해보자.
DevTools에서 성능 탭을 클릭
Screenshots 체크박스가 활성화 되어 있는지 확인
Capture Settings을 클릭 합니다
CPU 의 경우 2x slowdown 을 선택(DevTools는 CPU를 평소보다 2배 느리게 조절)참고 : 다른 페이지를 테스트할 때 저사양 휴대기기에서 제대로 작동하는지 확인하려면 CPU Throttling을 20x slowdown 으로 설정
성능 분석 하는 방법
성능 분석은 웹 페이지가 동작하고 있을 때 자동으로 되는 것이 아니라 특정 구간을 녹화한 후 그 구간을 분석해서 수행하는 식으로 이루어짐
초기 렌더링 성능을 분석하고 싶다면 웹페이지를 불러오기 전에 녹화 버튼을 누르거나 새로고침 버튼을 누르면 됨
1. DevTools에서 Record를 클릭 → DevTools는 페이지가 실행될 때 성능 메트릭을 캡처
2. 몇 초만 기다려보자.
3. 중지 를 클릭 → DevTools는 기록을 중지하고 데이터를 처리한 다음 성능 패널에 결과를 표시
분석결과의 의미
초당 프레임 분석
모든 애니메이션의 성능을 측정하는 주요 메트릭은 초당 프레임 수(FPS) : 사용자는 주로 애니메이션이 60FPS로 실행될 때 만족함
1. FPS 차트에서 FPS 위에 빨간색 막대가 표시될 때마다 프레임 속도가 너무 낮아져 사용자 경험에 해를 끼칠 수 있음을 의미하고 일반적으로 녹색 막대가 높을수록 FPS가 높음
그림 1 파란색 윤곽선으로 표시된 FPS 차트
2. FPS 차트 아래 에 CPU 차트가 표시됨. CPU 차트의 색상은 성능 패널 하단에 있는 요약 탭의 색상에 해당 CPU 차트가 색상으로 가득 하다는 사실 은 기록 중에 CPU가 최대로 사용되었음을 의미함 → 오랜 기간 동안 CPU가 최대치에 도달한 것을 볼 때마다 작업을 덜 수행할 수 있는 방법을 찾아야 한다는 신호임
그림 2 파란색 윤곽선으로 표시된 CPU 차트 및 요약 탭
3. FPS , CPU 또는 NET 차트 위로 마우스를 가져가면, DevTools는 해당 시점의 페이지 스크린샷을 보여줌 녹화를 재생하려면 마우스를 좌우로 움직여보자 → 이를 스크러빙이라고 하며 애니메이션 진행을 수동으로 분석하는 데 유용함
그림 3 기록의 2000ms 표시 부근의 페이지 스크린샷 보기
4. 프레임 섹션 에서 녹색 사각형 중 하나 위로 마우스를 가져가면, DevTools는 특정 프레임에 대한 FPS를 보여줌(각 프레임은 아마도 목표인 60FPS보다 훨씬 낮을 것)
그림 4 프레임 위에 마우스 올리기
병목 현상 찾기
애니메이션이 제대로 작동하지 않는다는 것을 측정하고 확인했다면, 이유를 찾아야한다.
1. 요약 탭을 확인해보자. 이벤트를 선택하지 않으면 이 탭에 활동 내역이 표시됨 페이지는 대부분의 시간을 렌더링하는 데 사용했다.
성능은 작업을 적게 하는 기술이므로 렌더링 작업에 소요되는 시간을 줄이는 것이 목표임
그림 1 요약 탭(파란색 윤곽선)
2. 기본 섹션을 확장해보자. DevTools는 시간 경과에 따른 기본 스레드 활동의 화염 차트를 보여준다.
x축은 시간 경과에 따른 기록을 나타내고 각 막대는 이벤트를 나타냄 → 넓은 막대는 이벤트가 더 오래 걸렸음을 의미
y축은 호출 스택을 나타냄 → 이벤트가 서로 쌓여 있는 것을 보면 상위 이벤트가 하위 이벤트의 원인이 되었음을 의미
그림 2 파란색 외곽선으로 표시된 메인 섹션
3. 기록에 많은 데이터가 있다. FPS , CPU 및 NET 차트 가 포함된 섹션인 개요 위로 마우스를 클릭한 상태로 드래그하여 단일 애니메이션 프레임 실행 이벤트를 확대해보자. → 기본 섹션 및 요약 탭 에는 선택한 녹음 부분에 대한 정보만 표시됨
그림 3 단일 Animation Frame Fired 이벤트 확대
(참고 : 확대/축소하는 또 다른 방법 은 배경을 클릭하거나 이벤트를 선택하여 메인 섹션에 초점을 맞춘 다음 W, A, S 및 D 키를 누르는 것)
5. Animation Frame Fired 이벤트를 클릭해보자 이제 요약 탭에 해당 이벤트에 대한 정보가 표시된다. → 클릭하면 DevTools가 Animation Frame Fired 이벤트 를 시작한 이벤트를 강조표시함
또한 app.js:94 링크를 클릭하면 소스 코드의 관련 줄로 이동함
그리고 원형 차트가 위치했던 summary 탭이 갱신되면 'reveal' 이라 표시된 링크가 생기고 이 링크를 클릭하면 이를 통해 정확히 어느 위치의 어떤 코드가 해당 이벤트를 발생시키는지를 추적할 수 있음
그림 4 Animation Frame Fired 이벤트에 대한 추가 정보
(참고 : 이벤트를 선택한 후 화살표 키를 사용하여 옆에 있는 이벤트를 선택)
6. app.update 이벤트 아래에는 많은 보라색 이벤트가 있을 수 있는데(더 넓으면 각각 빨간색 삼각형이 있는 것처럼 보임), 보라색 레이아웃 이벤트 중 하나를 지금 클릭해보자.
DevTools는 요약 탭 에서 이벤트에 대한 자세한 정보를 제공함.
실제로 강제 리플로우(레이아웃의 또 다른 단어)에 대한 경고가 있음.
7. Summary 탭 에서 Layout Forced 아래의 app.js:70 링크를 클릭해보자. → DevTools는 레이아웃을 강제로 적용한 코드 줄로 이동함
그림 5 강제 레이아웃을 유발한 코드 라인
참고 : 이 코드의 문제점은 각 애니메이션 프레임에서 각 사각형의 스타일을 변경한 다음 페이지에서 각 사각형의 위치를 쿼리한다는 것임. 스타일이 변경되었기 때문에 브라우저는 각 사각형의 위치가 변경되었는지 알지 못하므로 위치를 계산하기 위해 사각형을 다시 배치해야 함.(참조 : 강제 동기 레이아웃 방지)
성능을 이해하기 위한 Rail 모델
RAIL은 성능에 대해 생각할 수 있는 구조를 제공하는 사용자 중심 의 성능 모델임
이 모델은 사용자 경험을 주요 작업(예: 탭, 스크롤, 로드)으로 분류하고 각각에 대한 성능 목표를 정의하는 데 도움을 줌
RAIL은 웹 앱 수명 주기의 4가지 뚜렷한 측면인 응답(response), 애니메이션(animation), 유휴 상태(idle) 및 로드(load)를 나타내고 사용자는 이러한 각 컨텍스트에 대해 서로 다른 성능 기대치를 가지고 있으므로 컨텍스트 및 사용자가 지연을 인식하는 방식에 대한 UX 연구를 기반으로 성능 목표가 정의됨
성능 : 대화형 시간, 대기 시간, 속도 지수, 리소스 최적화, TTFB, 자산 전달, 스크립트 실행 시간, DOM 크기 등
SEO : 모바일 친화적, 메타, 크롤링, 표준, 구조 등
모범사례 : 이미지 최적화, JS 라이브러리, 브라우저 오류 로깅, HTTPS를 통한 액세스, 알려진 JS 취약점 등
접근성 : 페이지 요소, 언어, ARIA 속성 등
PWA : HTTP를 HTTPS로 리디렉션, 응답 코드 확인, 3G에서의 빠른 로딩, 스플래시 화면, 뷰포트 등
왜 Lighthouse를 써야하나?
사용하기가 편하다.
Google에서 개발했다는 점에서 신뢰도가 있다.
오픈소스이다.
완전히 자동화되어 있다.
스캔한 웹 페이지가 모바일 장치에서 어떻게 보이고 작동하는지도 테스트한다.
어떻게 쓸까?
Chrome 개발자 도구
이것이 이 문서의 메트릭에 대한 스크린샷을 만든 방법입니다.:
감사할 페이지로 이동합니다.
DevTools(Windows에서는 Ctrl+Shift+I 또는 F12, Mac에서는 Cmd+Option+I)를 엽니다.
감사 탭으로 이동합니다.
감사 수행을
클릭 하고 원하는 범주를 선택합니다.
감사를 실행합니다.
이는 사용자 인증이 필요한 페이지를 테스트할 때 특히 유용할 수 있습니다.
여기서 흥미로운 점은 Lighthouse 를 Google Chrome 뿐만 아니라 일부 Chromium 기반 브라우저에서도 사용할 수 있다는 것입니다. 예를 들어, 아래는 현재 Google Chrome과 동일한 엔진을 사용하는 최신 버전의 Microsoft Edge에서 가져온 Lighthouse 감사의 스크린샷입니다.
Microsoft Edge 브라우저에서 시작된 Google Lighthouse 감사의 스크린샷.
Lighthouse를 노드 모듈로 실행
이렇게 하면 명령줄에서 감사를 실행하고 감사 결과가 포함된 * .html 파일을 얻을 수 있습니다.
컴퓨터에 Google 크롬이 설치되어 있는지 확인하세요.
Node의 현재 장기 지원 버전을 설치합니다 (다음 예제는 최신 비 LTS 버전으로 수행되었지만 Google 자체에서 LTS 버전 사용을 권장함).
다음 명령을 사용하여 Lighthouse를 전체적으로 설치합니다. npm install -g lighthouse
