Log

개발 진행 및 완료 상황 3주차 python algorithm 난이도 중 이하 문제 풀이 완료 CSAPP 3.3 까지 공부 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 9084 동전(https://www.acmicpc.net/problem/9084) 풀이 과정 : j원을 만들 수 있는 경우의 수를 dp[j]라 한다면 동전의 한 종류인 i원을 더한 j+i원을 만드는 경우의 수도 dp[j+i]를 더함으로서 구할 수 있다. 정답코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 import sys ans = [] t = int(sys.stdin.readline()) for _ in range(t): n = int(sys.stdin.readline()) coin = list(map(int,sys.stdin.readline().split())) m = int(sys.stdin.readline()) dp = [0] * 10001 dp[0] = 1 for i in coin: for j in range(1,m+1): if j-i >= 0: dp[j] += dp[j-i] ans.append(dp[m]) print(*ans, sep='\n') 출처 : ...

1.개발 진행 및 완료상황 2주차 python algorithm 문제풀이 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2252 2252번: 줄 세우기 2252번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 줄 세우기 스페셜 저지 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 37709 21883 14481 56.278% 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, … ...

1.개발 진행 및 완료상황 2주차 python algorithm bfs 문제 풀이 중 CSAPP 2주차 목표 읽기 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 18352 18352번: 특정 거리의 도시 찾기 문제 어떤 나라에는 1번부터 N 번까지의 도시와 M 개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다. 이 때 특정한 도시 X 로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K 인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오. 또한 출발 도시 X 에서 출발 도시 X 로 가는 최단 거리는 항상 0이라고 가정한다. 예를 들어 N =4, K =2, X =1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자. 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서, 최단 거리가 2인 도시는 4… ...

1.개발 진행 및 완료상황 2주차 python algorithm dfs 문제 1회독 완료 CSAPP 2주차 목표 읽기 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2644(파이썬) 2644번: 촌수계산 문제 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다. 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오. 입력 사람들은 1, 2… ...

1.개발 진행 및 완료상황 3주차 python algorithm 그래프 탐색 기본 개념 공부 3주차 python algorithm 그래프 탐색 기본 문제 풀이 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 1991 1991번: 트리 순회 1991번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 트리 순회 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 43388 28410 21707 66.502% 문제 이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오. 예를 들어 위와 같은 이진 트리가 입력되면, 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 … ...

1.개발 진행 및 완료상황 2주차 python algorithm 종료 3주차 python algorithm 시작 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 1715 1715번: 카드 정렬하기 1715번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 카드 정렬하기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 46099 15534 11930 33.435% 문제 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶… ...

1.개발 진행 및 완료상황 2주차 python algorithm 틀린 문제 복습 완료 CSAPP 2주차 목표 읽기 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 백준 2110(파이썬) 2110번: 공유기 설치 2110번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 공유기 설치 다국어 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 55494 18901 13282 36.209% 문제 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x 1 , …, x N 이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수… ...

자료구조와 시간복잡도에 관한 무작위 정리 큐와 우선순위 큐의 시간복잡도차이 우선순위 큐 구현시 리스트, 힙자료구조 사용 가능 데이터 N개일때, 리스트기반시 최악의 경우 복잡도는 O(N^2), 힙은 O(NlogN) 데이터 갯수가 많아질수록 복잡도는 기하급수적으로 증가. 리스트와 딕셔너리의 차이점 list : 순서 존재, index 존재, mutable, index지정하여 값변경 가능 , 존재확인하는 in연산자는 하나씩 스캔후 반환하여 오래걸린다(성능 낮음) tuple : 순서 존재, index존재, immutable, immutable,같이 저장시 list보다 적은용량(수정 필요없고 간단한형태는 tuple이 좋다) unpacking(튜플의 값 차례대로 변수에 대입 가능 a,b = b, a가 그예임. 하나씩 안넣어도됨) dictionary : key와 value로 구성, 중복불가, 순서x, 크기와 무관하게 in 연산 속도 일정(key값만 찾으니까) set : key값으로만 구성, 중복불가, 순서 X ...

1.개발 진행 및 완료상황 2주차 python algorithm 문제 1회독 완료 이분탐색 백준 문제 복습 완료 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 코드 구성에 있어서 전체적인 구조가 잘못되기 보다는 세부적으로 틀려 반례가 존재하여 오답처리 되는 경우가 많았다. 반례를 찾는게 꽤 힘들었는데 같은 수의 입력, 최솟값 이나 최댓값 입력 등인 경우가 많았다. 범위 설정 등에서 신경을 많이 썼다. 새로 배운 내용 기존에 list.sort() 를 통해 오름차순으로 정렬하는 방법을 썼다. 하지만 리스트 내 원소가 리스트인 경우, 내부 리스트의 특정 index에 맞춰 정렬한다거나, 내림차순으로 정렬하는 등 세부적인 옵션을 부가하는 방법을 몰랐다. 첫번째 줄은 정렬 후 저장하여 원형이 변형되는 경우, 두번째는 변형되지 않는 경우, 세번째줄은 reverse = True 일경우 내림차순정렬이 된다. 마지막으로 리스트인 원소의 두번째 값으로 오름차순 정렬하는 코드이다. list.sort() sorted(list) list.sort(reverse = True) list.sort(key = lambda x : x[1]) ...

1.개발 진행 및 완료상황 2주차 python algorithm 우선순위 큐 문제풀이중 업무, 개발 중 발생한 이슈/고민 또는 이를 해결한 내용 priority queue 문제를 풀때 heapq를 사용해야 하는지, 기본적인 in-built함수로 구현할 줄 알아야 하는지 궁금했다. 코치님께 질문하였는데, 그 이유를 스스로 생각해보고 찾길 원하셨는지 여러가지 질문들을 하셨다. 시간복잡도, 자료구조, list, stack, queue등을 물어보셨는데 답변을 못하였다. 기초적인 개념들에 대한 이해가 부족하다는 것을 뼈저리게 느꼈다. 이와 관련된 공부들은 3번에 후술하였다. 새로 배운 내용 array 와list, tuple, dictionary, set의 개념과 차이 : ...