자료구조 & 알고리즘 & cs/CodingTest (67) 썸네일형 리스트형 [python] 프로그래머스 Lv2. - [2018 KAKAO] 압축 코딩테스트 연습 - [3차] 압축 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr from string import ascii_uppercase def solution(msg): alpa=[i for i in ascii_uppercase] answer = [] i=0 while msg: tmp=msg[i] for j in range(i+1, len(msg)): if tmp+msg[j] in alpa: tmp+=msg[j] else: alpa.append(tmp+msg[j]) break answer.a.. [python] 12904- A와 B 12904번: A와 B (acmicpc.net) 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 문자열 구현 문제이다. A와B로만 이루어진 문자열 2개가 주어지고 문자열 s를 문자열 t로 바꿀 수 있는지 판별하는 문제로 가능한 연산은 두 가지가 있다. 1. 문자열의 뒤에 A를 추가 2. 문자열을 뒤집고 뒤에 B를 추가 그런데, s에서 연산을 해서 t로 만드는 방법은 너무 많지않은가? 그래서 반대로 생각해보기로 했다. 이미 완성된 문자열에서 적용했던 연산을 거꾸로 한다면? t.. [python] 11559 - Puyo Puyo 11559번: Puyo Puyo (acmicpc.net) 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 보자마자 지난번에 풀었던 카카오 프렌즈 블록 문제랑 비슷하다고 생각했다. 그래서 일부 필요한 부분의 로직을 적용하였다. 우선 접근 단계는 다음과 같다. 1. 같은 색의 뿌요들이 4개 이상 모일 경우 터뜨린다. 2. 뿌요들이 터지면 아래가 비지 않게 하기 위하여 아래로 떨어트린다. 3. * 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 연쇄는 한 번이다. 3번 .. [python] 14891 - 톱니바퀴 14891번: 톱니바퀴 (acmicpc.net) 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 문제 접근의 시작은 어떤 구조를 쓸지 파악하는 것이었다. 1. 리스트를 사용해야하는데 회전해야한다? -> deque을 사용! 2. 회전시키는 톱니바퀴를 기준으로 하여 좌우 톱니바퀴들을 돌려주어야한다. 2-1. 톱니바퀴를 돌릴지 안돌릴지 판단하자. 2-2. 톱니바퀴를 돌려야 한다면 재귀를 사용하자. 여기까지가 처음 시작한 접근이었다. 톱니바퀴의 개수는 4개로 주어져 있기 때문에 각각 비교해야하는 톱니바퀴의 맞물리는.. [python] 1976 - 여행 가자 1976번: 여행 가자 (acmicpc.net) 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net union-find를 활용하는 문제였다. 도시를 탐색하면 되었기 때문에 bfs나 dfs로도 탐색할 수 있을 것 같았는데 유니온 파인드를 최근에 공부하였기 때문에 이를 이용하여 문제를 해결하였다. import sys sys.setrecursionlimit(1000000) input = sys.stdin.readline n = int(input()) m = int(input()) parent = [i for i in .. [python] 프로그래머스 Lv2. - 기능개발 코딩테스트 연습 - 기능개발 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 스택과 큐를 활용하는 문제이다. 스택과 큐 문제는 대부분 구현 가능하기는 한데 문제에서 주어진 상황에서 스택과 큐를 어떤 방식으로 활용해야 할지 아직 감을 못잡겠다. 그래서 처음에는 for문을 3개나 사용하여 해결하였더니 복잡한 코드가 나왔다. def solution(progresses, speeds): answer = [] for i in range(len(progresses)): rest=100-progresses[i] .. [java/python] 프로그래머스 Lv2. - n진수 게임 코딩테스트 연습 - [3차] n진수 게임 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문항이 조금 복잡했다. 문제에서 가장 중요한 것은 10진수를 입력받은 n진수로 변환하는 것. 2진수, 8진수, 16진수는 파이썬 내장함수가 존재하지만 (bin(), oct(), hex()) 나머지는 직접 구현해야 했다. 다른 코드를 참고하였다. [python] * divmod(a,b) : a를 b로 나눈 몫과 나머지를 튜플 형태로 반환한다. * int(string, n) : n진수의 string을 10진수로 변환.. [python] 4803 - 트리 4803번: 트리 (acmicpc.net) 4803번: 트리 입력으로 주어진 그래프에 트리가 없다면 "No trees."를, 한 개라면 "There is one tree."를, T개(T > 1)라면 "A forest of T trees."를 테스트 케이스 번호와 함께 출력한다. www.acmicpc.net 정답률을 보고 겁을 먹었는데 간단한 문제였다. 입력으로 주어진 그래프에 트리가 있는지 판별하는 문제로, 중요한 것은 사이클이 존재하는지를 체크하는 것이다. 그래프가 존재하지 않을수도 여러개 존재할 수도 있기 때문에 union-find 알고리즘을 사용하여 루트노드를 기록하고 사이클이 존재하는지 체크하였다. 사이클이 존재할 경우 트리의 개수를 카운팅 하지 않는다. # 4803 트리 - union find .. 이전 1 2 3 4 5 6 ··· 9 다음