#문제 정보프로그래머스, 퍼즐 조각 채우기문제: https://school.programmers.co.kr/learn/courses/30/lessons/84021#문제 요약정사각 격자 모양에 크기가 서로 같은 2차원 배열 game_board와 table가 주어진다.table에는 여러 도형 퍼즐이 놓여 있다. 도형 퍼즐은 1, 빈 공간은 0으로 표현되어 있다.game_board에는 퍼즐을 끼워 맞출 수 있는 빈 공간이 있다. 빈 공간은 0, 막힌 부분은 1로 표현되어 있다.table에 있는 도형 퍼즐을 game_board의 빈 공간에 최대한 많이 넣어 맞추려 할 때, 총 몇 칸을 채울 수 있을까?table의 도형 퍼즐을 빈 공간에 맞추기 위해서 회전할 수는 있지만, 뒤집을 수는 없다.#접근 방식table을..

#문제 설명 백준, 2206 벽 부수고 이동하기 문제: https://www.acmicpc.net/problem/2206 #오답 풀이 시작점에서 도착점까지의 최단 거리는 BFS로 구한다. 문제는 어떤 벽을 부숴야 하는지이다. 내가 짠 알고리즘은 이러했다. 시작점에서 어떤 벽까지의 최단 거리 + 그 벽에서 도착점까지의 거리를 구하기 위해, BFS를 두 번 나누어 수행한다. 처음 BFS에서는 방문하지 않은 길을 탐색하면서, 벽을 만난다면 벽의 위치를 다른 큐에 담는다. visited에 거리를 담는다. 다음 BFS에서는 벽의 위치를 담은 큐를 가지고 BFS를 수행한다. 벽에서 시작한다는 건 이미 벽을 부쉈다는 것이라고 볼 수 있으므로, 벽을 만난다면 무시한다. 반면 저번에 방문한 적이 있는 위치여도 현재 루트..

#문제 설명 백준, 1012 유기농 배추 문제: https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 "1의 군집 개수 구하기" 문제이다. #나의 풀이 T = int(input()) dr = [0, 0, -1, 1]# 상하좌우 4방향 (row) dc = [1, -1, 0, 0]# 상하좌우 4방향 (column) def dfs(r, c, arr, m, n): arr[r][c] = 0# 방문했으니까, 1 -> 0 for k in range(4):# 4방향 ..

#문제 설명 프로그래머스, 송아지 찾기 #나의 풀이 이 문제가 BFS로 분류되어 있어서 웬 BFS지 싶었는데, 몇 번만에 목표에 도달하는지 그 최소 횟수가 필요한 문제라 그런 것 같았다(BFS는 최단거리, 도달하기 위한 최소 횟수 구하는 문제 해결 방법으로 주로 쓰인다). 현수가 콩콩이로 점프하여 도달할 수 있는 위치를 상태 트리로 그리면 위와 같이 표현할 수 있다. 그리고 몇 번의 점프만에 어느 곳에 도달했는지를 아래 배열 그림과 같이 표현할 수 있다. 큐에 현재 위치에서 점프하여 현수가 도달 가능한 위치를 저장해놓고, 하나씩 pop하면서 송아지 위치와 일치하는지 확인하는 방식으로 문제를 해결할 수 있다. def solution(s, e): visited = [-1] * 10001 q = [s] cnt..

#문제 설명 프로그래머스, 완주하지 못한 선수 문제: https://programmers.co.kr/learn/courses/30/lessons/42576 #나의 풀이 function solution(participant, completion) { let map = new Map(); participant.forEach((p) => { map.get(p) ? map.set(p, map.get(p) + 1) : map.set(p, 1); }); completion.forEach((c) => { map.set(c, map.get(c) - 1); if (map.get(c) === 0) map.delete(c); }); return Array.from(map.keys()).toString(); } 문제 자체는 ..