이숭간 공부기록

https://www.acmicpc.net/problem/2262 2262번: 토너먼트 만들기 월드시에서는 매년 n명의 사람들이 모여 월드 크래프트라는 게임의 토너먼트 대회를 치른다. 이 게임은 특성상 실력만이 승패를 좌우하기 때문에, 아무리 실력이 엇비슷한 사람이 시합을 치러 www.acmicpc.net 문제유형 : 그리디 문제풀이 : 랭킹이 가장 낮은사람부터 찾은뒤, 좌우중에 랭킹차가 작은사람과 겨루게 한다. 랭킹이 가장 낮은사람부터 찾는이유?? :랭킹이 높은사람부터 찾고 랭킹차가 작은 사람과 겨루게하면 다음 라운드에서 만나게될 사람은 이전사람보다 더 랭킹차가 큰 사람일것이므로 그 차이가 점점더 커지게된다. 랭킹이 낮은사람을 찾고 겨루게한뒤에는 해당사람은 무조건 지게되있으므로 pop후에 리스트에서 없..

https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 문제유형 : 그리디, 정렬, 이분탐색 문제풀이 : 일반적인 그리디로 그냥 풀엇을때보다 이분탐색으로 풀면 10배정도 시간이 줄어든다. bisect 라이브러리를 이용하여 해당 크레인이 버틸수있는 무게의 가장 큰값을 찾을 수 있도록 했다. 삽질.. 분명 맞는거같은데 시간초과가나서 헤맸는데 알고보니까 맨처음 예외처리를 안해줘서 그랬다. ㅜㅜ... 하ㅏㅏㅏㅏㅏㅏㅏ 최대무게를 버틸수있는 크레..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 문제유형 : 정렬, 그리디, 우선순위큐 문제풀이 : 이전 회의의 종료시간과 현재 회의의 시작시간을 비교한다. 이때 서로 같은 강의실 이용이 가능하다면 큐의 원소를 다음회의로 갱신하도록 하고 서로 다른 강의실을 이용해야한다면 큐에 해당강의의 종료시간을 추가한다. 회의실 배정 문제와 비슷하다. 회의실배정문제에서는 연속된 회의를 가장많이 찾기만 하면 되는거였고 조건에 만족하지 않는애들은 버리면 되었는데, 여기서는 그런 애들도 다 체크해줘야되기때문에 ..

https://www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 문제유형 : 구현(시뮬레이션), 완전탐색 문제풀이 : 한명의 학생이 자리를 찾을때, 비어있는 모든 자리 탐색하며 조건에 가장 부합한 자리를 찾아야한다. (완전탐색) 학생은 딕셔너리형태로 {학생넘버 : 좋아하는학생리스트} 형태로 입력받는다. check(j,k)함수 : j,k인덱스 자리에서 인접한 자리에 위치한 친구들리스트와 빈칸의수를 리턴하는 함수 한명의 학생이 앉을 자리를 선택하는 과정..

https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제유형 : 구현(시뮬레이션), BFS 문제풀이 : 방문처리할 배열을 4차원으로 정의한다. (빨간구슬과 파란구슬을 함께 체크하기위함) check[rx][ry][bx][by] = True 이런식으로 초기의 빨간구슬과 파란구슬의 위치를 큐에 삽입 bfs함수를 통해, 빨간구슬과 파란구슬 모두 위,아래,왼,오른쪽으로 이동하는데 벽(#)이거나 구멍(O) 전..

https://www.acmicpc.net/source/31173872 로그인 www.acmicpc.net 문제유형 : 완전탐색 문제풀이 : 가능한 모든 연산자 순열을 찾는다. itertools의 permutations이용 주어진 숫자와 연산자를 식으로 해서 계산한다. 이때 음수를 나눌때만 예외처리를 해줘서 계산한다. 기억 처음에 숫자와 각각의 연산자 경우에 대해서 둘을 합쳐 하나의 식 형태의 문자열 배열을 만들고, 그 문자열을 eval로 계산하는식으로 했더니 시간초과가 났다. 굳이 문자열로 만든후에 계산하는 이 과정에서 배열을 한번더 돌게되니 시간초과가 난것같다. 그래서 그냥 num배열과 op배열을 주고 값을 계산하는 함수를 만들었더니 해결되었다. [1,2,3], [*,//]를 인자로 받아 문제 조건에..