이숭간 공부기록

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

www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 문제유형 : 분할정복, 재귀 문제풀이 : 아이디어 생각 자체는 어렵지 않은데 구현에서 먼가 꼬여서 생각보다 오래품 주어진 종이크기를 4등분하는함수 / 주어진종이가 모두 0인가(흰색정사각형인가)를 판단하는 함수 / 반대로 파랑인지 확인함수 이렇게 3개의 함수를 구현하고 풀었다 정답코드 import sys input = sys.stdin.readline n = int(input()) #종..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제유형 : 구현, 그래프탐색 (삼성기출) 문제풀이 BFS(DFS도 가능)를 통해 연합가능한 국가를 찾도록 한다. 전체국가를 돌면서 bfs로 연합가능한 국가의덩어리들을 찾고 각 덩어리들사이에서 인구이동을 진행한다. 모든칸(전체국가)을 돌았는데 인구이동이 한번도 없었다면 더이상 진행이 불가한것을 의미하므로 while문을 break하고 빠져나온다. 인구이동이 있었다면, 다시 visite..