두부의 코딩일기

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 풀이 이전에 풀었던 유기농 배추와 동일한 문제인데 난이도가 아주 조금 올라갔다. 아파트 단지 개수뿐만 아니라 단지 내에 몇 개의 집이 있는지를 구해야 하는 문제로 유기농 배추 문제에서 몇 가지 코드만 추가해주면 쉽게 풀 수 있다. 유기농 배추 문제와 달랐던 건 배열의 모양과 입력할 때이다. 예제를 살펴보면 '0110100'로 들어오는데 한 자리씩 잘라서 int형 배열에 넣어줘야 한다. map[i][..

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이 대표적인 dfs와 bfs 알고리즘 문제 중 하나이다. 필자는 재귀함수를 이용한 dfs가 제일 편하고 익숙해서 이걸로 해결했다. 1. N x M 크기의 int형 배열 2개를 만들어준다. 배추밭(map)과 방문 여부(check)를 기록할 배열이다. 2. 모든 배추밭을 다 돌면서 방문하지않은 곳의 인접한 배추를 찾으면 된다. if (x < map.length-1 && map[x+1][y] == 1 && che..

https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 주어진 숫자들로 덧셈과 뺄셈만을 이용해서 목표값을 만드는 문제이다. 모든 경우의 수를 거쳐야하므로 깊이 우선 탐색 (dfs)가 바로 생각이 났다. dfs 함수를 생성하고 마지막 노드까지 탐색했을 때 목표값과 일치한다면 answer++를 해주는 방식으로 코드를 설계했다. 여기서 중요한 건 목표값을 도달했을 때 answer++를 해주는 것이 아닌 마지막 노드까지 탐색을 완료해야한다는 점이다. 깊..