이숭간 공부기록

https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 문제유형 : 그리디, 정렬 문제풀이 : 가장 거리가 먼 구간부터 끊어주면 된다! 내가 좀 헤맷던 부분은 진짜 바보같은데 일단 거리를 기준으로 정렬까지 했는데, 해당 구간을 끊었을때 끊겨진 각 구간의 합을 어떻게 처리해야될지를 모르겠었다. 근데 그냥 거리를 저장한 배열에서 그 구간을 자를때마다 전체합에서 그만큼만 빼주면 최종결과가 그냥 최종답이다. k가 n보다 크거나 같을때..

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], [*,//]를 인자로 받아 문제 조건에..

https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 문제유형 : 분할정복? 문제풀이 : 내가 속해있는 팀을 구한다. 걔와 나는 언제 만나는가? --> 서로 같은 팀이 될때 만난다. 두 사람이 같은 팀에 속해질때 까지 팀구하기를 반복한다. 정답코드: def solution(n,a,b): answer = 0 x = min(a,b) y = max(a,b) while True: answer +=..