코딩테스트

[Python] 프로그래머스 - 입국심사

문제: https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분탐색 카테고리에 있는 문제였지만, 이분탐색으로 푸는 방법을 찾기까지 시간이 좀 걸렸다. '시간의 최소값'에 집중하면, 어떤 순서로 검사받든 가장 최소로 걸리는 시간을 계산하면 되는데, 심사받는 순서에 집중을 하다보니 이분탐색 풀이법이 바로 떠오르지 않았다. def solution(n, times): min_val = 1 max_val = max(times)*n answer = 0 whi..

[Python] 프로그래머스 - 섬 연결하기

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42861 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 최소 신장 트리(MST)를 구하는 문제이다. Kruskal 알고리즘을 사용해 MST를 구해보자. def solution(n, costs): answer = 0 costs.sort(key = lambda x: x[2]) link = set([costs[0][0]]) while len(link) != n: for v in costs: if v[0] in link and v[1] in link:..

[Python] 프로그래머스 - 카펫

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42842 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제를 보고 yellow의 약수를 나열해 문제를 풀면 되겠다고 생각했다. 곱해서 yellow 값이 나오는 약수 쌍을 구한 후, 각 쌍의 테두리 값을 구했을 때 brown과 값이 일치하는 쌍을 구하면 된다. 이때 약수 쌍을 (x, y)라고 하면, 테두리 값은 (x+1)*2 + (y+1)*2로 구할 수 있다. return값은 카페트의 총 가로, 세로 길이를 돌려주므로 (x+2, y+2)를 반환..

[Python] 프로그래머스 - 전화번호 목록

문제: https://school.programmers.co.kr/learn/courses/30/lessons/42577 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 1 def solution(phone_book): answer = True phone_book.sort(key=len) for i in range(len(phone_book)): for j in range(i+1, len(phone_book)): n = 0 while n < len(phone_book[i]): if phone_book[i][n] != phone_book[j][n]: b..

[Python] 백준 20055번 - 컨베이어 벨트 위의 로봇

문제: https://www.acmicpc.net/problem/20055 20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net 구현 문제였기 때문에 문제에서 요구하는 순서대로, 잘 구현해주었다. 문제를 풀면서 주의해야할 점들이 몇가지 보였는데 다음과 같다. 주의할 점 1. 벨트 순서 사진을 보면 N+1번째 칸이 N번째 칸 밑에 존재한다. 처음에는 1~N, N+1~2N 순서로 배열을 만들었는데 1~N, 2N~N+1 순서로 배열을 만들어 주어야 한다. (예제 1, 2, 3은 맞는데 예제 4번만 틀..

[Python] 백준 15684번 - 사다리 조작

문제: https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 문제를 처음보고 이걸 어떻게 풀어야하나 좀 당황스러웠다 ㅎㅎ.. 일단 사다리 구현부터 해보자 싶어서 dfs를 활용해 사다리 구현만 해보았따. 이후 부르트포스로 빈 사다리 자리에 하나씩 넣어가면서 풀어야하나 고민을 하다가 1시간이 지나서 답을 보기로했다. 답을 보니 실제로 dfs로 하나하나 넣어가면서 최소값을 찾는 문제였다.. 부르트 포스를 많이 안풀기도 했고, 비효율적이라는 생각이 들어서..

[Python] 백준 2146번 - 다리 만들기 (bfs, dfs 풀이)

문제: https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제를 보고 각 육지의 테두리에 있는 좌표들만 모아서 좌표들끼리 최단거리를 비교하며 최소값을 찾아가야겠다고 생각을 했다. 처음에는 bfs로 육지가 나올 때 마다 주변 4방향을 탐색하여 바다와 인접하는 경우에만 리스트에 담으며 테두리 좌표값을 구했다. 코드는 다음과 같다. from collections import deque n = int(input()) board = [list(map(int, ..

[Python] 백준 16234번 - 인구 이동

문제: https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 처음에는 모든 좌표를 방문하면서 오른쪽과 아래방향의 나라만 비교하면 중복없이 연합 국가들을 찾을 수 있겠다고 생각했다. 그렇게 연합국들을 찾아 union 변수에 다 넣고 처리해주면 풀 수 있을 줄 알았다. 실제로 예제 1~4는 해당 방식으로 문제가 풀렸는데, 예제 5에서 오류가 떴다. 문제는 연합국들이 2개 이상의 지역으로 나눠지는 경우였다. 연합국 지역이 2개 이상이면, 매..