목록알고리즘 (178)

시작이 반

[백준] 1759번(python 파이썬)

조합관련 문제이다. itertools의 combinations을 사용해도 되지만 백트래킹으로 풀었다. 사실 간단한 문제인데 문제를 제대로 읽지 않았다.. 처음에 대충 읽고 푼게 모음만 하나 이상이면 된다고 생각하여 풀었는데 오답이 나와서 다시 문제를 보니 자음도 최소 2개 이상 나와야 한다고 적혀있었다. 첫번째 잘못 이해.. 그리고 왠지 모르겠지만 모음이 연속으로 나오면 안된다고 적혀있지도 않는데 연속으로 나오지 않도록 풀었다... 두번째 잘못 이해.. 문제를 꼼꼼히 보자.. l, c = map(int, input().split()) cipher = list(input().split()) visited = [False] * c vowels = ['a', 'e', 'i', 'o', 'u'] cipher.s..
알고리즘/백준 2021. 2. 4. 14:34
[백준] 16968번(python 파이썬)

백트래킹 관련 문제여서 백트래킹으로 풀었는데 생각해보면 경우의 수를 구하는 문제라 백트래킹으로 풀지 않아도 된다 중복 형식일경우 경우의 수를 체크해주면된다.. ex) dd : 10*9 ddd: 10 * 9 * 10 cc : 26 * 25 ccc: 26 * 25 * 26 cdc : 26 * 10 * 26 이런식.... car_number = list(input()) result = 0 def BackTrack(depth, dup): global result if depth == len(car_number): result += 1 return if car_number[depth-1] != car_number[depth]: dup = -1 if car_number[depth] == 'c': temp = [Fa..
알고리즘/백준 2021. 2. 4. 00:07
[백준] 6603번(python 파이썬)

백트래킹의 쉬운 문제이다 숫자가 6개인 조합을 구해주면 된다. K와 S가 합쳐진 list를 입력받는데 이차원 list로 풀어도 되지만 동적 변수명 할당이라는 것을 봐서 이번에 이렇게 풀어봤다. 동적 변수명할당, 사용 i = 1 while True: globals()['lotto{}'.format(i)] = list(map(int, input().split())) if globals()['lotto{}'.format(i)][0] == 0: break globals()['visited{}'.format(i)] = [False] * (globals()['lotto{}'.format(i)][0] + 1) i += 1 lotto1, lotto2, ... visited1, visited2, ... lotto1 ->..
알고리즘/백준 2021. 2. 3. 16:21
[백준] 14889번(python 파이썬)

풀이 먼저 백트래킹을 이용하여 n/2 개의 수를 이루는 조합을 구한다. ex) n = 4 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 백트래킹을 이용하여 쉽게 구할수 있다. 구하는 도중 새로운 숫자가 들어오면 원래 있던 숫자와 S[i][j] + S[j][i]를 구한다. ex) (1) 에서 2가 들어옴 (1, 2) 이때 S[1][2] + S[2][1]를 구해주고 결과값을 매개변수로 넘겨줌 ex) (1, 2) 에서 3이 들어옴 (1, 2, 3) 이때 1,2에 대한 합은 구해줬으니 그 값과 S[1][3] + S[3][1], S[2][3] + S[3][2]을 반복문을 통해 더해줌... (말로 설명하는게 진짜 어려운거같다...) 이렇게 구하면 각 조합별로 구한값이 deque()에 들..
알고리즘/백준 2021. 2. 3. 00:48
[백준] 14888번(python 파이썬)

연산자에 대한 백트래킹 문제이다. 사실 푸는법은 바로 떠올라서 금방 풀었지만 정답이 제대로 나오지 않았다.. 몇시간 동안 디버깅을 한 결과 음수 // 양수 를 하면 정수로 변환되는데 이때 내림을 해서 변환하는거 같다.. -1//3 결과가 -1로 나왔음... -2//3 결과도 -1로 나옴 풀이 연자를 확인하면서 재귀를 실행한다. 중복해서 연산자가 있을경우 해당 연산자에 대해서 한번만 실행해도된다. 처음에 중복해서 실행하니까 실행 시간이 오래 걸렸다... 처음 풀이 n = int(input()) number = list(map(int, input().split())) operator = list(map(int, input().split())) result_max = -1e9 result_min = 1e9 d..
알고리즘/백준 2021. 2. 2. 18:53
[백준] 2580번(python 파이썬)

백트래킹으로 구현할 수 있는 문제이다. 우선 index 0 ~ 80 의 칸을 검사한다. 해당 칸이 빈칸일경우 해당 칸에 들어갈 수 있는 숫자를 구한다. def AbleNumber(n, m): ableNumber = [1, 2, 3, 4, 5, 6, 7, 8, 9] for i in range(9): if graph[n][i] in ableNumber: ableNumber.remove(graph[n][i]) for i in range(9): if graph[i][m] in ableNumber: ableNumber.remove(graph[i][m]) sub_n = n // 3 sub_m = m // 3 for i in range(sub_n * 3, sub_n * 3 + 3): for j in range(sub..
알고리즘/백준 2021. 1. 29. 01:37
[백준] 9663번(python 파이썬)

NxN크기의 체스판이 주어졌을때 퀸을 서로 공격할 수 없게 N개 놓을 수 있다. N개를 놓을 수 있는 경우의 수를 구하는 문제인다. N개를 놓을 수 있다는 것은 한 행에 한개씩 놓을 수 있으면 된다는 소리이다. 퀸은 대각선, 열, 행 이렇게 움직일 수 있다. 즉, 어떤 위치에 퀸이 놓여지면 해당 대각선, 행, 열은 더이상 다른 퀸을 놓을 수 없게 된다. 해당 행에서 열을 순회하면서 놓을수 없는지 판단하며 상태 트리를 만들게 된다. ex) 퀸이 0,0에 있다면 0,0에 퀸을 놓았다면 1,2에 놓을 수 있다. 1,2에 퀸을 놓았는데 행이 2인 곳에 퀸을 놓을 수 있는 자리가 없기 때문에 이전 상태로 올라간다. 1,3에 퀸을 놓으면 2,1에 퀸을 놓을 수 있다. 2,1에 퀸을 놓았는데 행이 3인 곳에 퀸을 놓..
알고리즘/백준 2021. 1. 28. 17:30
[백준] 15657번(python 파이썬)

입력으로 n개의 숫자를 임의로 받는다. 이를 list형태로 저장하고 숫자가 작은 것부터 탐색을 해야 하기 때문에 오름차순으로 정렬을 한다. 이전 방문 노드보다 같거나, 큰 숫자를 append한다. ( if depth == 0 or solve[depth - 1]
알고리즘/백준 2021. 1. 10. 19:35
이전 Prev 1 ··· 17 18 19 20 21 22 23 Next 다음