이 문제에 그리디를 적용 하면 최적의 해를 구할 수 없다. N = 10 이라고 하면 현재의 상황에서는 나누기 3을 하는게 좋아보이나, 실제로는 그렇지 않고 -1을 해야 최적의 해를 도출할 수 있으므로.
이 문제는 DP를 사용하는 것이 바람직하다. DP를 사용하면 작은 문제의 해를 저장하고, 이를 나중에 활용하여 큰 문제의 해를 도출할 수 있다. DP는 "메모이제이션" 개념을 활용한다.
import sys
def solution(N):
for i in range(2, N+1):
D[i] = D[i-1] + 1
if i % 2 == 0:
D[i] = min(D[i], D[i//2] + 1)
if i % 3 == 0:
D[i] = min(D[i], D[i//3] + 1)
return D[N]
if __name__ == "__main__":
input = sys.stdin.readline
N = int(input())
# D[i]는 주어진 규칙들로 정수 i를 1로 만드는데에 사용된 최소연산횟수
D = [0] * (N+1)
D[1] = 0
print(solution(N))
회전 초밥 음식점에는 회전하는 벨트 위에 여러 가지 종류의 초밥이 접시에 담겨 놓여 있고, 손님은 이 중에서 자기가 좋아하는 초밥을 골라서 먹는다. 초밥의 종류를 번호로 표현할 때, 다음 그림은 회전 초밥 음식점의 벨트 상태의 예를 보여주고 있다. 벨트 위에는 같은 종류의 초밥이 둘 이상 있을 수 있다.
새로 문을 연 회전 초밥 음식점이 불경기로 영업이 어려워서, 다음과 같이 두 가지 행사를 통해서 매상을 올리고자 한다.
원래 회전 초밥은 손님이 마음대로 초밥을 고르고, 먹은 초밥만큼 식대를 계산하지만, 벨트의 임의의 한 위치부터 k개의 접시를 연속해서 먹을 경우 할인된 정액 가격으로 제공한다.
각 고객에게 초밥의 종류 하나가 쓰인 쿠폰을 발행하고, 1번 행사에 참가할 경우 이 쿠폰에 적혀진 종류의 초밥 하나를 추가로 무료로 제공한다. 만약 이 번호에 적혀진 초밥이 현재 벨트 위에 없을 경우, 요리사가 새로 만들어 손님에게 제공한다.
위 할인 행사에 참여하여 가능한 한 다양한 종류의 초밥을 먹으려고 한다. 위 그림의 예를 가지고 생각해보자. k=4이고, 30번 초밥을 쿠폰으로 받았다고 가정하자. 쿠폰을 고려하지 않으면 4가지 다른 초밥을 먹을 수 있는 경우는 (9, 7, 30, 2), (30, 2, 7, 9), (2, 7, 9, 25) 세 가지 경우가 있는데, 30번 초밥을 추가로 쿠폰으로 먹을 수 있으므로 (2, 7, 9, 25)를 고르면 5가지 종류의 초밥을 먹을 수 있다.
회전 초밥 음식점의 벨트 상태, 메뉴에 있는 초밥의 가짓수, 연속해서 먹는 접시의 개수, 쿠폰 번호가 주어졌을 때, 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ k ≤ 3,000 (k ≤ N), 1 ≤ c ≤ d이다. 두 번째 줄부터 N개의 줄에는 벨트의 한 위치부터 시작하여 회전 방향을 따라갈 때 초밥의 종류를 나타내는 1 이상 d 이하의 정수가 각 줄마다 하나씩 주어진다.
출력
주어진 회전 초밥 벨트에서 먹을 수 있는 초밥의 가짓수의 최댓값을 하나의 정수로 출력한다.
문제풀이
구하고자 하는건 먹을 수 있는 초밥 가짓수의 최댓값이다.
핵심
1. 초밥은 회전하며 돌고 돌으므로 리스트를 하나 더 만들어 시작과 끝을 잇자.
=> extend() 활용
2. 연속으로 먹어야 한다 => 슬라이딩 윈도우
★윈도우를 이동시키면서 윈도우의 맨 왼쪽값을 빼고 맨 오른쪽 원소의 다음값을 넣으면서 탐색.
=> O(N)시간복잡도로 연산 가능하다.
잘못된 접근
처음에 봤을 땐, 문제 이해를 잘 못해서 회전할 수 있다는 내용을 보고 큐를 떠올렸다.
체크 배열을 만들어서 하나씩 초밥을 pop시켜
해당 초밥번호의 체크 배열 인덱스 값을 0에서 1로 갱신하고,
체크하지 않은 초밥과 쿠폰번호가 아닌 번호만 고르자 로 생각함;
두번째 시도했을땐, 투포인터를 떠올렸다.
하지만 시간복잡도를 간과하고 구현하니 시간초과 났다.
"핵심"부분에 언급한 내용을 상기하며 올바르게 구현할 수 있었다.
코드
import sys
input = sys.stdin.readline
N, d, k, c = map(int, input().split()) # d는 초밥가짓수, k는 연속으로 먹는 접시수
arr = [int(input()) for _ in range(N)] # 배열에 입력값 받기 (초밥번호)
dict = {} # 초밥 개수 저장할 딕셔너리
maxValue = 0
l = 0
r = l + (k-1)
# 회전하므로 리스트 두개를 잇는다
# 7 9 7 30 2 7 9 25 / 7 9 7 30 2 7 9 25
arr.extend(arr)
# 4개 연속으로 먹을거니까, 쿠폰번호 초밥 받음
dict[c] = 1
# 초기 윈도우에서 초밥 종류 세자.
for i in range(l, r+1):
if arr[i] not in dict:
dict[arr[i]] = 1
else:
dict[arr[i]] += 1
# 먹은 초밥 가짓수 세기
maxValue = len(dict)
r += 1
# 슬라이딩 윈도우 적용
while r < len(arr):
# 맨 왼쪽 초밥 제거
dict[arr[l]] -= 1
if dict[arr[l]] == 0:
del dict[arr[l]]
# 오른쪽 초밥 추가
if arr[r] not in dict:
dict[arr[r]] = 1
else:
dict[arr[r]] += 1
cnt = len(dict)
maxValue = max(cnt, maxValue)
l += 1
r += 1
print(maxValue)
#★=> 슬라이딩 윈도우를 활용하여 O(N)내에 해결가능하다.
=> dx, dy 배열 만들어 BFS시에 현재위치에서 다음 가능한 좌표구할때 반복문 돌리기.
K가 2500까지 가능하므로 이중 for문으로 돌려도 N^2으로 시간초과 걱정은 없다.
+ 적록색약 문제 핵심 떠올리자
1. 모든 노드를 시작점으로 하여,
그 위치를 방문하지 않았고, 배추가 있는 노드이면 BFS시행
2. BFS 시행이 한번끝났다는 건 인접한 구역 탐색이 끝났다는 것이므로
구역수 cnt 1증가
코드
from collections import deque
def BFS(r, c):
queue = deque([(r, c)])
visited[r][c] = 1
while queue:
cr, cc = queue.popleft()
for i in range(4):
nr = cr + dx[i]
nc = cc + dy[i]
if 0 <= nr < N and 0 <= nc < M and graph[nr][nc] and not visited[nr][nc]:
queue.append((nr, nc))
visited[nr][nc] = 1
# 테스트 케이스 입력값 부터 받아서 시작.
T = int(input())
for i in range(T):
M, N, K = map(int, input().split())
graph = [[0 for _ in range(M)] for _ in range(N)]
visited = [[0 for _ in range(M)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 입력값(배추좌표)받아 배추밭 채우기
for i in range(K):
x, y = map(int, input().split())
graph[y][x] = 1
# 구역 수 구하기
cnt = 0
for c in range(M):
for r in range(N):
#배추 있고 방문하지 않은 배추좌표만 탐색
if graph[r][c] and not visited[r][c]:
BFS(r, c)
cnt += 1
print(cnt)
# 필요한 배추흰지렁이 마리수
# 인접하지 않은곳은 지렁이가 갈 수 없으니
# == BFS를 통해 구역개수 구하기를 의도한 문제
# 어떻게 구하더라?
# 음... 적록색약 문제를 떠올려 보자면
# 반복문을 통해 (배추가있는)모든 좌표를 시작점으로 잡고, 그 위치가 방문하지 않은 좌표이면 BFS 시행
# 1번의 BFS 종료 후에 cnt 증가
체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?
입력
입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다.
각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1} × {0, ..., l-1}로 나타낼 수 있다. 둘째 줄과 셋째 줄에는 나이트가 현재 있는 칸, 나이트가 이동하려고 하는 칸이 주어진다.
출력
각 테스트 케이스마다 나이트가 최소 몇 번만에 이동할 수 있는지 출력한다.
예제 입력 1
3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1
예제 출력 1
5
28
0
문제풀이
체스 규칙대로 나이트가 이동하면서 목표좌표까지의 최소 연산 횟수를 구하는 문제
BFS로 쉽게 풀 수 있었다.
코드
from collections import deque
def BFS(curX, curY, cnt):
queue = deque()
queue.append(((curX, curY), cnt))
visited[curX][curY] = 1
while queue:
(curX, curY), cnt = queue.popleft()
if curX == desX and curY == desY:
print(cnt)
return
for i in range(8):
nx = curX + dx[i]
ny = curY + dy[i]
if 0 <= nx < I and 0 <= ny < I and not visited[nx][ny]:
queue.append(((nx, ny), cnt+1))
visited[nx][ny] = 1
T = int(input())
for _ in range(T):
I = int(input())
curX, curY = map(int, input().split())
desX, desY = map(int, input().split())
visited = [[0 for _ in range(I)] for _ in range(I)]
dx = [-2, -2, -1, -1, 1, 1, 2, 2]
dy = [-1, 1, -2, 2, -2, 2, -1, 1]
cnt = 0
BFS(curX, curY, cnt)
# 체스에서 나이트의 능력대로 이동하면서 목표지점까지의 최소 연산횟수를 구하는 문제
# BFS
from collections import deque
N = int(input())
graph = [[0 for _ in range(N)] for _ in range(N)]
section = [[0 for _ in range(N)] for _ in range(N)]
maxValue = 0
# 인풋값으로 그리드 판 채우기
for i in range(N):
graph[i] = list(input())
def BFS(cur):
global section
queue = deque()
queue.append(cur)
while queue:
(curX, curY), sNum = queue.popleft()
section[curX][curY] = sNum
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 다음 next좌표를 상하좌우로 찾는 로직
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
# section 리스트 값이 0이 아니면 방문한 것이므로 건너뜀
# 즉 0이 아닌 수로 업데이트가 안된 좌표만 탐색.
if 0 <= nx <= N-1 and 0 <= ny <= N-1 and not section[nx][ny]:
# 값(색상)이 다르면 구역나누기 => sNum 값 1증가
if graph[nx][ny] != graph[curX][curY]:
queue.append(((nx, ny), sNum + 1))
# 값이 같으면 섹션넘버 그대로 가져감
else:
queue.append(((nx, ny), sNum))
BFS(((0, 0), 1))
print(section)
for row in section:
rowMax = max(row)
maxValue = max(maxValue, rowMax)
print(maxValue)
2차 시기 코드
아래와 같이 구현하니 시간초과 났다.
찾아보니 방법은 맞게 접근하였지만, 시간초과 문제가 해결이 안돼서
setrecursionlimit도 설정하고.. 여러가지 해보았지만 여전히 시간초과가 난다.
사실 주어질 수 있는 입력값 N이 100까지 범위라 N^2 해도 시간복잡도 상으로는 괜찮다는걸 알고 있었지만 말이다.
from collections import deque
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
N = int(input())
graph = [0] * N
visited = [[False for _ in range(N)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 인풋값으로 그리드 판 채우기
for i in range(N):
graph[i] = list(input())
def BFS(start):
queue = deque([start])
while queue:
curX, curY = queue.popleft()
visited[curX][curY] = True
# 다음 next좌표를 상하좌우로 찾는 로직
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
# 인덱스 범위안에 있고 방문하지 않은 좌표이면 탐색
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
# 같은 색상이면
if graph[curX][curY] == graph[nx][ny]:
queue.append((nx, ny))
# BFS 활용하여 적록색약이 아닌 사람이 보는 section수 출력 로직
cnt1 = 0
for i in range(N):
for j in range(N):
if not visited[i][j]:
BFS((i, j))
cnt1 += 1
# BFS 활용하여 적록색약인 사람이 보는 section수 출력 로직
cnt2 = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
if graph[i][j] == 'G':
graph[i][j] = 'R'
for i in range(N):
for j in range(N):
if not visited[i][j]:
BFS((i, j))
cnt2 += 1
print(cnt1, cnt2)
코드
마지막으로 BFS호출하는 횟수가 여러번 있을거니까
그 안에서 visited 체크하는 로직에서 고칠 수 있겠다 싶어 보니,
이전 시기에는 큐에서 꺼낼때 visited체크 로직을 수행했지만,
큐에 삽입하고 나서 방문체크를 해야 중복된 노드를 탐색하지 않겠구나 싶어 수정하였다.
결과적으로 sys.stdin.readline 과 setlimitrecursion 처리 안해줘도 시간초과없이 성공!
정답코드
from collections import deque
N = int(input())
graph = [0] * N
visited = [[False for _ in range(N)] for _ in range(N)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 인풋값으로 그리드 판 채우기
for i in range(N):
graph[i] = list(input())
def BFS(x, y):
queue = deque()
queue.append((x, y))
visited[x][y] = True
while queue:
curX, curY = queue.popleft()
# 다음 next좌표를 상하좌우로 찾는 로직
for i in range(4):
nx = curX + dx[i]
ny = curY + dy[i]
# 인덱스 범위안에 있고 방문하지 않은 좌표이면 탐색
if 0 <= nx < N and 0 <= ny < N and not visited[nx][ny]:
# 같은 색상이면
if graph[curX][curY] == graph[nx][ny]:
queue.append((nx, ny))
visited[nx][ny] = True
# BFS 활용하여 적록색약이 아닌 사람이 보는 section수 출력 로직
cnt1 = 0
for i in range(N):
for j in range(N):
if not visited[i][j]:
BFS(i, j)
cnt1 += 1
# BFS 활용하여 적록색약인 사람이 보는 section수 출력 로직
cnt2 = 0
visited = [[False for _ in range(N)] for _ in range(N)]
for i in range(N):
for j in range(N):
if graph[i][j] == 'G':
graph[i][j] = 'R'
for i in range(N):
for j in range(N):
if not visited[i][j]:
BFS(i, j)
cnt2 += 1
print(cnt1, cnt2)
수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.
수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.
입력
첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.
출력
수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.
예제 입력 1
5 17
예제 출력 1
4
문제풀이
핵심
1. BFS
2. 메모이제이션
1. BFS
해당문제를 보고 DP로 풀어도 되겠다고 생각했다.
그러나 DP보다는 BFS가 더 적합하다.
이유는?
DP는 더이상 쪼갤 수 없는 시작위치에서 목표까지 구하는 문제에 유용하다.
하지만 이 문제는 임의의 시작위치에서 임의의 목표위치까지 가는 경우를 탐색하는 것이 핵심이므로 BFS가 더 적합하다.
BFS는 같은 연산횟수를 가진 형제를 먼저 탐색한다.
특정위치에서 연산 한번(연산 한번에 1초이므로)으로 갈 수 있는 위치는 -1, +1, *2 이다.
즉 연산은 -1, +1, *2 가 가능하고, N이 주어졌을때 K까지의 최소 연산 횟수를 구하면 된다.
2. 메모이제이션
연산횟수 리스트 만들어서 (나의 경우에는 dist = [0] * (MAX + 1))
자식노드 연산횟수는 부모노드 연산횟수에서 +1씩 업데이트
코드
import sys
from collections import deque
input = sys.stdin.readline
N, K = map(int, input().split())
MAX = 10 ** 5
dist = [0] * (MAX + 1) # ★거리(인덱스번호)에 따른 걸린시간 저장, dist[x] = x위치에 오기까지 걸린 시간
def BFS():
queue = deque()
queue.append(N)
while queue:
cur = queue.popleft()
# 최단시간 구해야하므로 시간이 지남에 따라 모든 경우의 수 중
# K값에 도달한 경우 나오면 리스트 값 바로 출력. => 최단시간
if cur == K:
print(dist[K])
return
# cur이 5라고 하면 다음 1초동안 갈수 있는 모든 거리의 경우의 수
# 즉, 4, 6, 10을 next 값으로 큐에 삽입 및 걸린시간정보 업데이트
for next in (cur-1, cur+1, cur*2):
if 0 <= next <= MAX and not dist[next]:
queue.append(next)
dist[next] = dist[cur] + 1
BFS()
BOJ 알고리즘 캠프에는 총 N명이 참가하고 있다. 사람들은 0번부터 N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구이다.
오늘은 다음과 같은 친구 관계를 가진 사람 A, B, C, D, E가 존재하는지 구해보려고 한다.
A는 B와 친구다.
B는 C와 친구다.
C는 D와 친구다.
D는 E와 친구다.
위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000)과 친구 관계의 수 M (1 ≤ M ≤ 2000)이 주어진다.
둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻이다. (0 ≤ a, b ≤ N-1, a ≠ b) 같은 친구 관계가 두 번 이상 주어지는 경우는 없다.
출력
문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다.
예제 입력 1
5 4
0 1
1 2
2 3
3 4
예제 출력 1
1
예제 입력 3
6 5
0 1
0 2
0 3
0 4
0 5
예제 출력 3
0
문제풀이
스택으로 풀어보려고 했는데 많이 헤맸다.
백트래킹은 재귀함수로 쉽게 구현가능하다고 한다.
핵심
1. 모든 노드를 시작점으로 하여 DFS 전부 수행
ABCDE 패턴을 DFS를 통해서 하나의 경로만 찾으면 되니까
2. 재귀 호출마다 depth를 더함
3. 백트래킹 (하나의 경로를 DFS 마치면 현재노드의 방문노드 해제하기)
코드
<재귀>로 푼 코드
import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
arrive = False
graph = [[] for _ in range(N)]
visited = [False] * N
#입력값 받아 인접리스트 만들기 (그래프 구현)
for _ in range(M):
s, e = map(int, input().split())
graph[s].append(e)
graph[e].append(s)
def DFS(cur, depth):
global arrive
if depth == 5: # depth 5가 되면 ABCDE 패턴 찾은것이므로 탐색종료
arrive = True
return
visited[cur] = True
# 현재노드의 친구관계 확인
for node in graph[cur]:
if not visited[node]:
#재귀호출
DFS(node, depth + 1) #현재의 경로의 깊이 정보를 DFS함수 매개변수로 넘겨줌
visited[cur] = False # 백트래킹 (현재노드의 방문노드는 다른 경로로 DFS할때 필요하므로 다시 해제)
# 모든 노드를 시작점으로 해서 DFS 전부 한번씩 수행
for i in range(N):
DFS(i, 1)
visited[i] = False
if arrive:
break
if arrive:
print(1)
else:
print(0)
<스택>으로 푼 코드
import sys
import copy
sys.setrecursionlimit(10000)
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
visited = [False] * N
arrive = False
for i in range(M):
n1, n2 = map(int, input().split())
graph[n1].append(n2)
graph[n2].append(n1)
def DFS(start):
global arrive
stack = [(start, 1, [start])]
while stack:
cur, depth, path = stack.pop()
visited[cur] = True
if depth == 5:
arrive = True
return
for node in graph[cur]:
if not visited[node] and node not in path:
newPath = copy.deepcopy(path)
newPath.append(node)
stack.append((node, depth + 1, newPath))
visited[cur] = False
for i in range(N):
DFS(i)
if arrive:
break
if arrive:
print(1)
else:
print(0)
핵심 1. 객체지향 프로그래밍 2. 프로토타입 기반 언어 3. 원시타입 vs 객체 4. 깊은복사 vs 얕은복사
1. 객체지향 프로그래밍
정의 : 실세계의 사물을 객체로 보고, 그 객체로부터 특징과 기능을 뽑아와(추상화) 모델링하는 프로그래밍 패러다임
쉽게말해, 우리가 주변의 실세계에서 사물을 인지하는 방식을 프로그래밍에 접목하려는 사상을 의미함.
★인스턴스 - 클래스에 의해 생성되어 메모리에 저장된 실체. 객체지향 프로그래밍에서 객체는 클래스와 인스턴스를 포함한 개념이다.
객체는 key와 value로 구성된 프로퍼티의 집합이라고 말할 수 있다. 근데 이 프로퍼티의 값으로 함수가 들어올 수 있음. 일반 함수와 구분 짓기 위해 '메서드'
=> 따라서 객체는 데이터를 의미하는 프로퍼티 + 동작을 의미하는 메서드로 구성됐다고도 말할 수 있다. 자바스크립트는 이미 생성된 인스턴스의 구조와 기능을 동적으로 변경할 수 있음.
cf. 자바스크립트의 객체는 상속을 구현하기 위해 Prototype이라는 객체의 프로퍼티와 메서드를 상속 받을 수 있다. ★객체지향의 상속, 캡슐화 등의 개념은 => 각각 프로토타입 체인, 클로저 등으로 비슷하게 구현 가능.
cf. 자바스크립트는 public 또는 private 등의 키워드를 제공하지 않는다. => 하지만 클로저를 활용하여 정보은닉 개념을 비슷하게 구현할 수 있다.
2. 프로토타입 기반 언어
자바스크립트가 객체를 생성하는 방법이다. JS에서 모든 객체는 상속 개념에 따라 자신의 부모 역할을 하는 객체와 연결되어 있는데, 이런 부모 객체를 프로토타입 객체라고 한다.
Java, C++와 같은 클래스 기반 객체지향 언어와 달리, JS는 프로토타입 기반 객체지향 언어이다.
클래스 기반 객체지향 언어는 객체 생성을 위해 클래스 정의가 선행되어야 하지만, 프로토타입 언어는 클래스 없이 객체 생성이 가능하다.
객체 생성 방법 (1) 객체 리터럴 편한 방법이지만, 동일한 프로퍼티 구조를 갖는 객체를 여러개 생성해야 할 경우에는 비효율적. e.g. 복수의 사용자, 메뉴 내 다양한 아이템을 객체로 표현할 경우
(2) 생성자 함수활용 생성자 함수를 활용해 객체를 생성하면 프로퍼티 구조가 동일한 여러개의 객체 동시 생성하기 용이.
프로퍼티 (1) 객체 프로퍼티 값 접근 방법 1. 마침표 표기법 2. 대괄호 표기법 객체에 존재하지 않는 프로퍼티를 참조하면 undefined를 반환한다.
(2) 프로퍼티 동적 생성 객체가 소유하고 있지 않은 프로퍼티 키에 값을 할당해도 생성해줌.
3. 원시타입 vs 객체(참조타입)
원시타입(boolean, number, string 등)과의 차이 - 원시타입은 변경 불가능 함. (메모리 영역에서의 변경(==수정)이 불가. 재할당은 가능) - 객체타입은 변경 가능한 값. ★왜? 변수에 객체값이 그대로 저장되는게 아니라, 객체에 대한 참조값이 저장되므로 (pass by reference)
cf. pass by value 와 pass by reference 원시타입과 객체의 가장 큰 차이라고 볼 수 있음.
객체는 참조에 의해 호출되고 전달됨. 하지만 이같은 특성은 의도하지 않은 객체의 변경 발생의 원인이 될수 있음. => 의도한 동작이 아니라면 참조를 가지고 있는 다른 장소에 변경 사실을 통지하고 대처하는 대응이 필요. => 스터디에서 다뤘던 디자인 패턴중 옵저버 패턴이 떠올랐다.
해결방법 - 객체의 방어적복사 객체의 변경이 필요한 경우에 참조가 아닌 방어적복사를 통해 새로운 객체를 생성 후 변경. - 불변객체화 Object.freeze()활용하여 프로퍼티 변경 방지
깊은복사 객체의 프로퍼티중 특정 프로퍼티의 값이 객체일 경우도 있을거다.(=> 중첩객체의 경우를 말함) clone.sizes = user.sizes를 하게 되면 sizes프로퍼티는 객체이므로 참조값이 복사된다. 이럴땐 각 프로퍼티의 값을 검사하면서, 값이 객체라면 그 객체의 구조도 복사해주는 반복문을 사용해야 함. => 깊은 복사. lodash메서드 사용.
