꾸준하게 거북이처럼

20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 이런 유형의 문제는 시뮬레이션 + 구현 문제로, 한 좌표에서 여러개의 정보가 들어가는데, 보통 dictionary나 2차원 배열을 사용한다. 아래와 같이 dictionary를 써보니 코드가 생각보다 간략해졌다. 1. 조건 - m개의 파이어볼, 방향 8방향, 처음 끝 행과 처음 끝 열 연결되어있음. - d방향 s칸 이동, 명령 k번 - 2개이상 파이어볼이 있으면 같은 파이어볼 4개로 나누어짐.(모두 방향이 짝/홀수면 0,2,4..

17140번: 이차원 배열과 연산 첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100) 둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다. www.acmicpc.net 구현 시뮬레이션 문제로, 문제 조건을 잘 체크해야한다. - 0은 정렬 X, - 정렬 하는 기준 : 등장 횟수 > 숫자 가 커지는! 순 - 크기가 달라지면 큰 행또는열 기준으로 0을 채워야함 - 행이나 열 크기가 100 넘으면 100x100으로 자르기 이 문제는 아래처럼 파이썬의 zip연산을 이용해서 열 정렬을 쉽게 할 수 있다. a = [[1,2,3], [4,5,6]] a = list(zip(*a)) print(a) # [(1,4) ,(2,5), (3..

6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 백트래킹 문제로, 알파세 사전순으로 출력은 입력받을 때, sort를 적용하면 된다. 하지만 중복된 문자열은 출력 되면 안되기 때문에 이 조건에서 고민을 했던것 같다. 시간 초과가 나지 않으려면, 중복조건은 피해야하는데 어떻게 풀 수 있을까? 'aabc' 이 입력일 때, 중복된 문자열을 피하려면, 재귀함수를 호출하며 가지가 뻗어나갈 때, 해당 depth에서 같은 문자가 가지에 포함되면 안된다. 하지만 주어진 문자열의 문자들을 다 사용해서 문자열을 만들어야하는..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 입력 개수 단위가 크다 => 완탐은 아니고, 이분탐색도 조건 찾을 때 시간초과 발생 가능,, 어떤 방법을 선택해야할까? 주어진 데이터를 순서대로 누적해서 계산하는 중에 조건에 부합하지 않은 상황이 발생시, 누적 데이터 중 가장 큰 값 또는 작은 값 제거가 필요한 경우, 힙 자료구조 (logN) 를 사용할 수 있다. 이 문제에서 현재까지 데이터 중에서 k개의 무적권은 가장 큰 수에 사용, 작은 수의 적군 일때는 병사를 소모하는 방법으로 최대 라운드 수를 구할 수 있다고 볼 수 있다. from heapq i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 이해가 잘 되지 않았던 문제다. 결론적으로 이 문제는 원소의 개수가 가장 큰 두 집합을 구하는 문제다. cards에서 임의의 숫자를 선택하여 규칙대로 만들어진 1번째로 생긴그룹 2번째로 생긴 그룹의 원소 개수의 곱 중 최대값을 알아내야함. 어떤 수를 먼저 선택해도 규칙대로 하다보면 같은 집합의 형태가 나온다! 나만 그 집합의 순서가 다를 뿐, 그 중 1번 2번 그룹 원소 개수 곱의 최대값을 알아야하니, 제일 원소의 개수가 가장 큰 것 2가지를 구하면된다. import collections def solu..

최대 그룹수를 만들어야하기 때문에, 공포도가 작은 모험가 먼저 그룹을 만들고 최소한만 그룹 조건을 만족하여 그룹을 나누면 최대 개수가 나온다. 따라서 sort를 통해 공포도가 낮은 것부터 연산을 할 수 있도록 하고, 공포도가 x인 모험가는 x명으로 구성해서 그룹에 넣는다. 예제에 입력된 공포도 값을 sort하면 1 2 2 2 3 => 1: 총 그룹 수 1개 , => 2 2: 총 그룹 수 2개, => 남은 2 3을 가지고는 그룹을 만들 수 없기 때문에(공포도가 3이므로 3이하의 공포도 모험가 한 명이 더필요) 답은 2이다. 코드 n = int(input()) arr = map(int,input().split()) arr.sort() g = 0 cnt = 0 for i in arr: cnt += 1 # 현재..

알고 있으면 좋은 2차원 배열 회전 알고리즘엠 대해서 알아보려고 한다. 가끔 문제에서 90도로 회전한 2차원 배열이 필요할 때가 있다. 오른쪽으로 90도 회전하기 Before After 1 (0, 0) (0, 2) 2 (0, 1) (1, 2) 3 (0, 2) (2, 2) 규칙을 보면 - 회전 전의 column 번호와 회전 후의 행 번호가 일치한다. - 회전 후의 열은 n - 1 에서 회전 전의 행을 뺀 값과 같다. 코드 def rotate_90(m): N = len(m) res = [[0] * N for _ in range(N)] for r in range(N): for c in range(N): res[c][N-1-r] = m[r][c] return res 90도로 바꾸는 함수를 몇 번 반복하면 180..

14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 1. 문제에서 필요한 데이터: 현재 화면에 있는 이모티콘 개수, 클립보드에 있는 이모티콘 개수, 현재까지 걸린 시간 3가지가 필요 2. 3가지를 표현할 방법: 2차원 배열 => { d[스크린에 있는 이모티콘개수][클리보드에 있는 이모티콘 개수] } => 걸린 시간 3. 주의사항: 인덱스로 개수를 표현하고 있기 때문에 배열의 인덱스가 제한 범위를 벗어나지 않도록 해야한다. ex) 1000까지 이므로 1000을 넘어가지 않도록, 삭제할 시 음수 인덱스가 나오지 않..

1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 이 문제는 stack의 LIFO 특징을 이용해서 중위 표기식을 후위 표기식으로 변환시키는 문제이다. 입력 받은 문자열을 하나씩 읽어들여 연산자들만 stack에 넣고 각 연산자들의 우선순위 규칙에 맞게 pop, append를 한다. 나머지 피연산자들은 최종적으로 답이 될 빈 문자열에 더해준다. 올 수 있는 모든 연산자: +, -, *, /, (, ) 우선순위 설정: priority = {"*": 1, '/':1, '+':0, '-':0,'(':-1} 나는 문제..

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 파이썬에는 sort 라이브러리가 있어서 아주 쉽게 문제를 풀 수 있다. 하지만, 일부 코딩테스트에서는 라이브러리 사용을 금지하는 경우도 있기 때문에 병합정렬 알고리즘을 이용해서 문제를 풀었다. 제출할 때는 pypy3로 제출해야 통과된다 def solution(arr): # 분할된 배열 길이가 1이면 정렬할 필요X 때문에 return if len(arr)