https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 시간초과 풀이 단순하게 구현했더니 시간초과 난다 ㅎㅎ import sys input = sys.stdin.readline r, c = map(int, input().split()) board = [] for i in range(r): data = input() temp = [] for j in range(c): temp.append(data[j]) board.append(temp) dx =..
백트래킹
https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs로 풀어야 겠다고 떠올렸다 그런데 보통 입력이 숫자로 주어졌고, 나는 그래프를 표현할 때 주로 이차원 리스트를 사용했는데 각각의 node에 해당하는 공항 이름들이 문자열이다보니, 처리를 쉽게 하기 위해서는 dictionary 자료형이 낫다고 생각했다. 내가 좋아하는.. 쓰기 편한 defaultdict으로 초기화 없이 우선 정의해주고, for 문에서 각각 그래프와, visited 딕셔너리에 F..
https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 계란치는_법_jpg 2번 과정에서 백트래킹으로 풀어야겠다고 캐치를 할 수 있었다 손에 들고 있는 계란으로 다른 계란 중 하나를 치는데 그게 뭐 바로 옆에 있는 계란일 수도 있고 아닐 수 도 있음 -> 백트래킹 사용해서 계란을 쳤다가 계란을 치기 전으로 다시 back해서 문제를 풀어가야 한다 # https://www.acmicpc.net/problem/16987 n = int(inpu..
https://www.acmicpc.net/problem/2448 2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 1. 우선 graph의 원소들을 초기화 한다 ! 2. 나는 n ==3 이면 가장 기본 모양의 삼각형이므로, n==3 이면 별 모양을 넣어주는 걸로 풀었다 n==3일때의 삼각형 모양이 반복되어 만들어지기 때문이다 !! 3. n==3 일때 별을 찍고, 이 모양이 반복되므로, x좌표와 y좌표값을 찾아서 반복해 주면 되는데, 그것이 star 함수를 재귀 호출 한 부분이다 왼쪽 아래 부분, 오른쪽 아래 부분, 그리고 현재 x,y 부분을 나눠서 별을 찍는다고 ..
백트래킹 문제로 되게 유명하다면서/!??! 그래서 풀어봤다 백트래킹 유형중에 백준에서 푼사람이 가장 많은 문제이기도 하다 백트래킹이란 ? 해를 찾는 도중에 해당 노드가 해가 아니라서 막히면 되돌아가서 다시 해를 찾아가는 기법이다. 첫번째 풀이는 시간초과가 났다 dfs로 퀸을 배치하고, 배치한다음에 시뮬레이션 돌려서 퀸을 공격할 수 있는지 없는지 여부를 true , false 로 반환해서 true 값을 세려고 했다 시간 초과 판정이 떴다. 퀸을 배치하는 과정에서 조금 더 개선해볼 수 있지 않을까 ??? # 9663 N-Queen n = int(input()) graph = [[0]*n for _ in range(n)] dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, ..
https://www.acmicpc.net/status?user_id=freemjstudio&problem_id=15666&from_mine=1 채점 현황 www.acmicpc.net 두번째 예시로 생각해보자 i) 중복 제거 n = 4, m = 2 그리고 후보로 주어진 숫자들은 9 7 9 1 이다. 어처피 우리는 중복해서 같은 숫자를 선택할 수 있으므로 중복을 set() 함수를 통해 제거한 후 다시 list로 형변환한다. 그러면 9 7 1 세가지가 남는다. 비내림차순이라는 조건이 주어졌으므로 -> 오름차순으로 바꿔봅시다. 그러면 후보들을 정렬했을 때 1 7 9 가 됩니다. ii ) for문과 재귀함수 호출 우리는 이제 1 7 9 세가지 선택지가 있고 이 세가지 숫자들을 for문을 통해서 순회하며 하나씩 ..
