코딩관계론

문제 이해하기조교들이 새로운 보안 시스템을 설치하기로 했습니다. 이 시스템은 알파벳 소문자로 이루어진 암호를 사용하며, 최소 한 개의 모음과 최소 두 개의 자음이 포함되어야 합니다. 또한 알파벳은 증가하는 순서로 배열되어야 합니다. 주어진 C개의 문자로 가능성 있는 암호를 구하는 프로그램을 작성해야 합니다.  문제 해결 방법 설명하기1. 모든 알파벳을 조합해야 합니다.아래의 코드를 사용하면 모든 조합을 구할 수 있습니다.def possible_passwords(length, num_chars, characters): results = [] combinations_list = list(combinations(characters, length)) 2. 조건검사만들어진 문자열 조합에서 모음과 자음의..

문제 이해하기n이 주어지면 그 중에 올바른 괄호쌍이 몇 개 있을 수 있는지 찾는 문제였다.올바른 괄호쌍이란 ()()()와 같이 모두 닫친 괄호를 의미한다.문제 해결 방법 설명하기1.가지치기n이 28(14 * 2)이기 때문에 완전탐색은 제한시간 내에 풀 수 없다. 따라서 시간을 줄이기 위해서 DP를 선택하던가 탐색하지 않아도 실패하는 경우를 발견해서 탐색을 줄여야 한다. 필자는 가지치기를 선택했고, 그 조건에 탐색 시점에서  남은 '(' 의 개수가 남은 ')'의 개수보다 많다면 탐색을 멈추도록 했다. 왜냐하면 닫친 괄호가 더 적게 남았다면  '(())))" 다음과 같은 상황이기 때문이다. if left_bracket > right_bracket: return 0 2. 완전탐색또한 항상 남..

문제 이해하기 아래의 그림과 같이 게임 보드와 테이블이 주어지는데 테이블의 블럭들을 사용해서 게임보드에 최대한 채워넣어주면 된다. 단 테이블에 있는 블록을 게임보드에 채워 넣을 땐 주위에 빈 칸이 있으면 안된다는 몇 가지의 조건을이 존재합니다. 문제 해결 방법 설명하기 1. 테이블에서 블럭의 모양을 추출한 후 roate 배열을 저장 블럭들의 회전 배열을 만들기 위해선 블럭의 모양을 알아야 합니다. 이를 위해서 저는 BFS를 사용해 블럭들을 상대좌표로 변환했습니다. 코드를 보면 연결된 블록을 찾기 위해서 절대좌표를 사용해 BFS탐색을 진행합니다. 만약 인접한 블록이 발견됐다면 해당 좌표를 상대 좌표로 변환해줍니다. def bfs(x, y, board, visited, choice = 0): queue = ..

문제 이해하기 N개의 주사위가 주어지고, 해당 주사위에는 6개의 면에 랜덤한 숫자들이 적혀있음 이 N개의 주사위 중 N/2를 A가 가져가고, 나머지를 B가 가져가고 이렇게 가져간 주사위 중 승률이 가장 높은 주사위를 반환해야함 문제 해결 방법 1. 주사위 선택을 어떻게 하냐에 따라서 결과 값이 달라지기 완전탐색을 진행해야 합니다. 파이썬에서는 combinations 함수를 통해서 주사위 조합을 구할 수 있습니다. combi = list(combinations(range(0, len(dice)), n)) 2. 내가 선택한 주사위에서 나올 수 있는 면들의 조합, 상대 방이 선택한 주사위에서 나올 수 있는 면들의 조합을 구해야 합니다. for my_dice in combi: enemy_dice = list(s..

아이디어 도출 방법 아래의 목표를 달성하기 위해서는 각 이모티콘에 적용할 할인률에 대한 모든 경우의 수를 계산해야 한다. 왜냐하면 어떤 이모티콘에 무슨 할인률을 적용하는지에 따라서 1번과 2번 목표의 값이 달라지기 때문이다. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것. 이모티콘 판매액을 최대한 늘리는 것. 각 이모티콘에 대해서 각각의 할인률을 조합하기 위해서 카타시안 곱을 사용한다. 카타시안 곱이란 간단히 말하면 모든 조합을 구하는 것이다. A ={1, 2, 3}, B = {5, 6, 7} A X B의 결과는 {1, 5}, {1, 6}, {1, 7}, {2, 5}, {2, 6}, {2, 7}, {3, 5}, {3, 6}, {3, 7}이 된다. 우리의 경우 각 이모티콘에 적용할 할인률만 구하면 되기..

링크 순위검색 풀이 "주어진 문자열을 어떤 방식으로 split할 것인가?" 완전탐색을 이용해 풀려고 했으니 특정 문자열을 내가 원하는 형식으로 만드는 것이 가장 중요하다. 먼저 주어진 query가 info 형식으로 변환될려면 " and" -> ""로 변경한 후 split(" ")을 하면 된다. "후보 쿼리는 어떤 방식으로 생성한 것인가?" 먼저 후보 쿼리를 직접 만들면 몇 개의 후보가 나올 수 있을지 생각을 해보자. 경우의 수는 두 가지 임으로 2 x 2 x 2 x 2 = 16개의 후보가 생성된다. 그럼 어떤 방식으로 생성할 것인가 조합함수를 이용해서 해당하는 인덱스를 '-' 문자열로 변경하면 모든 후보군을 생성할 수 있다. "정렬된 리스트에서 특정 값을 빠르게 찾는 방법" 이분 탐색을 수행하면 된다. ..