나보단 잘하자

7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 접근법 문제에서 '최소일수', '주변의 토마토들을 익힘' 이라는 말을 봐서 bfs 문제임을 알았다. dfs를 쓰면 안되는 문제였다. 깊이 들어갈 일이 없기 때문이다. 대각선 방향은 영향을 주지 않는다고 하였는데, 만약 대각선 방향의 영향을 준다면 위 아래 양옆 위치를 넣는 리스트에 대각선 방향만 넣으면 된다. 문제를 통해 한줄한줄 설명하겠다. 풀이 # bfs 특 queue 사용하기 # deque 모듈 안쓰면 시간복잡도 박살남(pop(0)이 시간복..

개념 타겟인 데이터의 앞 데이터들의 크기를 따져서 본인보다 큰 데이터 앞, 작은 데이터 뒤에 데이터를 삽입하는 방법이다. 이 배열을 삽입정렬로 오름차순 정렬해보자. 1. 처음은 처음의 다음 인덱스부터 타겟을 잡고 앞과 비교한다. 0번 인덱스의 데이터가 1번보다 크다. 그리고 0이 첫번째이기 때문에 더이상 앞으로 가 비교 할 데이터가 없다. 2. 2번 인덱스를 타겟으로 잡고 0, 1인덱스와 비교한다. 8을 보니 2보다 크기 때문에 교환 대상이지만, 삽입 정렬은 버블 정렬처럼 교환하지 않는다. '삽입' 하기 때문에 우선 2를 빼 두고 8을 2자리로 옮긴다. 0번째 데이터도 있기 때문에 2와 또 비교해본다. 3이 2보다 크기 때문에 3도 밀고 그 자리에 2를 '삽입' 한다. 3. 3번 인덱스를 타겟으로 잡고 ..

개념 이름 그대로, 배열 내 최솟값을 '선택'해서 맨 앞 인덱스와 교환하는 방법이다. 첫 인덱스가 최솟값으로 변경 되면, 그 다음 인덱스부터 시작하는 배열로 최솟값을 찾아 그 다음 인덱스를 최솟값으로 변경한다. 아래의 배열을 선택정렬로 정렬해보자. 1. 0번 인덱스부터 4번 인덱스중 최솟값인 2번 인덱스와 0번 인덱스 자리를 바꾼다. 2. 0번 인덱스가 이미 최솟값이 됐으니, 1번 인덱스부터 4번 인덱스 중 최솟값인 1번 인덱스를 그냥 놔둔다. 3. 2번 인덱스부터 4번 인덱스 중 최솟값인 4번 인덱스를 2번 인덱스와 교환한다. 원래같으면 3번 인덱스와 4번인덱스 사이의 숫자를 확인하겠지만, 이미 정렬이 완료 됐으니 그만 한다. 구현 비교 대상을 설정해야 한다. 비교 대상과 루프를 돌렸을 때 나오는 숫자..

개념 앞의 항과, 바로 뒤의 항 단 두 항만을 비교한다. 앞의 숫자보다 뒤의 숫자가 더 작다면 서로를 바꾼다. 아래의 배열을 버블정렬로 오름차순 정렬 해보자. 1. 인덱스 0과 1의 숫자들을 우선 비교한다. 8보다 3이 더 크므로, 둘을 바꾼다. 2. 인덱스 1과 2의 숫자들을 비교한다. 8보다 2가 더 크므로, 둘을 바꾼다. 3. 인덱스 2와 3의 숫자들을 비교한다. 8보다 7이 더 크므로, 둘을 바꾼다. 4. 마지막으로 인덱스 3과 4의 숫자들을 비교한다. 8보다 6이 더 크므로, 둘을 바꾼다. 첫번째 턴을 다 돌았다. 그러나 정렬되지 않았다. 이렇게 턴을 총 인덱스 - 1번만큼 돈다. 구현 lists = [8, 3, 2, 7, 6] for i in range(len(lists) - 1): for j..