알고리즘 문제 풀이: 파이썬/BOJ211

• 

  [BOJ_2775] 부녀회장이 될테야 문제 링크: https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 내 풀이: Review: 문제에서 주어진 조건에 맞게 거주자의 수를 계산하여 2차원 배열에 넣고, 테스트 케이스에 따라 2차원 배열에서 층과 호수를 찾아 결괏값을 출력했다. 문제를 풀고 다른 사람들의 풀이를 확인했는데 테스트 케이스 마다 해당 층과 호수 정보를 이용해 거주자를 매번 계산하는 풀이도 있었다. 하지만 테스트 케이스에 따라 계속 거주자를 계산하는 것보다 결과를 한 번 구하고 계속 이용하는 것이 좀 더 효율적인 코드.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 16.

• 

  [BOJ_2217] 로프 문제 링크: https://www.acmicpc.net/problem/2217 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net 내 풀이: Review: 모든 로프를 사용하지 않아도 되기 때문에 하나의 로프를 사용하는 것부터 로프의 개수를 하나씩 늘려가며 최대로 견딜 수 있는 무게를 계산했다. 이때, 로프들의 정보를 입력받은 배열을 내림차순으로 정렬하여 견딜 수 있는 무게가 가장 큰 로프부터 개수를 셀 수 있도록 했다. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 13.

• 

  [BOJ_1026] 보물 문제 링크: https://www.acmicpc.net/problem/1026 1026번: 보물 첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거 www.acmicpc.net 내 풀이: Review: 문제에서 요구하는 S의 값을 최소로 만들기 위해서는 A 배열에서 최댓값을 B 배열의 최솟값과 곱하고 그 결과를 더하는 과정을 통해 만들 수 있다. 문제의 조건에서 A 배열은 재배열을 하지만, B 배열을 재배열을 하면 안 된다는 조건이 있어서 A 배열만 역순으로 정렬을 하고, B 배열에서는 최솟값을 하나씩 꺼내 A 배열의 첫 번째 원소부터 곱하고 그 결과.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 13.

• 

  [BOJ_1343] 폴리오미노 문제 링크: https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 내 풀이: 참고용 풀이: Review: 분명히 맞게 푼 것 같은데 30%에서 계속 틀렸다... 백준의 질문 검색 게시판을 보며 반례를 찾아 계속 수정하고 제출했지만 번번히 틀렸다. 결국에는 내 풀이를 알고리즘 오픈 카톡방에 올렸고 한 분이 반례를 알려주셔서 그 부분을 수정하고 제출했더니 문제를 해결할 수 있었다!!! Idea: 사전 순으로 가장 앞서는 답을 출력해야 하는데 만약 XXXX가 있다면 BB를 두 번 사용하는 것보다 AAAA를 한 번 사용하는 것이 사전 순으로 앞선다. 이 분에 .. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 6.

• 

  [BOJ_11399] ATM 문제 링크: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 내 풀이: Review: 돈을 인출하는 데 걸리는 시간의 최솟값을 구하기 위해서는 각 사람들이 인출하는 데 걸리는 시간은 변경할 수 없기 때문에 자신의 순서를 기다리는 시간을 최소화해주면 된다. 이를 위해 입력값으로 주어진 배열을 오름차순으로 정렬했고, 기다리는 시간과 인출 시간의 합을 누적해서 더하기 위해 슬라이싱을 이용했다. 문제 난이도에 비해 꽤 쉬운 문제였다. Idea: 입력 값으로 주어진 배열을 정렬후 슬.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 4. 6.

• 

  [BOJ_1904] 01타일 문제 링크: https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 내 풀이: Review: 문제에서 결괏값을 15746으로 나눈 나머지의 값으로 리턴하라고 해서 결과를 반환하는 print() 안에서 나머지의 값을 반환하도록 코드를 작성하니 메모리 초과가 발생했다. 그래서 이 방법이 아닌 for 반복문 안에 배열의 값을 변경하는 부분에서 나머지 값을 저장하도록 변경하니 이 문제를 해결할 수 있었다. Idea: 규칙을 통해 점화식 찾기 알고리즘 문제 풀이: 파이썬/BOJ 2022. 3. 23.

• 

  [BOJ_9461] 파도반 수열 문제 링크: https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 내 풀이: Review: 어제 처음으로 DP 문제를 풀고 두 번째로 푼 DP 문제이다. DP는 뭔가 어려울 것 같다는 생각에 문제 푸는 것을 시도하지 않았는데, 패캠 강의를 통해 이론을 배우고, 문제 풀이 강의를 듣기 전에 해당 풀이를 시도했더니 전혀 어렵지 않았다. DP 문제를 풀때는 규칙을 통해 점화식을 구하는 것에 집중을 해보자! Idea: 규칙을 통해 점화식을 세울 수 있다면 어렵지.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 3. 23.

• 

  [BOJ_2578] 빙고 문제 링크: https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 내 풀이: Review: 약 두 달만의 알고리즘 문제 풀이라서 그런지 구현의 아이디어를 떠올리는 것을 어렵지 않았지만, 코드로 구현하는 데 시간이 꽤 걸렸다. 문제를 풀면서 빙고의 개수를 확인하는 부분을 어떻게 구현할지 고민했는데, 어렵게 생각하지 않고 단순하게 생각하니 의외로 쉽게 해결할 수 있었다. Idea: 1. 1~5번째 줄의 입력값을 철수의 빙고판(bingo_board)으로 저장 2. 6~.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 3. 4.

• 

  [BOJ_1107] 리모컨 문제 링크: https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 내 풀이 (Fail): 참고용 풀이 (Success): Review: 처음 문제를 접했을 때 완전 탐색이 아닌 N을 바로 만드는 경우에 대해서만 생각했고 그 결과가 위의 첫 번째 코드이다. 하지만 몇몇 테스트 케이스에서 실패하는 경우를 확인하고 어떻게 해결해야 할지 감이 잡히지 않아 구글링을 통해 다른 사람의 코드를 확인하며 문제를 다시 이해하려고 했다. 이 문제의 풀.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 1. 14.

• 

  [BOJ_1159] 농구 경기 문제 링크: https://www.acmicpc.net/problem/1159 1159번: 농구 경기 상근이는 농구의 세계에서 점차 영향력을 넓혀가고 있다. 처음에 그는 농구 경기를 좋아하는 사람이었다. 농구에 대한 열정은 그를 막을 수 없었고, 결국 상근이는 농구장을 청소하는 일을 시작 www.acmicpc.net 내 풀이: Review: 선수의 성의 첫 글자를 출력하는 부분과 항복을 뜻하는 'PREDAJA'를 출력하는 부분의 print()를 두 개의 print()로 출력하는 것이 아닌 하나의 print()문 안에 if-else문을 이용하면 보다 짧은 코드로 같은 결과를 낼 수 있을 것 같다. Idea: 입력값의 첫 번째 글자를 적절히 카운팅 해서 글자의 개수가 5개 넘으면 선수를 선발할 수 있기 때문.. 알고리즘 문제 풀이: 파이썬/BOJ 2022. 1. 8.