만족은 하되 안주하지는 말자

기록해야 기억한다

분류 전체보기 168

[python] 프로그래머스 삼각 달팽이

링크 programmers.co.kr/learn/courses/30/lessons/68645 코딩테스트 연습 - 삼각 달팽이 5 [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] 6 [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] programmers.co.kr 설명 달팽이 숫자 만들기의 삼각형 버전이다. 반시계방향으로 숫자를 채워나가야 한다. n 범위가 ~1000 이므로 n = 1000 일때의 시도횟수가 대략 몇회인지 고민을 먼저했다. n에 따른 삼각형 네모칸의 갯수는 n(n+1) / 2 와 같다. 대략 1000일때 50만번 카운팅 하면 된다. DFS/BFS 처럼, dx와 dy를 통해 삼각형 배열의 움직이는 방향을 지정했다. 삼각형을..

[python] 프로그래머스 스킬트리

programmers.co.kr/learn/courses/30/lessons/49993 코딩테스트 연습 - 스킬트리 programmers.co.kr 윈터코딩 ~2018 에 속한 문제. 시간복잡도 고려 최대 가능한 연산수가 26*26*20이기에 O(n^2) 까지의 시간복잡도여도 문제가 없을 것으로 예상된다. 코드 from collections import deque from copy import deepcopy def solution(skill, skill_trees): answer = 0 p_skill = deque([]) for c in skill: p_skill.append(c) for skill in skill_trees: if check(p_skill,skill): answer +=1 return..

[python] n진법 수를 10진법 수로, 10진법 수를 n진법 수로

10진수 정수를 1부터 9까지의 n진법으로 변환해 출력해보자. n진법 수 -> 10진법 수 num = '1001001' base = 2 answer = 0 for idx, i in enumerate(num[::-1]): answer += int(i) * ( base ** idx ) 문자열의 역순에서 base 의 자릿수승 (2진법의 경우 1,2,4,8,16, .... ) 만큼의 곱을 계속 더해 십진수로 변환함. 10진법 수 -> n진법 수 from collections import deque num=34 n=8 q = deque([]) o='' while num: num,m=divmod(num,n) o=(str(m) if m

[python] 백준 1260번: DFS와 BFS

www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 곧 있을 LG 코딩테스트에 앞서 기본기 복습 겸, 가장 기본적인 DFS / BFS 문제를 풀어보았다. 특징은 DFS 는 재귀함수가 아니라 stack 을 활용해 만들었다는 것. (기본적으로 같은 반복횟수면 시스템상 재귀방식보다 stack 이 속도가 빠르다고 한다) 그리고 기존엔 visited 배열을 True Or False 로 했다면 여기선 visited 에 방문한 노드의 번..

[python]백준 14891번: 톱니바퀴

문제 www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 � www.acmicpc.net 아이디어 구현 테마인데, 톱니바퀴를 연달아 반대방향으로 돌리는지 확인하고 돌리는 함수 do_wheels 를 만들어, 재귀형태로 풀었다. 바퀴는 4개로 고정이라서 depth가 아무리 깊어봤자 최대 2다. 4개의 톱니바퀴의 왼쪽부분과 오른쪽 부분을 상수 LEFT,RIGHT = 6,2 로 위치를 지정해놓고, 인덱스에는 변화를 주지않은채 '돌리는행동'을 queue의 앞과 끝을 pop,append 해주는 ..

[python] 코딩 테스트 약점 정리

첫 취준생으로써 몇번 코테를 보지도 않았지만 (코딜리티 2회, 라인,카카오,쿠팡,프로그래머스 코딩챌린지 끝) 그 동안의 연습 부족으로 생소했던 포인트들을 정리해 본다. 1. 시간이 나오는 문제 인풋이 [10/03 01:34:55, 10/04 13:35:22] 식의 시간 형태 리스트로 주어지는 경우 어찌할줄을 몰라 시간을 많이 날렸다. (쿠팡,카카오) python 은 이런 경우 datetime 모듈을 활용해 datetime.strftime 과 datetime.strptime 을 활용해 풀 수 있을 거 같은데 너무 생소해서 머리가 잘 안굴러가서 결국엔 못풇었다. 시간의 대소관계 비교라던지 등등을 잘 할 수 있게 연습해놓자 2. 진법 변환 문제 여러 군데에서 1,2번 문제로 나오기 좋은 테마인 것 같다. 10..

[python] 백준 6497번: 전력난

문제 https://www.acmicpc.net/problem/6497 알고리즘 최소 신장 트리, Union 아이디어 union 알고리즘인 find_parent, union_parent 를 기반으로, heapq 를 통해 거리가 최소인 순서대로 cycle이 존재하는지를 판단해 cycle 이 없는 경우엔 최적의 해임이 보장되므로 이를 추가한다. 코드 from sys import stdin import heapq def find_parent(parent,a): if parent[a] != a: parent[a] = find_parent(parent,parent[a]) return parent[a] def union_parent(parent,a, b): a = find_parent(parent,a) b = fi..