ym_coding

큐빙 문제 루빅스 큐브는 삼차원 퍼즐이다. 보통 루빅스 큐브는 3×3×3개의 작은 정육면체로 이루어져 있다. 퍼즐을 풀려면 각 면에 있는 아홉 개의 작은 정육면체의 색이 동일해야 한다. 큐브는 각 면을 양방향으로 90도 만큼 돌릴 수 있도록 만들어져 있다. 회전이 마친 이후에는, 다른 면을 돌릴 수 있다. 이렇게 큐브의 서로 다른 면을 돌리다 보면, 색을 섞을 수 있다. 이 문제에서는 루빅스 큐브가 모두 풀린 상태에서 시작한다. 윗 면은 흰색, 아랫 면은 노란색, 앞 면은 빨간색, 뒷 면은 오렌지색, 왼쪽 면은 초록색, 오른쪽 면은 파란색이다. 루빅스 큐브를 돌린 방법이 순서대로 주어진다. 이때, 모두 돌린 다음에 가장 윗 면의 색상을 구하는 프로그램을 작성하시오. 위의 그림은 루빅스 큐브를 푼 그림이다..

주사위 윷놀이 문제 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다. 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다. 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다. 말이 이동을 ..

새로운 게임2 문제 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다. 게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다. 턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동한다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에..

bisect - 이진 탐색 bisect 모듈은 이진 탐색 알고리즘을 구현한 모듈이다. bisect.bisect 함수는 정렬된 리스트에 값을 삽입할 때 정렬을 유지할 수 있는 인덱스를 리턴한다. 문제 A 학급의 학생수는 총 7명이다. 7명의 성적은 다음과 같다. [33, 99, 77, 70, 89, 90, 100] 그리고 성적에 대한 학점은 다음과 같은 기준으로 정해진다. 90점 이상 : A 80점 이상 : B 70점 이상 : C 60점 이상 : D 0~59점 : F A학급 학생들의 학점을 순서대로 구하시오. 풀이 보통 이런류의 문제는 if else를 이용한 분기문으로 풀이하지만 bisect.bisect 함수를 사용하면 보다 우아하고 간결하게 문제를 풀수 있다. 다음과 같이 코드를 작성해 보자. [파일명:..

Python array[::] 용법 간단한 파이썬 팁입니다. arr[::], arr[1:2:3], arr[::-1] 등으로 배열의 index에 접근하는 방법을 Extended Slices 라고 부릅니다. 설명 arr[A:B:C]의 의미는, index A 부터 index B 까지 C의 간격으로 배열을 만들어라는 말입니다. 만약 A가 None 이라면, 처음부터 라는 뜻이고 B가 None 이라면, 할 수 있는 데까지 (C가 양수라면 마지막 index까지, C가 음수라면 첫 index까지가 되겠습니다.)라는 뜻입니다. 마지막으로 C가 None 이라면 한 칸 간격으로 라는 뜻입니다. 예시 >> arr = range(10) >> arr [0,1,2,3,4,5,6,7,8,9] >> arr[::2] # 처음부터 끝까지..

들어가기 알고리즘 문제를 풀다 보면 시간복잡도를 생각해야 하는 경우가 종종 생긴다. 특히 codility는 문제마다 시간복잡도 기준이 있어서, 기준을 넘기지 못하면 문제를 풀어도 score가 50 이하로 나오는 경우가 많다. 찾아보니 파이썬 주요 함수, 메소드의 시간복잡도를 정리한 페이지가 있었다. (Complexity of Python Operations) 자주 사용하는 것들을 이곳에 정리하고 종종 참고하려고 한다. list OperationExampleBig-ONotes Index l[i] O(1) Store l[i] = 0 O(1) Length len(l) O(1) Append l.append(5) O(1) Pop l.pop() O(1) l.pop(-1) 과 동일 Clear l.clear() O(1..

출처:: 코딩테스트 교재 P313 분류:: 그리디알고리즘 1. 문제 이해 및 해결과정 - 입력 조건 : 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 주어집니다. (1 210 2. 풀이방법 N = list(map(str, input().strip())) result = 0 while(N): A = int(N.pop(0)) #0 if A == 0: continue if result == 0 and A != 0: result += A continue if result * A > result + A: result = result * A else: result = result + A print(result) 해설 ) 아이디어: 숫자를 사용자로부터 입력받아 리스트로 변경한다. 초기 result 값을 0으..

출처:: 코딩테스트 교재 최단경로알고리즘 분류:: 다익스트라알고리즘 1. 문제 이해 및 해결과정 입력 3 2 1 1 2 4 1 3 2 출력 2 4 첫 째줄에 도시의개수 N 통로의 개수 M 메시지를 보내고자 하는 도시 C가 있다. 둘째 줄 부터 M+1 번째 줄에 걸쳐서 통로에 대한 정보 X Y Z가 주어진다. 이는 특정 도시 X에서 다른 특정 도시 Y로 이어지는 통로가 있으며 메시지가 전달되는 시간이 Z라는 의미이다. 첫째줄 도시 C에서 보낸 메시지를 받는 도시의 총개수와 총 걸리는 시간을 공백으로 구분하여 출력한다. 2. 풀이방법 import sys from queue import PriorityQueue N, M, C = map(int , input().split()) dic_arr = {} weigh..

출처:: M기업 코딩 테스트 분류:: 플루이드 워셜 알고리즘 1. 문제 이해 및 해결과정 - N의 범위가 100이하로 매우 한정적이므로 플로이드 와셜알고리즘 이용 2. 풀이방법 #미래도시 import sys from queue import PriorityQueue INF = int(1e9) #10억 #노드의 개수 및 간선의 개수를 입력받기 n,m=map(int,input().split()) graph = [[INF]*(n) for _ in range(n)] for i in range(m): X, Y = map(int, input().split()) graph[X-1][Y-1] = 1 graph[Y-1][X-1] = 1 #비용은 0으로 초기화 for i in range(n): graph[i][i] = 0 ..

다익스트라 알고리즘 '한 지점에서 다른 특정 지점까지의 최단경로' 플로이드워셜 알고리즘 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우' 플로이드 워셜 알고리즘은 단계마다 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 따라서 O(N^3)의 시간복잡도를 가진다. [***모든 노드에서 다른 모든 노드까지]***의 최단 경로를 모두 계산한다. Floyd - Warshall 알고리즘은 다익스트라 알고리즘과 마찬가지로 “단계별로 거쳐가는 노드를 기준”으로 알고리즘을 수행한다. 다만, 매 단계마다, “방문하지 않은 노드 중” “최단 거리를 갖는 노드 찾기” 과정이 필요하지는 않다. 2D 테이블에, [최단 거리 정보]를 저장한다. 왜냐하면 [모든 노드] —> [모든 노드] 까지의 최단 경로를 ..