D36CHOI

링크 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를 통해 삼각형 배열의 움직이는 방향을 지정했다. 삼각형을..

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..

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 에 방문한 노드의 번..

문제 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 해주는 ..

문제 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..

문제 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net 분류 구현과 시뮬레이션 아이디어 설명대로 구현하되, DFS 모델에서 백트래킹이 없다고 보면된다. 다음 경우의 수를 찾으면 바로 break 걸어서 다른 경우의 수를 큐에 추가하지 않도록 해야한다. 문제를 꼼꼼히 읽지 않아 후진의 경우 를 코드로 구현하지않아서 이거 왜안돼?? 만 외친 채 40분정도를 날린 기분이다. 구현문제는 기본적으로 문제를 자아아알 읽는것이 정답의 길이다. 방향전환과 진행..

문제 www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변� www.acmicpc.net 테마 브루트포스 아이디어 테트로미노들은 기본모양에서 90도씩 회전, x/y축 반전(뒤집기) 등이 가능하다. 네모의 칸수는 총 4칸. 돌리고 뒤집고 돌리고 뒤집고 ... [[0,0,0], [0,0,0], [0,0,0]] 3*3 이내의 좌표로 모든 테트로미노의 좌표가 표현 가능하다. 무식하지만 총 19개의 테트로미노 경우의 수를 'tetrominos' 배열에 저장해 활용했다. N*M 배열에서 각 i행j열 좌..