목록코딩 테스트/백준 (139)
미소를뿌리는감자의 코딩
https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 1. 접근 방법 이 문제는 처음에는 dfs로 접근했다가, 재귀 호출 recursion error가 발생해서 다르게 접근해야 했다. 백준 밑에 있는 이분 탐색이라는 힌트를 보게 되었고 이를 이용해서 문제를 해결하고자 하였다. 이분 탐색을 어떤 기준으로 해야할 지 고민하다가 아래 유튜브 영상을 보게 되었다. https://www.youtube.com..
https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 1. 접근 방법 https://www.youtube.com/watch?v=1Bh6DBcKgOc 이 영상 덕분에 좋은 풀이를 잘 이해할 수 있었다. 동일한 대각선 위에 있는지 확인하는 방법을 알게 되었다. [x+y] 가 동일한지, [x-y] 가 동일한지 확인하면 된다. 그림으로 설명하는게 편할 것 같아서 그림을 그려보았다. 우선 같은 세로 줄에 위치하는지 확인하기 위해서는 v1이라는 선언된 리스트를 통해서 확인이 ..
https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 1. 접근 방법 이번 문제는 dfs가 아닌 bfs로 접근해야하는 문제라고 생각이 들었다. 같은 level에 위치한 값에 대해서, 좌우상하 퍼져나가는 것을 같은 시간대에 진행해야하기 때문이다. 만약 dfs로 진행한다면, 한 익은 토마토에 대해서 전체 박스에 퍼져나간 후, 다음 익은 토마토에 대한 코드를 진행하기 때문이다. 따라서 bfs로 재귀적으로 코드를 구성하고 문제를 푸니 rec..
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 1. 접근 방법 이 문제는 '2667번 단지번호 붙이기'처럼 접근해서 재귀적으로 풀었더니 깊이 초과가 되어서, 다른 방식으로 접근했어야 했다. 우선 재귀적으로 접근하였던 코드는 다음과 같다. def setting(): m, n, k = map(int, input().split()) list_r = [[0 for _ in range(m)] for _ in range(n)] for i in range(k): x,..