갬미의 성장일기

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 5 DFS/BFS 오늘 풀이한 문제 [백준 18405] 경쟁적 전염 접근 방법 (오답) 1. 한 리스트 안에 바이러스별로 위치를 저장하고 각 위치를 큐의 시작점으로 사용 2. virus 리스트를 돌면서 좌표와 index를 하나씩 받아옴 3. 좌표에서 K번씩 퍼트림 (cnt 변수를 사용) 이렇게 했을때 로직은 맞는것 같은데 자꾸 오답이라고 나왔다,, 👇 문제의 코드,,, n, k = 3, 3 s, x, y = 2, 3, 2 space = [[1, 0, 2], [0, 0, 0], [3, 0, 0]] virus = [[]*v for v in range (k+1)] ## virus위치 리스트 만들기 (index ..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 5 DFS/BFS 오늘 풀이한 문제 [백준 14502] 연구소 문제 - 바이러스(2)와 연결된 0을 오염시켜 2로 만들수 있다. 이때 현재 벽(1)에서 3개의 벽을 더 세워 최대한으로 살아남은 0의 개수를 센다 접근법 1. combinations를 사용해서 벽이 세워질 수 있는 모든 경우의 수를 구하자 2. 조합별로 bfs를 수행하고 0의 개수를 세자 - 이때 virus가 있는 부분에서만 bfs를 시작해서 실행시간을 단축하자!! ## input - 주피터에서 실험하기위해 미리 test case 입력 lab = [[2, 0, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 2, 0], [0, 1, ..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 5 DFS/BFS 오늘 풀이한 문제는 다음 두가지이다 [이코테 152P] 미로탈출 문제설명 N by M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 괴물이 있어 이를 피해서 탈출해야 한다. 유저의 초기 위치는 (1, 1)이고 미로의 출구는 (N, M) 위치에 존재하며 한 번에 한 칸 씩 이동이 가능하다. 이 때 괴물이 있는 부분은 0, 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이 때 유저가 미로를 탈출하기 위해 움직여야 할 최소 칸의 개수를 구해라. 단, 칸을 셀 때 시작, 마지막 칸도 포함시켜야 한다. 입력조건 첫째 줄에 두 정수 N, M(4 = m: con..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 5 DFS/BFS * 학습 전 미리 알아야 할 자료구조와 함수 1. 스택, 큐 - 스택 (Stack) 스택이란 선입후출 (First In Last Out, FILO) 자료구조로 차곡차곡 쌓아 올린 형태의 자료구조이다 스택은 python의 list로 구현이 가능하다 ( push -> append() / pop -> pop() ) - 큐 ( Queue ) 큐란 선입선출(First In First Out) 자료구조이며 '공정한' 자료구조로 비유된다 (은행 대기줄과 같음) 파이썬의 collections 라이브러리의 deque 를 사용할 수 있다 (push -> queue.append() / pop -> queue..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 4 구현 알고리즘 문제 풀이(3) 오늘 풀이한 문제는 다음이다 [ 백준 15686 ] 치킨 배달 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 파이썬 라이브러리 중 하나인 itertools를 알고 있다면 무난히 풀 수 있는 문제인 것 같다 ## Python3 itertools # 순열, 조합, 곱집합 구하기 from itertools import permutations, combinatio..

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다. Chapter 4 구현 알고리즘 문제 풀이(2) 오늘 풀이한 문제는 다음 두가지이다 [ 백준 3190 ] 뱀 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net - 뱀의 위치를 deque를 이용해서 푸는 방식도 있지만 list로 구현해 보았다 - 또한 어제 배운대로 이동시 위치는 dx, dy를 만들어 활용하였다. - 사실 로직은 맞았는데 뱀의 몸의 길이를 조절하는 부분에서 애를 먹었다 [프로그래머스] 기둥과 보 설치 문제 풀이 (202..