Door

https://www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 www.acmicpc.net 문제 길이가 상당합니다. 이 문제에서 크게 생각할 건 2가지. 1. 어떻게 배열을 나누지? 2. 어떻게 연산하지? 저는 연산에 따라 나누는 걸 다르게 하는 쪽으로 접근했습니다. 연산은 부분이냐 배열이냐 2가지인데 이 연산에 따라서 나누는 방식이 달라져야겠다 생각했습니다. # 배열 부분요소 if k상하반전 if k==1: for a in range(2**(l-1)): for b..

알고리즘 공부 2022. 8. 15. 09:37

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 구현해줘야할 부분은 2가지. 1. 배열 돌리기 2. 배열 돌리는 거 백트레킹 구현할 2가지가 난이도가 상당히 있는 편이라 체감난이도가 높았던 문제입니다. 우선 배열을 돌리는 것부터 차근히 보겠습니다. def rotate(r,c,s): #s의 수만큼 돌린다 for ro in range(s,0,-1): s_x=r-ro s_y=c-ro #돌리는 횟수는 ro*8 p=0 r_..

알고리즘 공부 2022. 8. 11. 11:26

https://www.acmicpc.net/problem/17281 17281번: ⚾ ⚾는 9명으로 이루어진 두 팀이 공격과 수비를 번갈아 하는 게임이다. 하나의 이닝은 공격과 수비로 이루어져 있고, 총 N이닝 동안 게임을 진행해야 한다. 한 이닝에 3아웃이 발생하면 이닝이 종 www.acmicpc.net 야구게임을 구현하는 문제입니다. 이 문제에서 포인트는 이렇게 됩니다. 1. 선수들 케이스 구하기 2. 선수들 순서 유지하면서 이닝넘어가기 3. 아웃~홈런 구현하기 1-->permutation으로 1~8번째의 케이스를 구해줍니다. 그 후, 각 케이스를 리스트로 만든 뒤 (permutation,combination의 결과값은 tuple이 되므로 list로 전환시켜줘야함) insert(3,0)으로 4번째타자..

알고리즘 공부 2022. 8. 9. 09:27

https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 문제를 처음 읽고 당황했던 것. '궁수는 어디다가 배치하지??' 입력값은 빈칸 or 적이라서 궁수는 어디다가 배치하나 했더니 격자아래에 궁수가 배치되었다는 전제. 구현할 걸 순서대로 나열하면 이렇습니다. 1. 궁수 위치 -->combination으로 나타냈습니다. 이렇게하면 시간초과 뜰 것 같았는데 질문하기의 코드들을 참고해보니 combination써도 되겠다 싶었습니다. 2. 궁수가 적을 맞추기 -->BF..

알고리즘 공부 2022. 8. 8. 12:40

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이 문제는 문제자체보다는 문제가 길어서 '이게 뭔소리야...' 하면서 문제를 이해하는 게 좀 걸렸습니다. (워낙 문제가 길어서) 이 문제는 구현만 잘 시켜주면 됩니다. 가로 세로 대각선 각각을 움직일 때 어떻게 움직일지 제대로 구현만 해주면 끝. # # from collections import deque # N=int(input()) # room=[list(map(int..

알고리즘 공부 2022. 8. 5. 10:54

https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순 www.acmicpc.net 이 문제에서 중요한 포인트는 '어떻게 괄호를 묶는가'라는 부분. 이 부분이 상당히 난감했습니다. '아니....모든 괄호를 묶는 경우를 다 생각해야하는데 이걸 어떻게 묶냐고.... 묶을 때 각각의 데이터를 어떻게 저장하지? 이 부분이 도저히 생각이 안나서 구글링의 도움을 받았습니다. 제가 구글링을 통해 배운 건 "몇 번째를 묶어주는가" 하는 부분이었습니다. solve함수를 보면 try ..

알고리즘 공부 2022. 8. 2. 17:48

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 이 문제를 풀 때 가장 어려웠던 부분은 사이클 구현에 대한 것입니다. DFS로 길찾기까지는 어느정도 이해가 가는데 그래서 어떻게 사이클을 만들지? 라는 고민이 들었습니다. 저는 root라는 것이 나오면 사이클이 있다고 판단하는 코드를 만들었습니다. 예를들면 1이 처음에 들어오면 root로 설정하고 이후에 1이 들어오면 사이클이 완성이 되었다고 판단하도록 만들었습니다. 그런데 이 방식은 위의 예시같은 경..

알고리즘 공부 2022. 7. 26. 11:33

https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 비슷한 문제로 강의실이 있었습니다. 2022.07.13 - [알고리즘 공부] - [백준 11000번] 강의실 배정(파이썬) [백준 11000번] 강의실 배정(파이썬) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si..

알고리즘 공부 2022. 7. 24. 22:49