Dev Note

- 블로그 찾아보면 비트마스킹으로 풀었다고 하는데 그게 더 효율적일지도 모르겠다. - 본인은 set() 자료형과 배열, 부분집합 subset()을 활용하여 풀었다. - 3중 for문이라니... ㅠㅠ;;; ;; (비공개를..해야하나..) - 문제를 이해하는게 어려웠다. 특히 최소성 부분에서 subset()의 개념을 생각하지 못하고 중복하는 건 다 걸러버리도록 로직을 짜서 처음부터 뜯어고쳐야 했다. - 시간이 굉장히 오래 걸렸지만.. 그래도 혼자 힘으로 구현하긴 했다. 실전이었으면 곤란했을 듯 하다. from itertools import combinations def is_duplicate(columns, relation): """ columns 가 (1, 2)라면 1번과 2번을 합친 값을 구하고 중복확..

문제 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대 www.acmicpc.net 처음 풀이 pop()으로 풀었는데, 우선순위큐를 활용하는 방식이 더 일반적인 것 같다. arr = [64] x = int(input()) while sum(arr) != x: if sum(arr) > x: target = arr.pop() arr.append(target//2) arr.append(target//2) if sum(arr[:len(arr)-1]) >= x: arr.pop() else: pass else: result = 1 result =..

1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net # 배열에서 최댓값을 구한다. # 맨 앞에 최댓값이 올때까지 큐를 돌린다. # 맨 앞에 최댓값이 오면 카운트를 1 증가시킨다. 그 값이 타겟이면 카운트를 반환하고 종료한다. # 뺀 값이 타겟이 아니면 그 다음 인덱스부터 위의 단계를 반복한다. 문제를 어떻게 풀지는 알았는데, 구현이 생각보다 바로 되지 않았다. 반례케이스에 걸리지 않으려면 얼렁뚱땅 풀면 안되고 while문과 if 조건문 구조를 미리 짜야 한다. 위의 흐름을 순서도를 이용해서 도식화하면 다음과 같다. ..

1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제포인트 정점을 돌면서 dfs 실행횟수를 구한다. 재귀 제한을 풀어준다. 에러원인 델타탐색 돌때 새로운 변수를 사용하지 않고 i,j 를 써서 for문을 돌 때 기존의 i, j 가 갱신되어버렸다. for문을 돌때마다 다시 원래 위치로 리셋되어야 하므로 새로운 변수를 사용해야 한다. 해결 nx, ny로 새롭게 변수명을 지정해주었다. # 이차원배열의 정점을 돌면서 dfs 실행한다. 방문했으면 건너뛴다. dfs 실행횟수만 계산하면된다. 재귀 제한 풀어주어야한다. import s..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net https://www.acmicpc.net/problem/2667..

코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 이해도 ★★☆☆☆ 접근방법 처음에는 이라 생각해서, 작업 소요 시간이 짧을수록 유리하다고 생각해 작업 소요 시간을 기준으로 정렬하였다. 대기시간의 합을 최소로 만들도록 하고 (대기시간 + 총작업시간 // 3) 하면 되겠지..라고 순진한 생각을 했다.(레벨 3인지 몰랐지) 그런데 처음 시작하는 일은 작업요청 시점이 작은 일부터 시작하는 것이어서 거기서부터 꼬이기 시작했다...torr.....

소수란? 1보다 큰 자연수 중 1과 자신만을 약수로 가지는 수 시간복잡도 O(N)인 소수 판별법 1보다 큰 자연수가 아닌 경우 걸러준다. 2부터 해당 수 - 1 까지 돌면서, 나누어 떨어지면 소수가 아니므로 걸러준다. 이 때 시간복잡도는 해당 숫자 - 1 까지 확인하므로 O(n)이다. def isPrime(number): if number in (0, 1): return False for i in range(2, number): if number % i == 0: return False return True 시간복잡도 O(√N) 인 소수 판별법 숫자가 15 이라면 1, 3, 5, 15 이 약수인데 이때 루트 15 (3,xx) 까지만 확인해도 된다. 숫자가 4이라면 1, 2, 4 이 약수인데 루트 4 (2..

코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 접근방법 학생별로 찍는 배열을 만들어주고, 카운트 초기화한다. 문제를 돌면서 정답을 확인하고 맞으면 카운트를 1 증가시킨다. 이 때, 나머지로 인덱스를 활용하는 것이 포인트이다. (문제 7번이라면 s1의 경우 6(idx) %5 =1(idx) 번째 정답 확인) 학생 순서별로 정답수를 넣은 배열을 돌리면서 최댓값이 나오면 결과 배열에 추가한다. def solution(answers): s1 = [1, 2, 3, 4, 5] s2 = [2, 1, 2, 3, 2, 4, ..