1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 카드 비교 횟수가 최소가 되는 총 비교횟수를 출력하면 되는 문제다. 처음에 문제를 읽고, 이게 골드4문제라고? 라는 생각이 들었다. 그래서 5분만에 구현하고 제출하니 바로 시간 초과가 떴다. 문제를 자세히 읽어보니 입력 크기가 최대 100,000개 이므로 단순 비교로는 O(N^2)이라서 당연히 시간 초과가 뜬다. 그래서 계속 고민을 해봤다. 고민하다 보니, 이런 규칙이 나왔다. 매번 합칠 카드 묶음을 정할 때, 카드 묶음 리스트 중 가장 작은 값 ..
알고리즘/이것이 코딩테스트다
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 실패율 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 간단한 happenundo.tistory.com 풀었던 문제다. 정렬 + 구현 문제. # 실패율 def solution1(N, stages): result = [] # (스테이지 번호, 실패율)을 저장하고 있는 리스트 challenge = [0] * (N+2) # 각 스테이지별 도전 중인 사용자의 숫자를 저..
18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 중앙값이 답이다. 나는 평균값을 구해서 틀렸다. 아이디어가 중요한 문제. 풀이 코드 # 18310번: 안테나 import sys input = sys.stdin.readline n = int(input()) house = list(map(int, input().rstrip().split())) house.sort() # 정렬한 후 print(house[(n-1)//2]) # 중앙값 출력
10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 파이썬 lambda 함수와 정렬을 사용하면 되는 문제. 입력이 최대 100,000개이므로 sys 라이브러리를 사용하면 시간이 확 줄어든다. 풀이 코드 # 10825번: 국영수 import sys input = sys.stdin.readline n = int(input()) student = [] # (학생이름, 국어점수, 영어점수, 수학점수) for _ in range(n): name, a, b, c = input().rstrip().spli..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 전형적인 BFS를 이용해서 최단거리를 구하는 문제이다. 다만, 일반적인 BFS 문제와 다른 점은 로봇이 차지하고 있는 위치가 두 칸이며, 가로세로 이동뿐만 아니라, 회전을 통해 이동할 수 있다는 점이다. 나도 BFS를 사용해야 하는 최단거리 문제라는 점은 바로 알았지만, 이를 어떻게 구현해야 할지, 즉, 구현력이 부족한 걸 느낀문제였다. 로봇이 차지하고 있는 위치가 2칸이라고 하더라도, 위치 정보를 관리할 수 있는 방법이 있다. 바로 튜플을 사용하는 것이다. 로봇의 상태를 {(1, 1), (1, 2)} 이런 ..
16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀긴 풀었는데, 시간 복잡도가 최악임 BFS를 활용해서, 인구 이동할 수 있는 국가들을 담은 리스트를 반환해주는 함수를 만들어주고, 해당 리스트에 담긴 원소(인구)의 합을 원소의 길이를 나눈 값으로 해당 국가들의 값(인구)으로 바꿔준다. 그리고, 만약, 위 과정을 겪었을 때, 그래프의 원소가 변하지 않았다면, 더 이상 인구이동을 하지 않은 것이므로 반복문을 종료한다. 내 풀이 코드 # 16234번: 인구 이동 from collections impor..
18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net 장애물을 정확히 3개 설치할 수 있는 경우의 수를 모두 찾아서, 감시를 피할 수 있는 경우가 있는 경우 YES를 출력하고, 그렇지 않은 경우 NO를 출력하면되는 문제다. 문제 구현을 위한 아이디어 생각은 금방했다. 1. 장애물을 설치한 후, 감시를 피할 수 있는지 여부를 확인하기 위한 함수 2. 장애물을 설치하는 함수 이 2가지 함수만 있다면 쉽게 풀 수 있는 문제라고 생각했다. 1번 함수는 금방 구현했으나, 문제는 2번이었다. 단순히 파이썬 iterto..
14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net itertools 패키지의 permutations 클래스를 활용해서 풀었다. 단, permutations를 사용해서 나올 수 있는 연산자 리스트의 후보를 구할 때, 한 연산자가 2개 이상 들어 있을 경우, 같은 연산자 리스트가 연산자 리스트 후보에 들어 있을 수 있으므로 set으로 바꿔줘서 중복을 없애주는 방식으로 구현했다. 내 풀이 코드 # 14888번: 연산자 끼워넣기 from itertools imp..
프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr DFS 문제 같이 생겼지만, DFS 문제는 아니고 재귀를 사용한 구현 문제다. 문제를 잘 이해하지 못해서, 풀지 못했다. 풀이를 보니 굉장히 쉽고, 문제만 이해한다면 구현할 수 있는 문제라는 생각이 들었다. 문제를 많이 풀어서 구현력을 키우자. 다시 풀어야 할 문제 풀이 코드 # 괄호 변환 # '균형 잡힌 괄호 문자열'의 인덱스 반환 def balanced_index(p): count = 0 # 왼쪽 괄호의 개수 for i in range(len(p)): if p[i] == '(': count += 1 els..
18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS 문제인데 응용해야 하는 문제다. 처음에는 전체 바이러스의 시작점의 위치를 큐에 넣고, 각 바이러스를 한번씩 이동시키면 되는 쉬운문제 아닌가? 라는 생각이 들었고, 구현도 시간이 오래 걸리진 않았다. 하지만 하나의 큐에 각 바이러스의 위치를 넣어서 BFS를 구현할 경우, 바이러스를 구분할 수가 없었다. 이걸 보고, 큐를 여러개 만들어야 하나? 라는 생각이 들었는데, 이러면 큐가 너무 많아지는데? 라는 생각이 들어서 넘겨버렸다. ..
