[프로그래머스] 압축 (Python)
https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 주어진 조건대로 구현하면 된다. from collections import defaultdict def solution(msg): alphabet ='ABCDEFGHIJKLMNOPQRSTUVWXYZ' answer = [] dict = defaultdict(int) for i,alpha in enumerate(alphabet): dict[alpha] = i+1 start, end, va..
2021. 11. 6.
[프로그래머스] 가장 큰 정사각형 찾기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/12905 코딩테스트 연습 - 가장 큰 정사각형 찾기 [[0,1,1,1],[1,1,1,1],[1,1,1,1],[0,0,1,0]] 9 programmers.co.kr 전형적인 DP 문제다. DP를 만족하기 위해서 1. 최적 부분 구조 (Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 한다. 이 정사각형 문제도 위의 두 조건을 만족한다. 처음엔 완전 탐색으로 풀었는데, 효율성 테스트에서 시간 초과가 나서 생각해보니 dp로..
2021. 11. 6.
[프로그래머스] 방문 길이 (Python)
https://programmers.co.kr/learn/courses/30/lessons/49994 코딩테스트 연습 - 방문 길이 programmers.co.kr set을 활용해서 풀면 된다. 주의해야 할 점은 (0, 0) -> (1, 0)으로 가는 길과 (1, 0) -> (0, 0)으로 가는 길은 동일한 길이다. 나의 풀이 from collections import defaultdict def solution(dirs): answer = 0 load = defaultdict(set) x, y = 0,0 for dir in dirs: if dir =='U': if y+1 -6: load[(x,y)].update([(x,y-1)]) load[(x,y-1)].update([(x,y)]) x,y = x,y-..
2021. 11. 4.
[프로그래머스] 쿼드 압축 후 개수 세기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr dp유형의 문제 같다 queue를 이용해서 하향식으로 풀었다. 나의 풀이 from collections import deque def check_all_number(x,y,l..
2021. 11. 4.
[프로그래머스] n^2 배열 자르기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/87390 코딩테스트 연습 - n^2 배열 자르기 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부 programmers.co.kr left와 right를 나열해서 쓰다 보면 left 값과 right 값으로 위치를 찾을 수 있다. 이를 통해 풀이하면 된다. 나의 풀이 def solution(n, left, right): answer = [] for i in range(left,right+1): answer.append(max(i//n..
2021. 11. 4.
[프로그래머스] 모음사전 (Python)
https://programmers.co.kr/learn/courses/30/lessons/84512 코딩테스트 연습 - 모음사전 사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니 programmers.co.kr 사전 규칙에 따라 알고리즘으로 구현하여 풀었다. 풀기 전에 itertools의 product를 떠올리긴 했는데 아직 익숙하지 않아서 그 방식으론 풀지 못했다. 나의 풀이 def change(vowel): next = {'A':'E','E':'I','I':'O','O':'U'} last_word = vowel[-1] ..
2021. 11. 3.
[프로그래머스] 전력망을 둘로 나누기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 전선을 하나씩 끊어 보며 bfs로 풀었다. from collections import deque def solution(n,wires): answer = 101 for i in range(len(wires)): wire = wires[:i] + wires[i+1:] graph = [[] for _ in range(n+1)] visited = [False for _..
2021. 11. 3.
[프로그래머스] 교점에 별 만들기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/87377 코딩테스트 연습 - 교점에 별 만들기 [[2, -1, 4], [-2, -1, 4], [0, -1, 1], [5, -8, -12], [5, 8, 12]] ["....*....", ".........", ".........", "*.......*", ".........", ".........", ".........", ".........", "*.......*"] [[0, 1, -1], [1, 0, -1], [1, 0, 1]] ["*.*"] [[1, -1, 0], [2, -1, 0], [4, - programmers.co.kr 2차원 평면상의 좌표와 2차원 배열의 좌표를 구하는데 시간이 오래 걸렸던 문제다...
2021. 11. 3.
[프로그래머스] 영어 끝말잇기 (Python)
https://programmers.co.kr/learn/courses/30/lessons/12981 코딩테스트 연습 - 영어 끝말잇기 3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3] 5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0] programmers.co.kr 스택을 통해 구현했다. 나의 풀이 def solution(n, words): stac..
2021. 11. 2.
[프로그래머스] 삼각 달팽이 (Python)
https://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 규칙을 찾아서 구현하면 된다. 항상 아래 , 오른쪽, 왼쪽 위 방향으로 움직인다. 나의 풀이 def solution(n): a = [['']*n for _ in range(n)] check = 0 now = [-1,0] num = 1 answer = [] for i in range(n,0,-1): x, y = now if check ==0: # down now = [x..
2021. 11. 2.
