본문 바로가기
728x90

전체 글

백준 문제풀이 2023. 1. 28. [백준][파이썬] 2580 스도쿠 1.문제 분석 스도쿠 판의 빈칸을 채우는 문제 가로, 세로, 사각형 모두 체크해야 한다. 2. 기본 아이디어 가로, 세로, 사각형을 체크할 함수를 구현한다. 빈 스도쿠 칸은 따로 리스트를 통해 빼둔다. 3.문제 풀이 빈칸의 좌표를 blank리스트에 따로 빼두었다. 이 빈칸의 좌표에 1~9까지의 숫자를 대입하며 가능성을 체크한다. def width(x, n): # x좌표 확인 for i in range(9): if (n == sudoku[x][i]): return False return True def height(y, n): # y좌표 확인 for i in range(9): if (n == sudoku[i][y]): return False return True def rectangle(x, y, n): ..
[백준][파이썬] 9663 N-Queen
백준 문제풀이 2023. 1. 27. [백준][파이썬] 9663 N-Queen 1.문제 분석 백트래킹 문제 N*N칸의 체스판에 N개의 퀸이 서로 공격하지 못하도록 한다. 2. 기본 아이디어 퀸은 한 행에 하나만 존재한다. ( N x N 칸에 N개의 퀸을 놓기 때문) 한 행에 퀸을 놓았다면 열, 대각선만 확인해주면 된다. 3.문제 풀이 2차원 배열을 통해 문제를 풀어야겠다고 생각했으나, 코드가 너무 복잡해졌다. 도무지 감이 안잡혀 구글링을 했고, 1차원 리스트로 표현할 수 있는 방법이 있다는 것을 알았다. 그리고 고민하던 중에 굳이 체스판을 입체적으로 생각하지 않아도 된다는 것을 알았다. (요즘 체스에 취미가 생긴 것이 한몫했다.) 체스판의 숫자와 알파벳을 1차원 리스트의 인덱스와 값이라고 생각하면 편리했다. 그러니까 chess[0] = 1 이라고 하면 윗 그림에서 흑 나이트 즉, ..
백준 문제풀이 2023. 1. 25. [백준][파이썬] 2587 대표값2 1.문제 분석 평균, 중앙값을 구하는 문제 정렬 문제 2. 기본 아이디어 파이썬의 list.sort()를 활용한다. 파이썬의 sum(list)를 활용한다. 3.문제 풀이 파이썬에는 정렬 함수와 합 함수가 만들어져 있다. 따라서 그 함수들을 활용한다. (그밖의 다른 정렬을 사용할 수도 있다.) lst = [] for i in range(5): lst.append(int(input())) lst.sort() n = sum(lst) print(n//5) print(lst[2])
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15652 N과 M (4) 1.문제 분석 중복을 포함한 비내림차순 수열을 출력하는 문제 백트래킹을 사용하는 문제 2. 기본 아이디어 매개변수로 num을 받아와 for문이 num부터 시작하도록 한다. 3.문제 풀이 i의 증가를 통해 재귀시마다 for문의 시작값을 증가시켜 비내림차순의 수열을 출력한다. n, m = map(int, input().split()) lst = [] def BackTracking(num): if len(lst) == m: print(" ".join(map(str, lst))) return for i in range(num, n + 1): # num을 i로 지정해 오름차순으로 출력한다. lst.append(i) # i not in lst를 사용하지 않아 중복을 허용한다. BackTracking(i) lst.p..
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15651 N과 M (3) 1.문제 분석 1부터 n까지의 자연수 중 중복을 포함하여 m개의 수를 고른다. 백트래킹을 사용하는 문제 2. 기본 아이디어 N과 M (1)번 문제에서 if not i in lst 구문 대신 len(lst) != m 구문을 넣는다. 3.문제 풀이 len(lst) != m 구문은 리스트의 길이가 m이 되기 전까지 재귀를 반복한다. 따라서 리스트의 길이가 m이 되었을 때 중복 상관없이 출력할 수 있게 된다. n, m = map(int, input().split()) lst = [] def BackTracking(): if len(lst) == m: print(" ".join(map(str, lst))) for i in range(1, n + 1): if len(lst) != m: lst.append(i) Ba..
백준 문제풀이 2023. 1. 13. [백준][파이썬] 15650 N과 M (2) 1.문제 분석 숫자의 중복 없이 오름차순 수열만 출력하는 문제 백트래킹을 사용하는 문제 2. 기본 아이디어 N 과 M (1)번 문제에서 오름차순 수열만 가져오도록 코드를 수정한다. 3.문제 풀이 오름차순을 출력하는 방법으로 실제 오름차순 리스트와 비교하는 문장을 추가했다. n, m = map(int, input().split()) lst = [] def BackTracking(): if len(lst) == m: lst_sorted = sorted(lst) # 리스트와 그 리스트의 오름차순 리스트가 동일한지 비교 if(lst == lst_sorted): print(" ".join(map(str, lst))) for i in range(1, n + 1): if i not in lst: lst.append(..
백준 문제풀이 2023. 1. 12. [백준][파이썬] 15649 N과 M (1) 1.문제 분석 백트래킹을 사용하는 문제 조건에 맞게, 중복 없이 수를 나열해야 한다. 1 ~ n 범위의 자연수 m개를 중복없이 골라야 한다. 2. 기본 아이디어 백트래킹 함수를 구현한다. 조건문과 재귀를 이용한다. 3.문제 풀이 우선 백트래킹이란 무엇일까? https://walk-cat-dev.tistory.com/56 - 이 곳에 간단하게 정리해 놓았다. 파이썬 코드 n, m = map(int, input().split()) lst = [] def backTracking(): if len(lst) == m: # 조건에 맞으면 출력 print(' '. join(map(str, lst))) for i in range(1, n+1): if i not in lst: # 중복 제거 lst.append(i) ba..
[알고리즘] 백트래킹 (BackTracking)
Computer Science/Algorithms 2023. 1. 12. [알고리즘] 백트래킹 (BackTracking) 백트래킹이란? 재귀적으로 문제를 풀어나가는 알고리즘 특정 조건에 위배되면 가지치기를 함 ( 특정 노드를 제외하는 것 ) DFS를 사용하는 알고리즘 중에 백트래킹이 있다. ( DFS는 최적의 경로를 반환한다.) 백트래킹과 DFS의 차이점 DFS는 가능한 모든 경로를 탐색하므로, 가지치기를 하지 않는다. 백트래킹은 현재의 경로가 불필요하다면 다시 되돌아간다. DFS에서 조건문과 재귀를 통해 코드를 구현하면 백트래킹을 구현할 수 있다. 백트래킹의 구현, 예제 결론적으로 백트래킹은 DFS를 수행하고, 유망한 노드인지를 판단한 뒤 하위 노드로 이동하는 형식이다. 백트래킹을 이용한 문제 백준 - N과 M (1) https://walk-cat-dev.tistory.com/57
[백준][파이썬] 1461 도서관
백준 문제풀이 2023. 1. 10. [백준][파이썬] 1461 도서관 1.문제 분석 최소 걸음 수를 구하는 문제 들 수 있는 책의 개수와 책을 가져다 놓을 위치가 정해진다. 2. 기본 아이디어 절댓값 순으로, 양수와 음수 파트를 분리한다. 한 번에 가져갈 수 있는 책의 개수 만큼 for문을 통해 이동한다. 3.문제 풀이 이 문제의 경우 그리디 알고리즘이 쓰인다. 그리디 알고리즘은 당장 눈 앞의 최선을 선택하는 알고리즘인데, 이 문제도 최소 걸음 수를 걷도록 리스트에 접근하기 때문에 알맞은 것 같다. n, m = map(int, input().split()) lst = list(map(int, input().split())) pos, neg = [], [] # 양수, 음수 분리 last, walk = 0, 0 # 가장 먼 거리, 걸음 수 for i in lst: if i <..
728x90

티스토리툴바