21610번: 마법사 상어와 비바라기 (acmicpc.net) 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net - 구현문제로 조건에 따라 순서대로만 한다면 큰 문제없이 풀리는 문제다. - 구름 생성에서 구름이 소멸한 자리인지 체크하기 위해 in 연산자를 사용했는데, 해당 문제에서는 중복되는 구름의 좌표가 없기 때문에 set을 이용했다. in 연산자는 list에서 시간복잡도는 O(n)이지만 set에서는 O(1)이기 때문에 조금이라도 시간을 줄여보고자 set을 이용했다. import sys input = s..
코딩테스트 연습 - 무인도 여행 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 전형적인 bfs문제였다. - 2차원 배열을 탐색하면서 땅인 경우를 찾고 연결된 무인도를 찾는다. - 탐색하면서 배열에 적힌 식량 값을 누적한다. - 더 이상 이어진 곳이 없다면 answer에 추가한 후 다음 지역 탐색 - 무인도가 존재하지 않는 다면 -1을 담아 return from collections import deque def find(island, sy, sx, w, d): cnt = int(island[sy..
코딩테스트 연습 - 호텔 대실 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 이러한 유형의 시간문제는 문제에서 주어지는 시각의 제일 작은 단위로 변환하여 list로 만들어서 문제를 푸는 방식이었던 것 같다. - 이 문제에서는 시간:분 이기 때문에 시각을 0부터 시작하여 11시 59분까지를 분으로 만들어 주었다. - 입력값을 분으로 변환 후 24시가 넘어가는 것은 주어진 조건으로 해결하고 대실 하는 시간에는 체크해준다. - 이때 청소시간에 이용이 불가능하기 때문에 대실시간에 함께 포함시킨다. de..
20056번: 마법사 상어와 파이어볼 (acmicpc.net) 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net - 2차원 배열로 진행하면서 헤매다가 fireball의 정보의 좌표를 key, 좌표에 있는 파이어볼 정보를 list로 만들어 풀었더니 쉽게 구현이 가능했다. - '행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.'는 파이어볼이 이동시 행 또는 열의 좌표가 N-1번, N번, 1번, 2번 이런 식..
21608번: 상어 초등학교 (acmicpc.net) 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net - 삼성 기출문제는 주로 구현 문제에 코드가 길어서 헷갈리지 않게 주석을 달거나 메모해 가면서 진행하는 게 좋은 것 같다. - |r1 - r2| + |c1 - c2| = 1 => 인접한 칸(상하좌우) - dict에 학생 번호(key), 좋아하는 학생 번호(value)로 받아 정리한다. ※ Python 3.6 버전부터는 dict에 순서를 가지고 있다. 대부분 코딩테스트에서 Python 3.6 버전 이상..
코딩테스트 연습 - 인사고과 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 점수의 합으로 석차를 확인하기 때문에 점수의 합이 완호의 점수보다 이하인 경우는 확인할 필요가 없다. - 두 가지 점수중 하나를 내림 차순, 나머지는 오름차순으로 정렬한다. - 한 가지 점수를 내림 차순으로 정렬했다면 나머지 하나의 점수는 계속 커져야 인센티브를 받을 수 있는 조건이 성립한다. def solution(scores): answer = 1 wh = scores[0] wh_score = sum(wh) score..
코딩테스트 연습 - 광물 캐기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 가지고 있는 곡괭이 * 5개까지만 체크 - 입력된 광물 list를 5개씩 어떤 광물인지 카운팅 하여 재정의 - 카운팅한 광물 list를 우선순위(다이아몬드 - 철 - 돌)에 따라 정렬 - 곡괭이도 마찬가지로 다이아몬드 - 철 - 돌 순서로 사용. 모두 소진 시 다른 재료 곡괭이 사용 def solution(picks, minerals): answer = 0 num = {'diamond': 0, 'iron': 1, 'st..
9084번: 동전 (acmicpc.net) 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net - 각각의 동전들이 1 ~ m원까지 만들 수 있는 곳의 경우의 수를 구한다. - i-coin을 만드는 값이 존재하는 경우 - dp[i] = dp[i] + dp[i-coin] - 존재하지 않는 경우는 그대로 유지 import sys input = sys.stdin.readline T = int(input()) for _ in range(T): n = int(input()) # 동전의 가지수 coins = ..
코딩테스트 연습 - 고고학 최고의 발견 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 질문하기의 힌트를 참고했다. 4번이상 회전은 하지않는다는 점과 첫째 줄에 대한 경우의 수만 체크하면 된다는 점이다. 이를 이용하여 코드를 작성했다. 첫번째 줄에 대한 경우의 수를 만들기 위해 중복순열을 이용하여 case를 만들며 체크를 했다. 그리고 시간을 줄이기 위해 깊은 복사는 slicing으로 진행을 했다. 이전 까지는 deepcopy를 사용하여 깊은 복사를 진행했지만 slicing이 더 빠르다는 것을 스터디..
코딩테스트 연습 - 풍선 터트리기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에는 그냥 생각나는 대로 다 해본 것 같다. 하지만 시간이 오래 걸리고 아이디어가 떠오르지 않아 접근법 힌트를 보고 풀게 되었다. 좌 -> 우 방향으로 최솟값을 갱신해 가며 answer에는 갱신되는 지점의 값을 추가한다. 마찬가지로 우 -> 좌 방향으로 최솟값을 갱신해 가며 answer에 갱신되는 지점의 값을 추가한다. set을 통해 중복된 지점을 제거한 후 개수를 return 한다. def solution(a): ..
