문제https://www.acmicpc.net/problem/29813문제 설명일렬로 서있는 N명의 학생들이 존재한다.가장 앞에 선 학생부터 최애의 팀원을 찾는다.가장 앞에 선 학생은 뒤를 돌아보며 맞은편에 있는 학생이 자신의 팀원이 아니라면 해당 학생은 맨 뒤로 이동한다.가장 앞의 선 학생의 학번이 X일 때 해당 학생의 팀원은 X-1명을 패스시키고 만난 X번째 학생이다.마지막으로 남은 사람이 김한양의 최애의 팀원이다.김한양의 최애의 팀원을 출력한다. 풀이마주본 학생이 팀원이 아닐 경우 맨 뒤로 가게되며,앞에 있는 학생들이 계속해서 뒤로 이동해서 다른 학생들은 앞으로 밀리는 구조가 반복된다.따라서 선입선출인 Queue 자료구조를 이용하여 팀원을 구한다.학번 - 1 만큼 뒤의 학생을 패스한다.패스가 끝난 ..

문제https://www.acmicpc.net/problem/23757문제 설명  N개의 선물을 M명의 아이들에게 나누어주어야 한다.아이들은 1부터 M까지 고유의 번호를 부여받는다.1번 아이부터 M번 아이까지 한 번에 한 명씩 현재 선물이 가장 많이 담겨있는 상자에서 원하는 만큼 선물을 가져갈 수 있다.누군가 선물을 가져간 상자에서 또 가져가도 상관없다.모든 아이가 원하는 만큼의 선물을 가져갈 수 있으면 1, 가져갈 수 없으면 0을 출력한다. 풀이아이들에게 1부터 M까지 고유의 번호가 존재하며, 1번 아이부터 순차적으로 가장 많이 담겨있는 상자에서 가져가므로최대힙을 통해 가장 큰 상자를 순차적으로 꺼내어 아이들에게 나누어 준다.선물 배열을 입력받은 후 최대힙으로 변환한다.최대힙에서 선물을 한 개씩 꺼내며..

문제https://www.acmicpc.net/problem/1927문제 설명  최소 힙 구조를 이용하여 아래 연산을 지원하는 프로그램을 작성한다.배열에 자연수 x를 넣는다.배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거한다. 풀이파이썬의 heapq 라이브러리를 이용한다.수를 입력받는다.입력받은 수가 0일 때heap 배열의 크기가 0이라면 0을 출력한다.heap 배열의 크기가 1 이상이라면 가장 작은 수를 출력한다.입력받은 수가 0이 아닌 수일 때heap 배열에 수를 저장한다.코드import sysimport heapqinput = sys.stdin.readlineheap = []N = int(input())for i in range(N): temp = int(input()) if t..

문제https://www.acmicpc.net/problem/20920문제 설명N개의 단어를 입력받는다.N개의 단어 중 길이가 M이상인 단어들만 외워야 한다.단어들을 외우는 순서에는 우선순위가 존재한다.자주 나오는 단어일수록 앞에 배치한다.해당 단어의 길이가 길수록 앞에 배치한다.알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다.  풀이N개의 단어를 입력받을 때 길이가 M이상인 단어들만 갯수를 Count한다.암기 우선순위에 맞게 정렬한다.코드import sysdic = dict()n,m = map(int,input().split())for i in range(n): word = input().strip() if len(word) 시간복잡도N개의 단어를 딕셔너리에 입력받을 때 $O(N)$딕..

문제https://www.acmicpc.net/problem/1706문제 설명  RxC 크기의 다 푼 크로스워드 퍼즐이 입력된다.각 칸은 알파벳이 하나씩 적혀있다.금지된 칸은 #으로 표기한다. 각 가로, 세로별 존재하는 낱말 중사전식으로 가장 앞서 있는 낱말을 구해라.이 때 한 단어는 낱말로 취급하지 않는다. 풀이 완전탐색을 통해 가로 세로 별로 낱말을 탐색한다.금지 단어 #을 기준으로 낱말을 파싱하여 한 글자가 아니라면 최종 단어 배열에 추가한다. 정렬을 통해 가장 첫 번째 인덱스 단어를 출력한다.코드import sysinput = sys.stdin.readlineR,C = map(int,input().split())board = [list(input().strip())+["#"] for _ in ra..

문제https://www.acmicpc.net/problem/1874문제 설명  1부터 n까지 수를 스택에 넣고 늘어놓으면, 하나의 수열을 만들 수 있다.스택에 push할 때, 순서는 반드시 오름차순으로한다.임의의 수열의 숫자가 한 개씩 순서대로 주어진다.스택을 통해 그 수열을 만들 수 있는지 없는지, 확인해야 한다.주어진 수열을 만들 수 있을 때 push와 pop연산을 어떤식으로 수행해야 하는지 계산하여 출력한다. 풀이수열의 한 숫자 t를 입력받았을 때 현재 count의 수 만큼 stack을 채운다.스택은 1부터 n까지 순차적으로 입력한다. 따라서 count의 수는 현재 $n_i$번째 수까지 넣었음을 의미한다.t가 count보다 크거나 같다면 스택에 숫자를 추가하고 결과에 '+'를 추가한다. t가 co..

문제https://www.acmicpc.net/problem/7507문제 설명 올림픽의 모든 경기의 시작 시간과 종료시간, 날짜가 주어진다.이 때 볼 수 있는 경기의 최대 개수를 구해라.경기를 보던 도중 다른 경기를 보기 위해 경기장을 옮길 수 없다.경기장을 이동하는데 걸리는 시간은 없다. 경기가 시작된 이후 경기장에 들어갈 수 없다. 풀이그리디하게 가장 빠른 날짜부터 경기가 끝나는 시간이 빠른 경기 순서대로 선택하면 될 것이라고 생각했다.모든 경기의 날짜, 끝나는 시간을 오름차순으로 정렬한다.모든 경기를 반복문을 통해 탐색한다.이전 경기의 종료 시간을 prev에 저장한다.현재 경기의 시작 시간이 prev보다 같거나 크다면 prev를 초기화 하고 카운팅한다.코드import sysinput = sys.st..

문제https://www.acmicpc.net/problem/14732문제 설명상현이는 행사장을 대여하려고 한다.행사장을 완전이 포갤 수 있는 N개의 직사각형을 만든다.N개의 직사각형들은 일부분 혹은 전체가 겹칠 수 있다.각 직사각형의 좌측 하단, 우측 상단의 좌표를 알려준다.행사장의 넓이를 구해라. 풀이X,Y의 최대 크기만큼 배열을 생성하여 0으로 초기화 한다.각 직사각형 좌표의 값을 +1한다.전체 배열을 반복문으로 탐색하면서 0이 아닌 위치만 카운트한다.코드import sysinput = sys.stdin.readlineN = int(input())board = [[0 for _ in range(500)] for _ in range(500)]res = 0for i in range(N): x1,y..

문제https://www.acmicpc.net/problem/15889문제 설명욱제를 포함한 N명의 전우들의 좌표가 주어진다.욱제와 전우들은  사거리 내에 있는 누구에게나 수류탄을 던질 수 있다. 정확히 날아오는 수류탄은 항상 받을 수 있다.수류탄이 바닥에 떨어지지 않고 마지막 전우에게 전달해야 한다.풀이맨 처음의 사람부터 그리디하게 최대 사거리를 계산하여 마지막 전우가 받을 수 있는지 체크하면 되는 간단한 문제였다.N-1번 전우까지 탐색한다.현재 던질 수 있는 최대 사거리가 현재 전우의 좌표보다 더 길다면 최대 사거리를 현재 전우가 던질 수 있는 사거리와 현재 최대 사거리중 최대로 초기화 한다.최대 사거리가 마지막 전우의 좌표보다 크거나 같다면 "권병장님, 중대장님이 찾으십니다"를 출력한다.그렇지 않다..

문제https://www.acmicpc.net/problem/14562문제 설명 경기에서 역전하기 위해 할 수 있는 연속 발차기의 종류는 두가지다.발차기 A:  현재 점수의 2배가 된다. 하지만 상대도 3점을 득점한다.발차기 B: 1점을 얻는다.태균이의 점수 S, 상대의 점수 T가 주어질 때 S == T가 되는 최소 연속 발차기 횟수를 구한다. 풀이1차원 배열의 탐색 문제이다. 발차기를 했을 때 점수는 음수로 가지 않는다. 따라서 사이클이 존재하지 않고, 증가했을 경우만 확인하면 되기에 너비우선탐색(BFS)를 떠올렸다.Queue에 나의 점수, 상대의 점수, 발차기 횟수를 입력한다.계속해서 증가하기 때문에 방문처리는 따로 하지 않았다.발차기 A를 했을 때 결과를 queue에 입력한다.발차기 A를 한 후 내..