분류 전체보기(754)
-
[알고리즘][2][X] 등굣길
문제 설명 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다. image0.png 가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다. 격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요. 제한사항 격자의 크기 m, n..
2023.08.25 -
[알고리즘][2] 아이템 줍기
아이템 줍기 문제 설명 다음과 같은 다각형 모양 지형에서 캐릭터가 아이템을 줍기 위해 이동하려 합니다. rect_1.png 지형은 각 변이 x축, y축과 평행한 직사각형이 겹쳐진 형태로 표현하며, 캐릭터는 이 다각형의 둘레(굵은 선)를 따라서 이동합니다. 만약 직사각형을 겹친 후 다음과 같이 중앙에 빈 공간이 생기는 경우, 다각형의 가장 바깥쪽 테두리가 캐릭터의 이동 경로가 됩니다. rect_2.png 단, 서로 다른 두 직사각형의 x축 좌표 또는 y축 좌표가 같은 경우는 없습니다. rect_4.png 즉, 위 그림처럼 서로 다른 두 직사각형이 꼭짓점에서 만나거나, 변이 겹치는 경우 등은 없습니다. 다음 그림과 같이 지형이 2개 이상으로 분리된 경우도 없습니다. rect_3.png 한 직사각형이 다른 직..
2023.08.23 -
[알고리즘][2][X] 게임 맵 최단거리
문제 설명 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 최단거리1_sxuruo.png 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 ..
2023.08.23 -
[AI] feature extraction과 feature selection에 대한 나름의 이해
feature selection은 원래 있던 feature들 중 필요없는 것들을 제거하는 것이고 feature extraction은 원래 있던 feature들을 활용하여 새로운 feature들의 집합을 만드는 것이다. feature extraction에는 대표적으로 PCA가 있는데 주요한 성분 먼저 추출을 통해 압축을 하는 것으로 볼 수 있다. 입력 데이터의 공분산 행렬을 통해 고유벡터를 구하고 입력데이터와 고유벡터를 선형변환하여 차원을 축소하는 방법이다. Reference https://huidea.tistory.com/126 [Machine learning] 차원축소, PCA, SVD, LSA, LDA, MF 간단정리 (day1 / 201009) Q. 차원의 저주에 대해 설명해주세요. dimensio..
2023.08.23 -
[CS] 플로이드 워셜 이해 안되는 점
과연 시작되는 순서가 바뀐다고 해도 결과는 같을까? 결과적으로 for문의 순서를 바꿔도 같고 iteration 숫자를 바꿔도 같다. 왜 그런지는 잘 모르겠다. def floyd(): # k는 경유하는 노드 for i in range(1, NODE_CNT+1): for j in range(1, NODE_CNT+1): for k in range(1, NODE_CNT+1): # k노드를 경유하는 거리값이 더 작으면 갱신 graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]) if __name__ == "__main__": NODE_CNT = 4 INF = 2147000000 graph = [[INF] * (NODE_CNT + 1) for _ in range(NO..
2023.08.23 -
[알고리즘][2][RE] 사칙연산
문제 설명 사칙연산에서 더하기(+)는 결합법칙이 성립하지만, 빼기(-)는 결합법칙이 성립하지 않습니다. 예를 들어 식 1 - 5 - 3은 연산 순서에 따라 다음과 같이 다른 결과를 가집니다. ((1 - 5) - 3) = -7 (1 - (5 - 3)) = -1 위 예시와 같이 뺄셈은 연산 순서에 따라 그 결과가 바뀔 수 있습니다. 또 다른 예로 식 1 - 3 + 5 - 8은 연산 순서에 따라 다음과 같이 5가지 결과가 나옵니다. (((1 - 3) + 5) - 8) = -5 ((1 - (3 + 5)) - 8) = -15 (1 - ((3 + 5) - 8)) = 1 (1 - (3 + (5 - 8))) = 1 ((1 - 3) + (5 - 8)) = -5 위와 같이 서로 다른 연산 순서의 계산 결과는 [-15, -..
2023.08.23