👩🏻‍💻 은진의 로그파일 ✍️

👩🏻‍💻문제링크 [백준 15686] 치킨 배달 (Python) ✍️Idea Sketch 2021-08-10 1. 출력값 분석하기 치킨거리 : 집과 가장 가까운 치킨집 사이의 거리 집 (x1, y1), 치킨집 (x2, y2) 일 때, 치킨거리는 |x1-x2| + |y1-y2| 이다. 도시의 치킨거리 : 모든 치킨거리의 합 도시의 치킨거리의 최솟값은? 2. 입력값 분석하기 도시의 크기는 n*n 이다. 치킨집은 m개 빼고 다 폐업할 예정이다. 0은 빈칸이다. 1은 집이다. 2는 치킨집이다. 3. 로직 살펴보기 치킨집이 5개고, m이 2인 경우 치킨집 5개 중에 2개를 고르는 모든 조합을 combinations 로 구한다. city_length()에서 치킨거리 min_length 와 도시의 치킨거리 total을..

👩🏻‍💻문제링크 [백준 16234] 인구 이동 (Python) ✍️Idea Sketch 2021-08-09 1. 이번 문제는 80% 에서 시간 초과가 발생해 애를 먹은 문제다. Python3에는 약 1000회의 재귀 제한이 있다. PyPy3는 재귀 제한 횟수가 더 커서 통과할 수 있었다. import sys sys.setrecursionlimit(10**6) 2. BFS와 DFS DFS, BFS 둘 중 어느 것을 해도 상관없지만 BFS로 구현한 사례가 많다. 이번에 DFS로 구현해봤는데 재귀 제한으로 애를 많이 먹었다. 다시 이 문제를 본다면 BFS로 구현해볼 것. 3. 로직 이해하기 로직 이해에 많은 도움이 된 마이구미님 블로그 dfs(x, y) : 상하좌우 인접한 나라와 인구 차이를 확인한다. fla..

👩🏻‍💻문제링크 [백준 14891] 톱니바퀴 (Python) ✍️Idea Sketch 2021-08-09 1. 문제 이해하기 톱니바퀴는 한 칸 이동을 기준으로, K번 회전한다. 시계 or 반시계방향으로 회전한다. A가 회전하기 전 B와 극이 다른 경우, B는 A와 반대 방향으로 회전한다. B와 극이 같은 경우, B는 회전하지 않는다. 2. 입력값 살펴보기 12시부터 시계방향 0은 N극, 1은 S극 회전 횟수 K 회전할 톱니바퀴 번호(num) 및 회전방향 1은 시계방향 -1는 반시계방향 3. 재귀적 로직 예제1 참고) 톱니바퀴 3을 반시계방향으로 회전시켜보자. 톱니바퀴 3과 오른쪽으로 인접한 톱니바퀴 4를 살펴보자. recursion() graph[3][2]와 graph[4][6]의 두 극이 다른 경우, ..

멀티프로그래밍은 여러 개의 프로세스가 동시에 메모리에 로드되는데 각 프로세스가 cpu를 선점해서 concurrent하게 실행되는 것을 멀티 프로그래밍이라고 함 (멀티 테스킹) concurrent의 목적 전제조건 : cpu가 매우 빨라서 놀고있을 때 시분할하여 cpu자원을 사용하는 것 cpu utilization을 늘리기 위해 스케줄링이 필요함 cpu 스케줄러 ready상태의 프로세스들 중에 cpu를 할당해줄 수 있는 프로세스를 선택 현 cpu running 중인 프로세스가 있고 ready인 프로세스 중 어느 프로세스를 선택할 것인가? preemptive(선점형) vs non-preemptive (비선점형) 선점형 : 강제로 쫓아낼 수 있다. 자발적으로 나가게 스케줄러가 할당 중인 프로세서를 쫓아낼 수 있..

👩🏻‍💻문제링크 [백준 10026] 적록색약 (Python) ✍️Idea Sketch 2021-08-03 1. 문제가 요구하는 출력값은? 적록색약이 아닌 사람은 R, G, B 세 종류로 구역을 나눈다. 적록색약인 사람은 R=G, B 두 종류로 구역을 나눈다. 두 사람이 인지하는 구역의 수를 각각 출력해야 한다. 2. main 로직 입력값을 받아 graph를 작성한다. 방문여부를 저장하는 visited를 작성한다. 모든 color를 방문하므로 이중 반복문을 사용한다. for i in range(n): for j in range(m): # graph[i][j] 적록색약이 아닌 사람 1) 처음 방문한 경우, 새로운 구역을 인지한 것이다. 2) 따라서 result += 1 을 실행한다. 적록색약인 사람 0) c..

👩🏻‍💻문제링크 [백준 7576] 토마토 (Python) ✍️Idea Sketch 2021-08-02 1. 예상 출력값 1) 처음부터 모두 익은 경우, 즉 입력값에 0이 없는 경우에는 0을 출력한다. 2) 0이 모두 1이 되기까지 걸리는 최소 날짜를 출력한다. 3) 모두 익지는 못하는 경우, 즉 모든 연산이 끝난 후에도 0이 남아있는 경우에는 -1을 출력한다. 2. main 로직 입력값을 받아 graph 에 정리한다. 익은 토마토의 x, y 인덱스를 queue에 저장한다. queue의 첫번째 요소 x, y를 pop한다. dfs 연산을 하기 위해 방문여부를 초기화한다. (visited[y][x] = 0) dfs(x, y) 함수를 호출한다. 3. DFS 로직 경계값을 분석한다. 처음 방문하면서 1) 익은 토..

👩🏻‍💻문제링크 [백준 1759] 암호 만들기 (Python) ✍️Idea Sketch 2021-07-29 1. 풀이법 방법 1. DFS 조합 구현 방법 2. itertools 라이브러리 사용 from itertools import combinations words = combinations(alpha, L) # combinations(조합할 원소의 배열, 조합할 원소의 개수) 2. 서로 다른 L개의 알파벳을 뽑은 후(조합), 문제조건을 만족할 때 print 3. 놓친 부분 : 입력값을 받자마자 정렬하기 올바른 코드 L, C = map(int, input().split()) alpha = sorted(input().split()) #1, 입력값을 받자마자 정렬할 것 문제상황 : 아래와 같이 print할 ..

👩🏻‍💻문제링크 [백준 2309] 일곱 난쟁이 (Python) ✍️Idea Sketch 2021-07-29 1. 브루트 포스(brute force) = 무식한 힘 = 완전탐색 알고리즘 2. i는 0부터 8번째까지 탐색, j는 i+1부터 9번째까지 탐색 for i in range(8): for j in range(i+1, 9): 3. 이중 반복문 종료하기 방법 1 : 함수 선언 후 return 방법 2 : sys.exit(0) 사용 ✍️소스코드 2021-07-29 방법 1. 함수 선언 후 return, 80ms 통과 height = sorted([int(input()) for _ in range(9)]) total = sum(height) def solution(): for i in range(8): fo..

👩🏻‍💻문제링크 [백준 1012] 유기농 배추 (Python) ✍️Idea Sketch 2021-08-02 1. 단지번호붙이기와 같은 DFS 로직 2. 오랜만에 풀어서 잊은 것 main에서 dfs()를 호출할 때 이중반복문을 사용해서 2차원 배열 graph 의 모든 원소를 확인한다 3. dx dy 사용 시 소요시간 4ms 증가 (96ms) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def dfs(x, y): if (0

👩🏻‍💻문제링크 [백준 2178] 미로 탐색 (Python) ✍️Idea Sketch 2021-07-28 1. 백준 입력값 처리에서 헤맸던 문제 sys.stdin.readline() : 한 줄을 입력받으며, input()과 비슷하다. split() : 띄어쓰기를 기준으로 원소를 나눈다. rstrip() : 우측 \n를 제거한다. list(map(int, sys.stdin.readline().rstrip())) : 한 줄 입력받고, 우측 \n을 제거한 후, 모든 원소를 int형으로 변환한 배열을 생성한다. N, M = map(int, sys.stdin.readline().split()) graph = [list(map(int, sys.stdin.readline().rstrip())) for _ in ran..