목록프로그램 (94)
Brise
파이썬을 이용하여 다시 풀어본 드래곤 커브 문제이다. 18년도 삼성전자 코딩 테스트에 기출되었던 문제이고, 보통은 스택을 이용하여 푸는 방식이 일반적인 것 같다. 일전에 풀었을 때는 미리 드래곤 커브를 모두 만들어 놓는 방식으로 만들려고 했다. 드래곤 커브에서는 end 기준으로 90도 회전하도록 되어 있어 아래와 같은 수도코드를 이용하여 최대 generation인 10에 맞추어 모든 행렬을 사전에 만들어 놓고 주어진 수에 합성하는 방식으로 짰었다. 거기다가 C로 짜니 코딩하는 시간이 많이 걸릴 수밖에... ARR1 = find end point and transition to [end_x, end_y] = 0 for all point: ARR2[nx; ny] = [cos sin; -sin -cos]*[x..
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 입출력 예 triangle result [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 (0)7(0) \|\| (0..
DP문제는 아무래도 재귀 형식으로 표현하여 sub 문제들을 해결하여 큰 문제를 해결할 수있도록 하는 틀을 짜는 능력이 중요한것 같다. 이 문제의 경우에는 생각해보았지만, 해당 틀을 떠올리지 못해서 다른 소스코드를 참고하여 짠 코드이다. 발상 방법이야 여러개 있지만 내가 동작 시킨 코드는 아래와 같다. def calc(A, B): ret = set() for a in A: for b in B: ret.add(a + b) ret.add(a - b) ret.add(a * b) if b != 0: ret.add(a // b) return list(ret) def solution(N, number): answer = 0 # merge plus substract times divide result = dict() ..
그래프를 탐색하며 가장 먼 노드를 찾는 문제이다. 나는 BFS를 이용하여 거리를 구한 뒤 가장 먼노드를 찾았다. def solution(n, edge): answer = 0 v = [set() for _ in range(n+1)] visit = [-1] * (n+1) for e in edge: v[e[0]].add(e[1]) v[e[1]].add(e[0]) def bfs(root): from collections import deque queue = deque() queue.append((root, 0)) visit[root] = 0 while queue: n, l = queue.popleft() for e in v[n]: if visit[e] == -1: visit[e] = l+1 queue.appen..
문제 풀이 상 깊이/너비 우선 탐색 유형으로 풀이되는 문제이다. 내가 풀은 방법은 아래와 같다. def solution(n, computers): answer = 0 visited = [0] * n def dfs(i): nonlocal answer visited[i] = 1 for n, c in enumerate(computers[i]): if c == 1: if 0 == visited[n]: visited[n] = 1 dfs(n) for i in range(n): if visited[i] == 0: dfs(i) answer+= 1 return answer통상 깊이우선탐색을 사용할 때는 스택을 사용하고, 너비우선탐색을 사용할 때는 큐를 사용하는데 이 부분이 현재는 익숙하지가 않아 재귀문법으로 풀이하였다...
220404~220407 C++ Design pattern 교육 C++ 언어 내용 요약 Public : 기반 클래스, 파생 클래스, 외부에 모두 공개 protected : 기반 클래스, 파생 클래스에 공개 생성자를 protected에 놓는 경우: 추상적인 개념을 모델링 할 때 생성자를 직접 호출 불가능하게 만들고 파생되는 실체 클래스가 생성자를 호출할 수 있도록 하기 위함. (Abstract class) private : 기반 클래스에게만 공개 upcasting: 객체지향 언어 특성 상 파생클래스의 포인터를 기반 클래스의 객체로 캐스팅할 수 있다. (파생클래스는 기반클래스에서 정의하는 모든 기능을 지원함) 단, 기반클래스 형태일 때 파생클래스에서 정의한 고유 멤버에 접근이 불가능하며 파생클래스에서 정의하..
객체의 멤버 함수나 멤버 데이터에 접근하려면 클래스 내부에서 각 함수나 변수의 이름을 사용하면 되었다. 사실은 이 경우 실 동작은 컴파일러가 직접 함수 선언에 대하여 내부적으로 this라는 인자를 생성하여 각 객체별로 함수나 변수가 동작하도록 변경하여 동작시키는 구조이다. // 3_this1.cpp 126 page ~ #include class Point { int x, y; public: void set(int a, int b) // set(Point* this, int a, int b) { x = a; // this->x = a; y = b; // this->y = b; 처럼 컴파일 됩니다. // this : 현재 멤버 함수를 호출할때 사용한 객체의 주소 std::cout
C언어에서의 static 변수 또는 static 함수는 정해진 영역 내에서만 고유하게 접근 가능한 변수나 함수를 의미한다. 여기서 정해진 영역이란 파일 또는 중괄호({}) 사이에 위치한 섹션을 의미한다. C++에서는 클래스의 선언(아마 구조체에도 static 선언이 가능할 것으로 보인다. 구조적으로..) 의 멤버변수를 static으로 선언할 수 있는데, 이 경우 해당 클래스를 이용하는 모든 인스턴스의 변수가 통일되어 사용된다. 또한 해당 정적 멤버의 경우 정적으로 할당되기 때문에 정의 영역이 클래스 밖에 위치하게 되며 인스턴스가 생성되기 이전에도 활용할 수 있다. // 2_정적멤버1 - 110 page #include //int cnt = 0; // 전역변수. 모든 객체가 공유 한다. // 어디서나 접근..