본문 바로가기

전체 글203

[프로그래머스] DFS/BFS - 게임 맵 최단거리 아직 BFS가 낯설어서! 다른 분 코드 참고 from collections import deque def solution(maps): # 방향 설정 : 앞,아래,뒤,위 dx = [-1,0,1,0] dy = [0,1,0,-1] result = 0 n = len(maps) # 행 개수 m = len(maps[0]) # 각 열마다 몇 개 있는 지, ck = [[0]*m for _ in range(n)] # n*m 2차원 배열 생성 dis = [[0]*m for _ in range(n)] # n*m 2차원 배열 생성 queue = deque() # 큐 생성 ck[0][0] = 1 #방문처리 dis[0][0] = 1 #방문처리 queue.append((0,0)) #큐에 삽입 while queue: now = qu.. 2024. 3. 22.
[이것이 코딩테스트다] Chapter 02. DFS/BFS 이어서 인접 행렬 방식 : 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비 인접 리스트 방식 : 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용 인접 리스트 방식은 인접 행렬 방식에 비해 정보를 얻는 속도가 느림 But. 인접 리스트 방식은 인접 행렬 방식에 비해 메모리 공간의 낭비가 적다. DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 3. 2번의 과정을 수행할 수 없을 때까지 반복한다. 깊이 우선 탐색 알고리즘인 DFS는 .. 2024. 3. 21.
[이것이 코딩테스트다] Chpter 05 DFS/BFS 탐색 - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조 - 데이터를 표현하고 관리하고 처리하기 위한 구조 삽입 : 데이터를 삽입한다 삭제 : 데이터를 삭제한다. 스택 - First IN Last Out 나중에 들어온 것이 먼저 빠짐. 샌드위치 구조 stack = [] stack.append(4) stack.pop() 큐 - First In First Out ex. 놀이공원 처음에 들어온 사람이 먼저 나감 queue = deque() queue.append(5) queue.popleft() print(queue) -> 먼저 들어온 순서대로 출력 queue.reverse() -> 역순으로 바꾸기 재귀 함수 자기 자신을 다시 호출하는 함수 DFS 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 .. 2024. 3. 20.
[이것이 코딩테스트다] Chapter 2. 구현 - 실전문제 / 게임 개발 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 캐릭터는 상화좌우로 움직일 수 있고, 바다로 되어 있는 공간에느 갈 수 없다. 움직임을 설정하기 위해 정해 놓은 메뉴얼은 이러하다. 1. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향부터 차례대로 갈 곳을 정한다. 2. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음 왼쪽으로 한 칸을 전진한다. 왼쪽 방향에 가보지 않은 칸이 없다면, 왼쪽 방향으로 회전만 수행하고 1단계로 돌아간다. 3. 네 방향 모두 가본 칸이거나 바다로 되어 있는 칸이면, 바라보는 방향을 유지한 채로 한 칸 뒤로 가고 1단계로 돌아간다. 단, 이때 뒤쪽 .. 2024. 3. 18.
[이것이 코딩테스트다] Chapter 2 구현 실전문제 왕실의 나이트 실전문제 - 왕실의 나이트 나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 이동하는 법 1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기 2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기 나이트의 위치가 주어졌을 때 , 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램 입력예시 : a1 출력예씨 : 2 나이트의 이동 경로를 steps 변수에 넣는다면 위 규칙에 따라 8가지 경우의 수를 정의할 수 있다. 각 8가지 방향에 대하여 각 위치로 이동이 가능한 지 확인한다. # 현재 나이트의 위치 입력받기 input_data = input() row = int(input_data[1]) # 열 column = int(ord(in.. 2024. 3. 18.
[프로그래머스] 완전탐색 - 카펫 나의 답 def check(brown, yellow,x,y): b = x*y-((x-2)*(y-2)) y = (x-2)*(y-2) if brown == b and yellow == y: return 1 else: return 0 def solution(brown, yellow): cnt = brown+yellow arr = [] for i in range(3,cnt+1): # 약수 구하기 if cnt%i==0: arr.append(i) for value in arr: # 약수 조합 활용 x = value y = int(cnt/value) if check(brown, yellow,x,y): # 가로, 세로 값에 따라서 brown, yellow 충족 확인 return [x,y] if x>y else [y, .. 2024. 3. 18.

티스토리툴바