티스토리

Dev Note

검색하기

블로그 홈

Dev Note

ninefloor-design.tistory.com/m

lluna 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[프로그래머스] 2019 카카오 블라인드 #3 후보키 - 블로그 찾아보면 비트마스킹으로 풀었다고 하는데 그게 더 효율적일지도 모르겠다. - 본인은 set() 자료형과 배열, 부분집합 subset()을 활용하여 풀었다. - 3중 for문이라니... ㅠㅠ;;; ;; (비공개를..해야하나..) - 문제를 이해하는게 어려웠다. 특히 최소성 부분에서 subset()의 개념을 생각하지 못하고 중복하는 건 다 걸러버리도록 로직을 짜서 처음부터 뜯어고쳐야 했다. - 시간이 굉장히 오래 걸렸지만.. 그래도 혼자 힘으로 구현하긴 했다. 실전이었으면 곤란했을 듯 하다. from itertools import combinations def is_duplicate(columns, relation): """ columns 가 (1, 2)라면 1번과 2번을 합친 값을 구하고 중복확.. 공감수 0 댓글수 0 2022. 7. 17.
[Baekjoon] 1094. 막대기 (비트마스킹) 문제 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 =.. 공감수 0 댓글수 0 2021. 12. 27.
[Baekjoon] 1966. 프린터 큐 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net # 배열에서 최댓값을 구한다. # 맨 앞에 최댓값이 올때까지 큐를 돌린다. # 맨 앞에 최댓값이 오면 카운트를 1 증가시킨다. 그 값이 타겟이면 카운트를 반환하고 종료한다. # 뺀 값이 타겟이 아니면 그 다음 인덱스부터 위의 단계를 반복한다. 문제를 어떻게 풀지는 알았는데, 구현이 생각보다 바로 되지 않았다. 반례케이스에 걸리지 않으려면 얼렁뚱땅 풀면 안되고 while문과 if 조건문 구조를 미리 짜야 한다. 위의 흐름을 순서도를 이용해서 도식화하면 다음과 같다. .. 공감수 0 댓글수 0 2021. 12. 11.
[Baekjoon] 1012. 유기농 배추 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제포인트 정점을 돌면서 dfs 실행횟수를 구한다. 재귀 제한을 풀어준다. 에러원인 델타탐색 돌때 새로운 변수를 사용하지 않고 i,j 를 써서 for문을 돌 때 기존의 i, j 가 갱신되어버렸다. for문을 돌때마다 다시 원래 위치로 리셋되어야 하므로 새로운 변수를 사용해야 한다. 해결 nx, ny로 새롭게 변수명을 지정해주었다. # 이차원배열의 정점을 돌면서 dfs 실행한다. 방문했으면 건너뛴다. dfs 실행횟수만 계산하면된다. 재귀 제한 풀어주어야한다. import s.. 공감수 0 댓글수 0 2021. 12. 9.
DFS & BFS 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.. 공감수 0 댓글수 0 2021. 12. 8.
[프로그래머스][힙] 디스크 컨트롤러 (211114) 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 이해도 ★★☆☆☆ 접근방법 처음에는 이라 생각해서, 작업 소요 시간이 짧을수록 유리하다고 생각해 작업 소요 시간을 기준으로 정렬하였다. 대기시간의 합을 최소로 만들도록 하고 (대기시간 + 총작업시간 // 3) 하면 되겠지..라고 순진한 생각을 했다.(레벨 3인지 몰랐지) 그런데 처음 시작하는 일은 작업요청 시점이 작은 일부터 시작하는 것이어서 거기서부터 꼬이기 시작했다...torr..... 공감수 0 댓글수 0 2021. 11. 14.
소수 판별하기 소수란? 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.. 공감수 0 댓글수 0 2021. 11. 13.
[프로그래머스][완전탐색] 모의고사 (211109) 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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, .. 공감수 0 댓글수 0 2021. 11. 9.
heappush vs. heapify 왜 다를까 / 힙 자료구조 문제를 풀다가 궁금증이 생겼다. 같은 배열을 heapq 모듈을 사용하여 heap 자료구조를 만드는데 heappush 방식과 heapify 방식의 결과가 다르다. 힙(heap)이란? 힙은 "부모 노드가 자식보다 작거나 같은 값을 갖는 이진 트리" 이다. 힙은 "0부터 요소를 셀 때, 모든 k에 대해 a[k] 공감수 0 댓글수 0 2021. 11. 2.
[Programmers][그리디] 조이스틱 python (211031) 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 이해도 ★☆☆☆☆ 접근방법 왜 이 문제가 그리디 문제일까? 생각해보았다. 그리디 문제인 이유는, 상하 움직이고 좌우 움직일 때 덜 움직이는 방향을 선택해야 하기 때문이다. 1. 상 - 하 방향의 관점 A 부터 오름차순으로 알파벳을 찾는게 빠를지, Z부터 내림차순으로 찾는게 빠를지 비교한다. 각 알파벳마다 상하조정 중 min 값으로 최소 횟수를 담아두는 배열을 만든다. 2. 좌 - 우 방향의 관점 방법 1) 왼쪽에서 오른쪽으로만 이동하는 경우 .. 공감수 0 댓글수 0 2021. 10. 31.
[백준][2075][우선순위큐] N번째 큰 수 python (211030) https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이해도 ★★☆☆☆ 접근법 반복문 접근하면 메모리 초과가 나서 우선순위 큐를 구현해야 한다. 우선순위 큐는 힙으로 구현한다. 한 행씩 진행한다. 힙이 비어있다면 푸시하고, 비어있지 않은데 가장 작은 수보다 큰 수가 나오면 푸시하고, 추가된 힙에서 가장 작은 수를 pop 한다. 하나씩 추가했다 뺏다를 반복하므로 가장 큰 수부터 N개의 숫자가 힙에 담겨있다. 그 중 가장 작은 수를 출력한다. 왜 메모리 초과 .. 공감수 0 댓글수 0 2021. 10. 31.
[Programmers][해시(Hash)] 완주하지 못한 선수 python (211028) 문제 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 이해도 ★★☆☆☆ 소감 이름 갯수(1~20개 알파벳 소문자), 동명이인 여부에 낚여서 헤매었다. 이 문제에서는 필요가 없었다. 해시를 어떻게 적용해야할지 고민이 되어서 쉬운 문제인데도 접근이 어려웠다. 인덱스를 비교해도 되고, 해시맵을 사용해도 된다. 방법 1. 반복문 돌며 인덱스 비교하기 두 리스트의 인덱스를 비교해서 해당 값이 다르면 완주를 못한 사람임을 알 수 있다. 먼저 인덱스를 비교하기 위해 각 리스트를 정렬해야 한다. 원본 리.. 공감수 0 댓글수 0 2021. 10. 28.
[Programmers][힙(Heap)] 더 맵게 python (211027) 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 이해도 ★★★☆☆ 소감 힙 자료구조에 대해 알게되었다. 파이썬 힙큐(heapq) 모듈을 사용하여 구현하는 방법을 알게 되었다. 힙을 만드는 방법 방법 1. 빈 리스트 생성 후 heappush 함수로 넣기 방법 2. heapify 함수로 리스트를 바로 힙으로 바꾸기 -> 처음에 이 두 개를 같이 써서 시간초과가 났었다. heapify 사용할 경우, 새로운 변수에 넣는게 아니라 리스트를 힙 자체로 변환한다는 점에 주의하자! heapify 하면 기존 리스.. 공감수 0 댓글수 0 2021. 10. 27.
정렬 알고리즘 정리&비교 (진행중..) https://www.toptal.com/developers/sorting-algorithms/ Insertion Sort - Sorting Algorithm Animations Animation, code, analysis, and discussion of insertion sort on 4 initial conditions. www.toptal.com 시간복잡도 빠르기 비교 O(1) > O(logN) > O(N) > O(NlogN) > O(n^2) 시간복잡도 비교 선택 정렬 삽입 정렬 버블 정렬 병합 정렬 퀵 정렬 힙 정렬 카운팅 정렬 시간복잡도(평균) n^2 n^2 n^2 nlogn nlogn nlogn n 시간복잡도(최악) n^2 n^2 n^2 nlogn n^2 nlogn n 가장 빠른 경우 일정.. 공감수 0 댓글수 0 2021. 10. 25.
계산기에서 Stack을 활용하는 방법 Intro stack 을 활용하면 infix notation을 postfix notation으로 변환할 수 있다. 1972년에 도입된 최초의 휴대형 계산기 HP-35는 postfix notation을 기반으로 계산한다. 당시에 괄호를 처리하는게 어려웠기 때문이다. 일단 postfix notation으로 변환하고 나면 계산기 입장에서는 계산이 쉬워진다. 왼쪽부터 차례대로 읽는다. (Read the expression from left to right) 현재 요소가 피연산자(숫자)이면 스택에 넣는다. (If current element is a value (e.g. Integer) push it to the stack) 연산자(operator)이면 마지막 두 요소를 꺼내 (pop last two operan.. 공감수 0 댓글수 0 2021. 10. 22.
[SWEA][stack] 4866_괄호검사 (211019) 이해도 ★★★★★ 문제 접근방법 stack 이 빌 때까지 반복하며 여러 경우의 수를 처리한다. 스택이 다 비면 1, 그렇지 않으면 0, 중간에 여러 경우의 수에 걸리면 0을 출력한다. left 리스트의 인덱스와 right 리스트의 인덱스가 일치하면 짝이 맞는 괄호이다. [경우의 수] 1. 스택은 비어있는데 우측 괄호가 나온 경우 ex. ) or } 2. 스택의 마지막 괄호와 다음 괄호의 인덱스가 다른 경우 ex. ({) 3. data를 다 돌았는데 stack이 남아있는 경우 ex. ) , } , )} , { ,...etc 나의 코드 while 반복문 사용 left, right 분리 T = int(input()) for tc in range(1, T+1): data = list(input()) left =.. 공감수 0 댓글수 0 2021. 10. 19.
[SWEA][stack] 4875_미로 (211018) 이해도 ★★★☆☆ 문제 접근방법 [공통] 함수에서 이차원 배열과 시작점의 x 및 y 좌표를 파라미터로 사용한다. 델타 탐색으로 진행한다. 이차원의 visited 배열(0 또는 False)을 만들어 방문처리한다. 벽을 빠져나가지 않도록 처리한다.(추가 벽을 세우거나, 델타 범위를 제한한다.) [다양한 방식] 1. DFS 사용 1-1. 스택 사용하여 반복문으로 구현 1-2. 재귀함수로 구현 2. DFS 사용하지 않고 구현(스택.pop()대신 좌표를 감소시킴) 나의 코드 스택 사용한 반복 DFS 구현 def dfs(board, start): visited = [[False] * N for _ in range(N)] stack = [start] while stack: curr = stack.pop() visit.. 공감수 0 댓글수 0 2021. 10. 18.
[분할정복] 합병정렬(Merge Sort) 구현 및 시간복잡도 증명하기 분할정복 알고리즘 유형중에 분할정복 유형이 있다. 문제를 부분 문제로 나누어 각 부분 문제를 해결하고, 부분 문제들의 결과를 합쳐 기본 문제를 해결하는 유형이다. 정렬 알고리즘에서 합병정렬과 퀵정렬이 이에 속하는데, 합병 정렬에 대해 알아보고자 한다. 합병정렬 크게 세 부분으로 생각하면 된다. 1. 나눈다. 2. 정복한다. 3. 합친다. 1. 나눈다. 리스트를 절반씩 나눈다. 이를 재귀적으로 실행하기 때문에 계속해서 절반씩 나누어진다. 그림에서 1~3번째 줄 과정이다. 2. 정복한다. 1.나눈다 와 같은 함수라고 보면 된다. 나누다가 길이가 1이 된다는 것은 더 이상 나눌 수 없을 뿐더러 '정렬'된 상태라는 것이다. 그러므로 이 때 결과를 return 한다. 그림에서 4번째, 가운데 과정이다. 3. 합친.. 공감수 4 댓글수 1 2021. 10. 17.
파이썬으로 순열과 조합 구현하기 (+중복순열, 중복조합) + 추가가능한 부분 [순열] 서로 자리를 바꾸어 순열을 만드는 알고리즘으로 시간복잡도 최소화 [조합] n개에서 r개를 택할 때, r의 갯수를 하나씩 줄여가며 재귀로 푸는방식 (nCr = n-1Cr-1 + n-1Cr 활용) 순열(Permutation)과 조합(Combination) 순열 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 순서대로 배열한다. 조합 : 서로 다른 n개의 원소를 가진 집합에서 r개를 선택하여 그룹을 만든다. 차이점은 순열은 수를 뽑은 후 순서를 생각해야 하지만 조합은 뽑은 것으로 끝난다는 것이다. 내장 패키지 모듈 또는 재귀로 구현할 수 있다. 순열은 어느정도 이해가 되었는데 조합은 조건부분을 아직 완전히 이해하진 못했다. 내장 패키지 모듈 사용 - 순열 from ite.. 공감수 2 댓글수 3 2021. 10. 16.
최단 경로와 다익스트라 알고리즘(Dijkstra Shortcut Path) 최단 경로란? 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 1. 다익스트라 알고리즘(Dijkstra) 음의 가중치를 허용하지 않는다. 어떤 경로로 가는게 효율적일까? 특정 시작점에서 도착점까지의 최소거리를 구하자. 시작점 0, 나머지는 INF 무한대로 배치. 갈래길을 가기 위해 cost에 원래값(현재 위치의 cost)에 앞으로 갔을때의 갚을 덮어씌운다. (갱신이 아닌 누적) 하나의 노드가 끝나면, 그 다음으로 cost가 가장 작은 node로 간다. 방문하지 않은 노드로 가는데 cost에 더해주고, 기존의 길과 비교해서 더 작은 길을 선택한다. 가장 cost가 작은 노드로 시작한다. 방문체크하고, 방문하지 않은.. 공감수 0 댓글수 0 2021. 10. 16.
서로소 집합과 MST 최소신장트리 / 프림 & 크루스칼 알고리즘 서로소 집합 서로소(상호배타) 집합(Disjoint-sets) 서로소 또는 상호배타 집합이란 서로 중복 포함된 원소가 없는 집합, 교집합이 없는 집합이다. 집합에 속한 하나의 특정 멤버(대표)로 집합을 구분하며 이를 대표자(representative)라 한다. 상호배타 집합 연산 Make-Set(x) : x 를 대표로 하는 집합을 만들어라! # 초기설정 Make-Set(a) ~ Make-Set(f) : [0, 1, 2, 3, 4, 5, 6] 또는 [a, b, c, d, e, f] : 대표는 자기자신을 가리킨다. Find-Set(x) : x 가 속한 집합의 대표원소를 알아내라! 자기자신을 가리키는 원소(=대표원소)를 만날때 까지 찾는다. Union(x, y) : x가 속한 집합과 y가 속합 집합을 합쳐라!.. 공감수 0 댓글수 0 2021. 10. 15.
[SWEA] 2814. 최장 경로 D3 BFS에 거리를 추가하는 방식으로 구현하였다. 테스트케이스 2개만 맞고 계속해서 오류가 떴다. 추가로 테스트케이스를 넣어봤는데 맞는 답이 나왔는데도 통과하지 못했다. 초기화도 했는데 무엇이 문제인지 머리가 터질 것 같다. ㅠㅠ 대부분의 사람들이 dfs로 문제를 풀어서 힌트를 얻지 못했다. 결론 : BFS 로 풀 수 없다. BFS 1차수정 (오류) 일단 따로 table 필요 없이 visited 를 숫자배열로 배치 global 로 maxV 변수를 쓰기 때문에 return 따로 해주지 않아도 된다. bfs 는 초기화시킬 필요 없을것 같고.. bfs로 풀 수 있는건가? import sys sys.stdin = open('input.txt') from collections import deque def numbe.. 공감수 0 댓글수 0 2021. 10. 14.
[graph] BFS 기본 구현 문제 접근 import sys sys.stdin = open('input.txt') from collections import deque V, E = map(int, input().split()) # 7, 8 edge = list(map(int, input().split())) # [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7] # 인접 행렬을 만든다. graph = [[0]*(V+1) for _ in range(V+1)] # (V+1 * V+1) 행렬 for i in range(E): ni, nj = edge[2*i], edge[2*i+1] graph[ni][nj] = 1 graph[nj][ni] = 1 # 무방향 그래프 # 큐와 visited 설정한다. dequ.. 공감수 0 댓글수 0 2021. 10. 13.
[graph] DFS 기본 구현 문제 접근방법 깊이 우선 탐색의 기본 알고리즘 구현 방향을 확인해보니 무방향 그래프이고 정점은 7개, 간선은 8개이다. 간선 정보는 1 2 1 3 2 4 2 5 4 6 5 6 6 7 3 7 시작 정점은 1이다. 1) 인접 행렬 또는 2) 인접 리스트로 받아올 수 있다. DFS 경로이므로 1) 재귀를 사용하거나 2) 반복문과 스택(pop메서드) 사용할 수 있다. ✅ 인접행렬 + 재귀로 구현 1-2-4-6-5-7-3 import sys sys.stdin = open('input.txt') from collections import deque V, E = map(int, input().split()) # 7, 8 edge = list(map(int, input().split())) # [1, 2, 1, 3, .. 공감수 0 댓글수 0 2021. 10. 13.
[graph] 문제유형 3가지 : 완전탐색/MST/다익스트라 1. 완전탐색 : '친구관계' 문제 A 로부터 시작해서 한 명의 친구에게만 소식을 전달할 수 있다면, 최대 몇 명의 친구가 소식을 전달받을 수 있을까? (단, 소식을 전달 받은 친구한테는 소식을 재전달 할 수 없다.) A로부터 시작해서 친구들에게 동시에 소식을 전달할 수 있다고 할 때, 가장 늦게 전달받는 사람은 누구인가? (단, 친구에게 소식을 전달하는 속도는 동일하다.) 그래프 순회란? : 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것 깊이 우선 탐색(Depth First Search, DFS) 너비 우선 탐색(Breath First Search, BFS) DFS 깊이 우선 탐색 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해 가다가 더 이상 갈 곳이 없게.. 공감수 0 댓글수 0 2021. 10. 13.
[graph] 그래프를 인접행렬 또는 인접리스트로 받아오기 Vertex 노드의 갯수와 Edge 간선의 갯수, 그리고 출발점과 연결점이 한 쌍으로 연결된 정보가 주어진다. 이때 인접행렬 또는 인접리스트로 정보를 받는다. 언제 인접행렬 / 인접리스트를 사용하나? 주어진 문제 상황에 따라 다르며 무엇이 더 좋고나쁘고, 어렵고 쉽고는 없다. 일반적으로는 노드 수가 1000개를 넘어가면 인접행렬보다는 인접리스트를 사용한다고 한다. 또한 유향그래프인지, 무향그래프인지 문제에 따라 다르므로 확인하자! # 6 8 # 0 1 0 2 0 5 0 6 4 3 5 3 5 4 6 4 V, E = map(int, input().split()) edge = list(map(int, input().split())) 인접행렬로 받기 노드 수 + 1만큼의 행렬, 0으로 구성된 이차원 리스트를 만.. 공감수 0 댓글수 0 2021. 10. 13.
[SWEA] 2105. [모의 SW 역량테스트] 디저트 카페 이해도 ★☆☆☆☆ 지못미.. 소감 DFS, 백트래킹을 사용하는 문제로 난이도 높게 느껴졌다. 위의 알고리즘을 사용하지 않고 푸는 것도 가능하다. 왼쪽과 오른쪽 갈 수 있는 거리를 구해 조건을 걸어주는 식이다. DFS, 백트래킹 이해 후 다시 도전하는 것이 좋겠다. 접근방식 유형1 방향은 한쪽 방향으로만 돌아도 괜찮다. 백트래킹으로 분기처리를 하기 => d, d+1인 이유는 두 방향(우-하 방향으로 진행중이었다면 우-하 와 좌-하) 으로 가면 되기 때문이다. map 함수를 사용하여 이중리스트 내에 있는 리스트들의 길이를 routes에 담는다. DFS 처럼 끝까지 갔다가 돌아오는건 아니고, 함수 리턴값 없이 가지치기 하며 뻗어나가는 구조이다. import sys sys.stdin = open('input.t.. 공감수 0 댓글수 0 2021. 10. 13.
[SWEA] 4012. [모의 SW 역량테스트] 요리사 (211012) 소감 [업데이트] 변수명 구체적으로 변경 : food_combination -> ingredient_combination 문제가 구체적이지 않아서 애를 먹었다. 디버깅과 문제의 문제점..! 을 짚어준 댓글이 없었다면 풀기 힘들었을 것 같다. 재료 2개를 구할 경우 (1, 2) (2, 1) 조합으로 풀면 되는데 재료가 3개일 경우 2개를 선택하는 건지, 아니면 재료 3개를 모두 선택하는건지 등에 대한 정보가 없었다. 이차원 리스트 벽 세우는걸 좀 더 깔끔하게 구현할 수 없을까..? 접근법 이차원리스트를 받아온다. 이 때 재료와 인덱스 순서를 맞추기 위해 좌측, 상단에 벽을 세운다. 전체 리스트에서 조합으로 2개 선택한다. 반복문을 돌며 음식별 맛의 합계를 구한다. 이 때, 재료를 순열로 다시 구해서 음식1.. 공감수 0 댓글수 0 2021. 10. 12.
[1-2][DP] 거듭제곱 빠르게 구현하기 다이나믹 프로그래밍 재귀적 호출을 power(x, y - 1) 대신 power(x, y // 2) 로 바꿔줌으로써 시간복잡도를 O(n)에서 O(lgn) 으로 줄일 수 있다. 홀수와 짝수를 나누어서 계산한다. # 시간복잡도 O(n) def power(x, y): if y == 0: return 1 return power(x, y - 1) * x # 시간복잡도 O(lgn) def power(x, y): if y == 0: return 1 # 계산을 한 번만 하기 위해서 변수에 저장 subresult = power(x, y // 2) # 문제를 최대한 똑같은 크기의 문제 두 개로 나눈다. if y % 2 == 0: return subresult * subresult else: return x * subresu.. 공감수 0 댓글수 0 2021. 10. 12.
[1-1][Brute Force] 투자귀재 규식이1 문제 특정 기간 중 수익이 가장 큰 기간을 찾기 # 테스트 print(sublist_max([4, 3, 8, -2, -5, -3, -5, -3])) print(sublist_max([2, 3, 1, -1, -2, 5, -1, -1])) print(sublist_max([7, -3, 14, -8, -5, 6, 8, -5, -4, 10, -1, 8])) 내 풀이 모든 경우의 수를 리스트에 추가해서 최댓값을 구함 def sublist_max(profits): profit_list = [] for i in range(len(profits)): for j in range(i, len(profits)): profit_list.append(sum(profits[i:j+1])) return max(profit_list.. 공감수 0 댓글수 0 2021. 10. 12.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.