Study/algorithm
[softeer] [인증평가(4차) 기출] 슈퍼컴퓨터 클러스터 (python)
https://softeer.ai/practice/info.do?idx=1&eid=1204&sw_prbl_sbms_sn=83550 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 예산의 범위가 매우 커서 처음엔 하나씩 올려가면서 찾는 방식을 선택했더니 시간 오류가 났다. 이 전에 이진 탐색으로 큰 범위에서 되게 빠르게 풀어나가는 문제를 softeer에서 풀었었는데 혹시 여기도 적용이 될까 해서 풀어봤는데 바로 문제 없이 풀렸다... import sys def check(mid): cost = 0 for i in power: if mid > i: cost += (mid - i) ** 2 if cost
[softeer] [21년 재직자 대회 본선] 트럭 (python)
https://softeer.ai/practice/info.do?idx=1&eid=631&sw_prbl_sbms_sn=82669 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 처음엔 돈 범위만큼 배열을 만들어 각각의 이익을 얻으려면 필요한 size를 모두 넣어서 구하려고 했다. 지금 생각해보면 매우 무식한 방법이고 시간 초과가 뻔했다. 인터넷 검색을 좀 해봐서 각각의 buyer가 제시한 사이즈에 맞는 금액과 시나리오를 정렬을 하면 가장 사이즈부터 시나리오에 부합하는지 찾기 때문에 더 빠르게 답을 찾을 수 있었다. 만약 해당 buyer가 이전에 이미 지불한 금액이 있었다면 그 금액과 비교해서 더 큰 금액일 시 바꿔주는 부분도 필요했다. 그리고 처음 정렬을 해..
[softeer] [21년 재직자 대회 예선] 회의실 예약 (python)
https://softeer.ai/practice/info.do?idx=1&eid=626 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 각 회의실마다 각 시간별로 스케줄을 만들어서 예약이 될 때마다 그 시간엔 예약이 되었다고 입력해준다. busy를 사용해서 회의실이 이미 예약 되었는지 체크를 한다. import sys n, m = map(int, sys.stdin.readline().split()) room = {sys.stdin.readline().strip(): [False] * 10 for _ in range(n)} for _ in range(m): r, s, e = sys.stdin.readline().split() s, e = int(s) - 9,..
[softeer] [21년 재직자 대회 예선] 이미지 프로세싱 (python)
https://softeer.ai/practice/info.do?idx=1&eid=627 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 image의 크기가 크지 않아서 입력을 받을 때마다 bfs를 통해서 색깔을 모두 바꿔주었다. 하지만 계속 히든 케이스에서 시간 초과가 나서 좀 찾아봤더니 만약 x, y, c를 입력받았는데 (x, y)의 색깔이 c와 같다면 무한 loop를 돌게 되어서 시간 초과가 나는 것이었다. 간단하게 시작 지점에서 해당 좌표의 색이 바꾸려는 색과 같은지 조건문 하나만 넣어 간단하게 해결하였다. import sys from collections import deque dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] h,..
[programmers] 합승 택시 요금 (python)
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 회고 다익스트라 알고리즘이 익숙지 않아서 개념 공부를 하고 푼 문제 다익스트라 알고리즘을 공부하고도 바로 풀지는 못했다. 문제를 작은 문제로 나눠서 풀었다. S와의 최단거리, A와의 최단 거리, B와의 최단 거리를 가지는 한 point를 찾아서 그때의 비용을 답으로 구한다. 총 세 가지 다익스트라 distance를 구했다. (S, A, B) import heapq def solution(n,..
[softeer] [인증평가(1차) 기출] 로봇이 지나간 경로 (python)
https://softeer.ai/practice/info.do?idx=1&eid=577 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 시작할 수 있는 point의 특징은 본인은 #이고 주변에 하나의 #만을 가지는 point를 먼저 찾았다. 총 두 개의 point가 찾아지는데 하나는 start 나머지는 end point로 설정하고 경로를 탐색한다. 가장 오래 고민했던 부분은 바라보는 방향을 돌릴 때 왼쪽, 오른쪽 어느 방향으로 돌려야 최적의 방법인지 결정하는 부분이었다. 처음에는 그냥 조건문으로 처리하려고 했는데 코드가 너무 길어질 것 같아서 softeer algo tutor를 참고해서 index를 이용해서 풀었다. -1을 해서 같은 방향이면 왼쪽으로, +..
[softeer] [인증평가(1차) 기출] 안전운전을 도와줄 차세대 지능형 교통시스템 (python)
https://softeer.ai/practice/info.do?idx=1&eid=580 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 bfs를 이용해서 경로를 찾아주면 된다. 하나 신경 쓸 부분은 해당 교차로에 오는 방향에 따라 다음 교차로로 갈 수 있냐 없냐가 정해진다는 점이다. 처음에는 당연하게 check list를 만들어서 방문한 교차로는 다시 방문하지 않도록 하였는데 계속해도 틀려서 조금 검색을 해보았더니 방문한 교차로도 돌고 돌면서 최종적으로 갈 수 있는 교차로를 모두 구하는 문제였다. 문제를 잘 이해하는 것이 중요할 것 같다. 변수 이름 짓기도 너무 어렵다... import sys from collections import deque n, t ..
[softeer] [인증평가(3차) 기출] 플레이페어 암호 (python)
https://softeer.ai/practice/info.do?idx=1&eid=804 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 문제 회고 주어진 규칙을 하나씩 구현해내는 문제였던 것 같다. 하나씩 차근차근해 나가 어렵지 않게 풀 수 있었다. import sys message = sys.stdin.readline().strip() key = sys.stdin.readline().strip() answer = '' # 1. key 5x5에 배열 # 2. message 두 글자씩 규칙에 맞춰서 배열 # 3. 배열을 하나씩 확인하며 같은 행에 존재하면 오른쪽으로 한칸 이동한 칸에 적힌 글자를 사용 HE -> EI, XX -> ZZ # 4. 같은 열에 존재한다면 아래..