프로그래밍/자료구조 및 알고리즘(6)
-
[백트래킹, 백준] N과 M (1), (2) <중복을 허용하지 않는 순열, 조합>
N과 M - 1, 2의 차이 1번에서는 중복을 허용하지 않는 순열, 2번에서는 조합을 뽑는 문제이다. 1번에서는 단순히, 중복에 대해 체크하는 1차원 리스트를 만들어 플래그로 활용하면서, 재귀적으로 호출하면 쉽게 해결할 수 있다. n, m = map(int, input().split()) arr = [i + 1 for i in range(n)] selected = [False] * n result = [] def permutation(m): if m == 0 : print(*result) return for idx in range(n): if not selected[idx] : selected[idx] = True result.append(arr[idx]) permutation(m - 1) result...
2023.09.03 -
[백트래킹, 코드트리] 아름다운 수
내 코드 - 일부 케이스를 잡아내지 못했음. n = int(input()) # 1 ~ 4 의 수로, 그 중 연달아 같은 수가 나오는 숫자 - 아름다운 수 # 동일한 숫자에 대해 정확히 해당 숫자만큼 연달아 같은 묶음 (111 : 1이 1번 - 3번 / 222222222 : 2가 2번이 4번) # 1 이 1번, 2가 2번, 3이 3번 (단일 연속) # 222의 경우 22 / 21 이라서 아름다운 수가 아님...! (2가 3번 나오면 안되고, 정확히 2번 나와야 함으로 인지) # out : n자리의 아름다운 수가 몇 개인지 ? # Step 1 : n 자리의 1 ~ 4로 꾸려진 수를 먼저 출력해야 함. # Step 2 : 각 수들에 대한 아름다운 수 여부를 검사 answer = [] beautiful_num_..
2023.08.15 -
[프로그래머스] 숫자의 표현 - 파이썬 풀이
문제 설명 Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다. 1 + 2 + 3 + 4 + 5 = 15 4 + 5 + 6 = 15 7 + 8 = 15 15 = 15 자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요. 제한사항 n은 10,000 이하의 자연수 입니다. 풀이 손풀이를 간단히 첨부하겠다. 처음에는 등차수열 공식으로 접근해보려고 했는데, 이것을 프로그래밍으로 구현을 하기에 괴리감이 있었다. 🥲 두번째로는, 예시 케이스를 보며 규칙성을 확보하여, 이에 대한 수..
2023.02.14 -
[프로그래머스] Lv.0 안전지대 파이썬 코드 풀이
문제설명 다음 그림과 같이 지뢰가 있는 지역과 지뢰에 인접한 위, 아래, 좌, 우 대각선 칸을 모두 위험지역으로 분류합니다. 지뢰는 2차원 배열 board에 1로 표시되어 있고 board에는 지뢰가 매설 된 지역 1과, 지뢰가 없는 지역 0만 존재합니다. 지뢰가 매설된 지역의 지도 board가 매개변수로 주어질 때, 안전한 지역의 칸 수를 return하도록 solution 함수를 완성해주세요. 나의 풀이 핵심은, 지뢰의 좌표를 구하여서, 그 주변 8방향에 대해 지뢰를 추가적으로 설치한 후에, 지뢰가 없는 지역을 세주면 된다. 객체지향 프로그래밍 연습을 해보기 위해 아래와 같이 구현해보았다. class Mine(): def __init__(self, board): self.coord = board self..
2023.01.24 -
[자료구조, 파이썬] 리스트, 딕셔너리, 튜플(list, dict, tuple)
현재까지의 코딩테스트 문제를 풀이했던 경험으로 볼 때, 3가지 자료구조의 용례를 개인적으로 정리해보면 다음과 같다. - 리스트 : 뭘 써야할 지 모를 때, 가장 무난하게 사용하기 좋다. C++등의 배열에 해당하는 컨셉이 구현되어 있어, 인덱스에 따른 순차적인 접근이 가능하다. 예 ) a = [1, 2, 3, 'a', 'b'] >> a[1] = 2 - 딕셔너리 : 리스트와 달리, 사람이 알아볼 수 있는 자료형으로 태깅하여(해싱) 자료값에 접근이 가능하다. 또 중복값이 불가능하다. 예) b = {'name' : 'gildong', 'birth' : '2000. 01. 01', 'address' : '서울시 관악구 관악로 144'} >> b['name'] = 'gildong' - 튜플 : immutable(변..
2023.01.18 -
[프로그래머스] 코딩테스트 연습 - 이중우선순위큐 풀이 (파이썬)
문제 - 요약 명령어 수신 탑(높이) I 숫자 큐에 숫자 삽입 D 1 큐에서 최댓값 삭제 D -1 큐에서 최솟값 삭제 모든 연산 수행 후 큐가 비어있으면 [0, 0], 아니면 [최댓값, 최솟값] return - 제한사항 : operations 의 길이 : 1 ~ 1,000,000 : operations 의 원소 : "명령어 데이터" 의 형식 - 연산에서 최댓값/최솟값이 둘 이상일 경우 하나만 삭제 : 빈 큐에 데이터 삭제 연산 - 무시 - 입출력 예시 operations return ["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"] [0,0] ["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "..
2023.01.03