1.개발 진행 및 완료상황
- 2주차 python algorithm 틀린 문제 복습 완료
- CSAPP 2주차 목표 읽기
-
업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용
- 백준 2110(파이썬)
2110번: 공유기 설치
2110번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공유기 설치 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 55494 18901 13282 36.209% 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x 1 , …, x N 이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수…
www.acmicpc.net
공유기를 일정한 거리로 설치한다. 설치 거리를 이분탐색을 통해 구한다.
설치한 공유기 수와 입력값으로 주어진 공유기 수와 비교하며 답을 찾아냈다.
import sys N, C = map(int, sys.stdin.readline().split()) houses = list(int(sys.stdin.readline()) for _ in range(N)) houses.sort() pl, pr = 1, houses[N-1]-houses[0] result = 0 if C == 2: print(pr) else: while(pl<pr): pc = (pl+pr)//2 count = 1 recent = houses[0] for i in range(N): if houses[i]-recent >= pc: count += 1 recent = houses[i] if count >= C: result = pc pl = pc+1 elif count <C: pr = pc print(result)
- 백준 8939(파이썬)
8983번: 사냥꾼
문제 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가정하고, 사대의 위치 x 1 , x 2 , …, x M 은 x-좌표 값이라고 하자. 각 동물이 사는 위치는 (a 1 , b 1 ), (a 2 , b 2 ), …, (a N , b N )과 같이 x,y-좌표 값으로 표시하자. 동물의 위치를 나타내는 모든 좌표 값은 양의 정수이다. 사냥꾼이 가지고 있는 총의 사정거리가 L이라고 하…
www.acmicpc.net
사로 좌표 리스트를 오름차순으로 정렬 한다. 각 동물을 기준으로 가장 가까운 사로를 찾아낸다. 범위 내의 경우 카운트한다. 거리 비교시 abs를 이용한 절댓값보단 비교연산자를 두번 사용하는게 오히려 편리했다.
import sys input = sys.stdin.readline m, n, l = map(int, input().split()) shooting*place = list(map(int, input().split())) animal = [list(map(int, input().split())) for * in range(n)] shooting_place.sort() count = 0 for a, b in animal: if b > l: continue start = 0 end = m - 1 while start <= end: mid = (start+end)//2 if shooting_place[mid] < a + b - l: start = mid + 1 elif shooting_place[mid] > a - b + l: end = mid - 1 else: count += 1 break print(count)
- 백준 2630(파이썬)
2630번: 색종이 만들기
문제 아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2 k , k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이…
www.acmicpc.net
변의 길이, 시작 행,열 세가지를 변수로 하는 함수를 만든다.
시작 행열과 반복문을 통한 색깔 비교를 통해 갯수를 구했다.
return을 헷갈려서 고생했다.
import sys n = int(sys.stdin.readline()) sqaure = [] for _ in range(n): sqaure.append(list(map(int,sys.stdin.readline().split()))) ans = [] def devide(n,a:int,b:int): col = sqaure[a][b] for i in range(a,a+n): for l in range(b,b+n): if col != sqaure[i][l]: devide(n//2,a,b) devide(n//2,a+n//2,b) devide(n//2,a,b+n//2) devide(n//2,a+n//2,b+n//2) return ans.append(col) devide(n,0,0) print(ans.count(0)) print(ans.count(1))
- 백준 1629(파이썬)
1629번: 곱셈
1629번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 곱셈 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 0.5 초 (추가 시간 없음) 128 MB 88238 24202 17716 26.443% 문제 자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 출력 첫째 줄에 A를 B번 곱…
www.acmicpc.net
지수법칙과 나머지 법칙을 이용했다.
나머지 법칙은 (ab)%c = ((a%c)(b%c))%c 이다.
import sys a,b,c = map(int,sys.stdin.readline().split()) def multi (a,n): if n == 1: return a%c else: tmp = multi(a,n//2) if n %2 ==0: return (tmp _ tmp) % c else: return (tmp _ tmp *a) %c print(multi(a,b))
- 백준 2493(파이썬)
2493번: 탑
2493번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 탑 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1.5 초 128 MB 55041 17911 11983 31.102% 문제 KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으…
www.acmicpc.net
탑의 번호와 레이저 방향이 다르다는 것이 헷갈렸다. 또한 송신탑을 찾았을 때 입력할 index값도 헷갈렸다. 레이저를 기준으로 파악하는 것보단 탑이 세워진 쪽으로 생각하는 것이 조건 분류에는 편했다.
import sys N = int(sys.stdin.readline()) top_list = list(map(int, sys.stdin.readline().split())) stack = [] answer = [] for i in range(N): while stack: if stack[-1][1] > top_list[i]: answer.append(stack[-1][0] + 1) break else: stack.pop() if not stack: answer.append(0) stack.append([i, top_list[i]]) print(“ “.join(map(str, answer)))
- 백준 2812(파이썬)
2812번: 크게 만들기
2812번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 크게 만들기 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 24759 6493 4683 26.031% 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 …
www.acmicpc.net
위의 탑 문제와 비슷한 부분에서 부족했다. 기존 리스트를 이용하기 보단 스택을 만들어 push, pop을 자유롭게 이용하는 것이 열쇠였다. 또한 빼야할 숫자 개수 k가 남았을 때를 현명하게 설정해주는 것이 힘들었다.
import sys N,K = map(int,sys.stdin.readline().split()) numbers = sys.stdin.readline().rstrip() stack = [] for num in numbers: while stack and stack[-1] < num and K >0: stack.pop() K -= 1 stack.append(num) if K > 0: print(‘‘.join(stack[:-K])) else: print(‘‘.join(stack))
- 새로 배운 내용
- stack,list 등에서 일부 범위만 설정할 땐 [:]을 사용하는게 편하다. start,end에 음수 index를 사용할 수 있다.
print(list) print(stack[start:end])
- 참고할 만한 레퍼런스들
- 자료구조와 함께 배우는 알고리즘 입문 파이썬편(BohYoh Shibata 지음, 강민 옮김, 이지스 퍼블리싱)
-
특이사항
- 내일은 알고리즘 2추자 시험날이다. 후회 없이 하자.
- 조가 바뀐다.
-
회고
- 꽤 많은 문제에 대해 이해했고, 익혔지만 여전히 부족하다. 다음주 부턴 세부적으로 수치가 틀린 문제, 알고리즘 방향이 잘못된 문제, 접근조차 못한 문제로 나누어 학습해야겠다.
- TO-DO-LIST
- 2주차 파이썬 알고리즘 시험
- 2주차 파일 정리
