https://school.programmers.co.kr/learn/courses/30/lessons/159993 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - BFS로 문제를 해결했다. - 레버를 거쳐가야 출구에 있는 문을 열 수 있기 때문에 출구에서 레버로, 레버에서 출구로 가는 최단거리를 구한다. - 이때 두 가지 경우 중 한 가지라도 목적지에 도달하지 못하는 경우 -1을 return 한다. from collections import deque def solution(maps): n, m = len(maps), len(maps[0]) dy = ..
코딩테스트 연습 - 표 병합 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - Union - find를 이용해 문제를 해결했다. - 사실 union - find가 잘 기억나지 않아 찾아보았다. 그리고 2차원 배열에서는 적용해 본 적이 없어 다른 사람의 풀이를 참고해보기도 했다. - 같이 스터디하시는 분 중 한분께서 51 x 51의 2차원 배열을 51을 제곱한 값인 2601의 길이를 가진 1차원 배열로 하여 문제를 해결했다. 표 편집이라 해서 2차원으로 체크를 해야 한다는 생각에 갇힌 것 같다. 알고..
코딩테스트 연습 - 게임 맵 최단거리 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 기본적인 BFS/DFS문제이다. def bfs(maze, n, m): visited = [[0] * m for _ in range(n)] q = [] q.append([0, 0]) visited[0][0] = 1 dy = [-1, 1, 0, 0] dx = [0, 0, -1, 1] while q: st = q.pop(0) for k in range(4): i, j = st[0] + dy[k], st[1] + dx[..
코딩테스트 연습 - 과제 진행하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 정렬 + 스택을 이용했다. - 처음에는 스택의 마지막과 현재 정보랑 비교해서 하는 식으로 진행하려 했으나 잘되지 않아 시간의 흐르면서 스택의 마지막에 있는 과제를 진행하는 방식으로 바꿨다. - 먼저, 입력 받는 값의 시간을 분으로 바꿔준다. 플레이 시간도 int 값으로 변환 후 새로 list에 저장한다. 이때 시간을 key로 하고 나머지를 value로 하는 시간 체크용 dict도 만들어 준다. - 과제 시작 시간으로..
https://school.programmers.co.kr/learn/courses/30/lessons/152996 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - Counter를 이용해 몸무게에 따른 사람 수를 체크한다. - 거리에 따른 비율 list 생성한다. 이때 1 이하인 비율은 확인하지 않는다. 그 이유는 나라는 기준점에서는 1 이하 일 수 있지만 시소 반대편 사람기준에서는 역수가 되어 1보다 커지기 때문이다. 그래서 중복으로 체크할 필요가 없다. - 몸무게를 순회하면서 확인한다. 이때 같은 몸무게가 2명 이상이면 같은 몸무게가 같은 경우의수도..
https://www.acmicpc.net/problem/23290 23290번: 마법사 상어와 복제 첫째 줄에 물고기의 수 M, 상어가 마법을 연습한 횟수 S가 주어진다. 둘째 줄부터 M개의 줄에는 물고기의 정보 fx, fy, d가 주어진다. (fx, fy)는 물고기의 위치를 의미하고, d는 방향을 의미한다. 방향 www.acmicpc.net - 어디가 틀렸는지 몰라서 헤맨 탓에 3시간 넘게 걸렸다. 단계 별로 조건에 맞는 값이 나오는지 확인 후 넘어가는 습관을 들이자. - 2차원 리스트를 이용하여 풀이를 진행했지만, 이전에 포스팅했던 파이어볼 문제처럼 dict를 이용한다면 제출 시 시간을 더 단축할 수 있을 것이다. 코드를 참고하고 싶다면 해당 문제에서 맞힌사람 → 언어: Python에서 2등이신 분..
코딩테스트 연습 - 택배 배달과 수거하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - Greedy 문제로 이 문제에서는 먼 곳부터 배달, 수거를 하는 방식으로 진행했다. - pop을 이용해 배달, 수거를 해야할 가장 먼 집들을 찾는다. - 물류창고에서 배달 or 수거를 하고 다시 돌아와야 하기 때문에 answer에는 왕복거리를 계산하기 위해 *2를 하며, 배달 or 수거 중 먼거리를 수행한다. - 배달과 수거의 경우를 나누어 아래 코드와 같이 체크하면서 연산을 진행했다. def solution..
코딩테스트 연습 - 이모티콘 할인행사 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 문제에서 주어진 이모티콘의 할인율을 가지고 이모티콘 할인하는 모든 경우의 수를 만들어서 체크를 했다. - 이때 할인율은 개별적인 것이기 때문에 중복순열(itertools의 product)을 이용해 풀이를 진행했다. - 이모티콘들의 할인율에 대하여 모든 경우를 체크한다. - 모든 경우를 다 체크한 후, 주어진 조건 1, 2를 기준으로 answer을 정렬한 뒤 가장 조건에 부합하는 0번 index의 값을 return..
https://www.acmicpc.net/problem/21611 21611번: 마법사 상어와 블리자드 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그, 비바라기 마법을 할 수 있다. 오늘 새로 배운 마법은 블리자드이고, 크기가 N×N인 격자에서 연습하려고 한다. N은 항상 홀수이고, ( www.acmicpc.net - 특별한 알고리즘이 필요하지 않았지만 틀린 부분 찾느라 시간을 많이 소비했다. - 문제에서 주어진 조건을 순서대로 구현하면 된다. - 채우는 것을 매번해줘야 하기 때문에 미리 좌표를 구해놓고 시작했다. 상어를 기준으로 문제에서 주어진 달팽이 형태의 이동경로를 따라 좌표를 list에 넣어주었다. - 먼저 블리자드로 구슬 파괴를 하는데 이때 파괴도 폭파에 포함인 줄 알고 같이 카운..
코딩테스트 연습 - 숫자 변환하기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - Dynamic Programming 중 Memoization을 이용한 풀이 - 초기 값(횟수)을 넣어주고 dp 테이블 생성 후 for문으로 탐색 - 이때 생성되지 않는 값은 pass - 주어진 조건으로 연산된 값이 되는 index에서의 연산 횟수와 연산 전 값에서 연산 횟수 +1 중 최솟값을 갱신하는 방식으로 진행 → dp[idx+n] = min(dp[idx+n], dp[idx]+1) def solution(x, y..
코딩테스트 연습 - 뒤에 있는 큰 수 찾기 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - heapq를 이용해서 풀었다. - 존재하지 않으면 -1을 담기 때문에 초기값을 -1로 한 answer list를 생성한다. - 입력값을 하나씩 꺼내온다. 꺼내온 값과 heap에서 꺼낸 값을 비교하고 작다면 heap에서 꺼내 온 값의 index에 현재 값을 넣어준다. - while문을 빠져나왔다면 heap에 현재 값과 index를 함께 넣어준다. import heapq def solution(numbers):..
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이 더 빠르다는 것을 스터디..
