BOJ (7) 썸네일형 리스트형 [1700] 멀티탭 스케줄링 (python) https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 문제에 대한 접근법 문제의 상황에서 볼 때 멀티탭을 꽃을때 최소의 꽃았다 뺐다를 반복하면서 전체 전기용품의 경우를 꽃는 것이다. 다음으로 미루어 봤을 때 경우를 나누어 조건에 맞춰 멀티탭을 꽃으면 된다. 멀티탭이 꽃을려 할 때 가장 먼저 멀티탭이 현재 비어있다면 순차적으로 꽃으면 되는 것이고, 만약 N개의 구멍에서 전부 꽃아져 있다면 다음 꽃을 전기용품이 이미 꽃혀있는지를 전제로 확인해야한다. 위.. [1715] 카드 정렬하기 (python) https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 문제에 대한 접근법은 다음과 같이 접근하였다. 1. 주어진 카드 개수를 입력으로 받아 리스트 형식으로 저장한다 2. heapq를 이용하여 리스트 내 최소값을 구하기 쉽도록 만든다. (계산량 효율을 위해서 heapq를 쓴다) 3. 해당 리스트에서 heappop을 통해 가장 작은 2개의 값을 추출하여 first, second에 저장 후 둘을 더한 값을 결과값에 더한 뒤 원래 리스트에 h.. [18808 번] 스티커 붙이기 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 문제 자체가 길어서 조금 읽는데 힘들었지만, 문제에서 말하고자하는 내용은 정확하게 파악할 수 있었습니다. 첫번 째로는 노트북에 스티커를 특정 영역에서 붙일 수 있는지 없는지 확인하는 것이 먼저이고, 그 다음에는 스티커를 회전하는 방법이 있습니다. 우선 노트북의 (x,y)에 모눈종이의 (0, 0)이 올라가게 스티커를 붙이려면 노트북 위의 스티커가 붙은 칸과 모눈종이 위에 스티커가 붙은 칸이 겹지면 안.. [11728 번] 배열 합치기 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 문제 자체 상황에서는 merge sort를 구현을 할때 많이 사용되는 논리를 가져와서 문제를 풀었스니다. 문제에서 가장 중요한 부분은 2개의 정렬이 되어있는 배열을 합치는 과정에서 조건문인데, 서로 다른 미지수를 사용해서 인덱스를 다르게 증가시켜야하기 때문에 idx1, idx2를 사용했습니다. 그리고 조건문 중에서 가장 중요한 idx1==n , idx == m일.. [15683 번] 감시 https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net BFS문제를 풀었을 때와 비슷하게 2차원을 표시하는 x,y표시를 dx[],dy[]를 이용하여서 0,1,-1을 활용하여 남,동,북,동쪽 방향을 나타내게 만들었습니다. board1은 원본 board2는 cctv가 감시하는 구간을 0에서 7로 변경하면 내부 인덱스값을 바꾸면서 값을 넣는 배열로 만들었습니다. cctv 좌표를 저장할 vector변수를 만들어줍니다. 문제를 풀 때 특정 (x,y).. [9663번] N-Queen 이 문제는 NxN 체스판에 퀸 N개를 서로 공격하지 못하는 위치에 놓는 경우의 수를 구하는 문제입니다. 퀸은 체스판 위에서 상하좌우 대각선으로 공격할 수 있는 기물인 것을 유의해야합니다. 단 문제의 N은 14이하이므로 백트래킹을 이용해서 문제를 풀 수 있습니다. 이 문제에서 가장 어려운 부분은 특정 좌표에 퀸을 둘 수 있는지 어떤 식으로 판별하는가 입니다. 저희가 실제 코딩 할 때 2차원 배열의 좌표를 쓰는 것이 편하기 때문에 좌표로 생각을 하겠습니다. 퀸이 놓인 자리에는 행과 열이 같은 자리에는 다른 퀸을 못놓으며, 좌측 하단과 우측 상단을 잇는 대각선은 x가 1 증가하면서 y가 1감소하는 대각선입니다. 그리고 좌측 상단과 우측 하단을 잇는 대각선은 x-y가 같은지 보면 됩니다. #include usi.. [15649번] N과 M(1) 백트래킹 문제를 풀려고하면 구현력을 상당히 필요로하고 실수하기도 쉬운구간입니다. 또한 재귀의 특성상 한 번 오류가 나면 디버깅하는데 오래걸리기 때문에 그래서 많은 시간을 쌓아야 한다고 생각합니다. 위 알고리즘은 8중 for문을 쓰면 어거지로 풀 수는 있지만, 조금 있어보이게 (?) 풀기 위해서는 백트래킹 알고리즘을 사용해서 풀면 좋습니다. 비어있는 리스트에서 시작해서 수를 하나씩 추가하면서 길이가 M인 수열을 완성되면 출력하는 방식으로 구현할 수 있습니다. 하지만 이걸 구현한다고 하면 사실 감이 잘 안옵니다. #include using namespace std; int n, m; int arr[10]; //수열을 담을 배열 bool isused[10]; //특정 수가 쓰였는지를 true 혹은 false로.. 이전 1 다음
