본문 바로가기

전체 글

 (129)
Baekjoon 2263. 트리의 순회 / Python 2263. 트리의 순회난이도 : 골드 1소요 시간 : 10분날짜 : 2024.12.30언어 : 파이썬알고리즘 유형 : 재귀, 트리, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명트리의 크기 n이 주어짐중위순회(inorder)와 후위순회(postorder)가 주어짐전위순회(preorder)결과를 구하기.2. 해결 방식중위순회는 왼쪽부터 하위트리를 우선으로 트리를 방문 후 루트를 방문하는 방식후위순회는 왼쪽부터 "하위트리를 모두 방문한 후" 루트를 방문하는 방식전위순회는 루트노드부터 시작하여 왼쪽 자식먼저 방문하는 방식재귀함수의 원리 및 사용후위순회의 마지막 요소는 현재 서브트리의 루트 노드이다.중위순회에서의 루트를 기준으로 왼쪽, 오른쪽으로 서브트리를 나눈다.루트 노드를 출력한다.(전위순회)3...
Baekjoon 12850. 본대 산책 2 / Python 12850. 본대 산책 2난이도 : 골드 1소요 시간 : 15분날짜 : 2024.12.29언어 : 파이썬알고리즘 유형 : 행렬, 그래프, 분할 정복설명 보기전에 문제 풀어보러 가기1. 문제 설명그래프가 주어진다. 만들어야 한다. 귀찮다....d분동안 산책한다.정보과학관을 돌아오는 경로의 경우의 수를 구한다.2. 해결 방식행렬에 대한 이해를 필요로 하는 문제이다.i분 산책한 경로 배열 * j분 산책한 경로 배열 을 하면 i+j분 산책을 한 경로를 구할 수 있다.이를 활용하면 시간복잡도를 log2(d)로 해결가능.3. 정답 코드# 숭실대 지도 그리기arr = [[0] * 8 for _ in range(8)]arr[0][1], arr[1][0] = 1, 1arr[0][2], arr[2][0] = 1, 1arr..
Baekjoon 28707. 배열 정렬 / Python 28707. 배열 정렬난이도 : 골드 1소요 시간 : 20분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 다익스트라, 그래프, 해시, 트리, 최단 경설명 보기전에 문제 풀어보러 가기1. 문제 설명배열 A가 주어진다.커맨드 l, r, c가 주어진다 : l과 r을 바꾼다. c의 비용이 든다.커맨드들을 이용해서 최소비용으로 정렬하라.2. 해결 방식배열을 문자열로 저장한다.배열을 목표배열까지 가는 최소경로를 구하면 된다.다익스트라를 활용하여 최소비용을 구한다.3. 정답 코드import sysinput = sys.stdin.readlinefrom heapq import heappop, heappushfrom collections import defaultdictn = int(input()) # ..
Baekjoon 10775. 공항 / Python 10775. 공항난이도 : 골드 2소요 시간 : 15분날짜 : 2024.12.28언어 : 파이썬알고리즘 유형 : 그리디, 분리집합설명 보기전에 문제 풀어보러 가기1. 문제 설명G개의 게이트와 P개의 비행기가 있다.비행기를 게이트에 도킹해야 한다.$g_i$가 입력으로 주어지고, 1 ~ $g_i$ 의 게이트에 i번 게이트를 도킹해야한다.게이트에 도킹을 할 수 없으면 끝도킹 수의 최댓값을 구하자.2. 해결 방식union-find 알고리즘을 사용한다. - 게이트에 각자의 게이트 번호를 부여한다. - 비행기번호를 union-find를 통해 게이트 집합을 만들어 관리한다.3. 정답 코드import syssys.stdin = open("C:/Users/ghtjd/Desktop/tmp/python/input..
알고리즘 유형공부 - 우선순위 큐 (Priority Queue) 우선순위 큐 (Priority Queue)1. 개요우선순위 큐는 각 원소에 우선순위를 부여하여, 우선순위가 높은 원소가 먼저 처리되도록 하는 데이터 구조일반적인 큐는 FIFO(First In, First Out) 방식이지만, 우선순위 큐는 우선순위를 기준으로 순서가 정해짐. 주로 힙을 사용하여 구현되며, 배열이나 연결 리스트를 통해서도 만들 수 있음.2. 우선순위 큐의 특성1. 원소의 입, 출삽입: 새로운 원소를 큐에 추가삭제: 가장 높은 우선순위를 가진 원소를 큐에서 제거조회: 현재 가장 높은 우선순위를 가진 원소를 반환2. 배열, 연결리스트, 힙을 통한 우선순위 큐구현 방식삽입 시간복잡도삭제 시간복잡도공간복잡도특징배열 (정렬X)O(1)O(N)O(N)삽입은 빠르지만 삭제 시 전체를 탐색해야 함.배열 ..
Baekjoon 19236. 청소년 상어 / Python 19236. 청소년 상어난이도 : 골드 2소요 시간 : 35분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 백트래킹, 구현, 시뮬레이션설명 보기전에 문제 풀어보러 가기1. 문제 설명상어 이동, 물고기 이동 을 반복함.상어 이동경계 안에서만 이동물고기가 있는 곳으로만 이동여러 칸 이동 가능물고기의 방향을 흡수?함이동 불가 : 집으로 감물고기 이동번호 작은 물고기부터 순서대로 이동경계 안에서만 이동한 칸만 이동상어 있는 곳으로 이동 불가다른 물고기가 있다면 자리 교체이동 불가 : 이동 안함"잡아먹은 물고기 번호의 합"의 최댓값을 구하라.2. 해결 방식dfs + 백트래킹상어 이동방향에 맞게 이동시키고 해당 자리의 물고기를 배열에서 없앤다.이동할 때마다 res를 max 값으로 갱신했다.물고기 이동각..
Baekjoon 9527. 1의 개수 세기 9527. 1의 개수 세기난이도 : 골드 2소요 시간 : 25분날짜 : 2024.12.27언어 : 파이썬알고리즘 유형 : 수학, 비트마스킹, 누적 합설명 보기전에 문제 풀어보러 가기1. 문제 설명$(x)$는 $x$를 이진수로 표현했을 때에 1의 개수를 의미 한다.$a, b$가 주어지면 $$\sum_{x=a}^{b} f(x)$$ 를 구한다.2. 해결 방식음 나는 그냥 재귀함수와 수학으로 풀었는데. 알고리즘 유형은 비트마스킹과 누적 합이라고 한다.내가 사용한 비트마스킹은 연산을 전혀 사용하지 않고 2 ** index를 left shift를 이용해서 표현한 것 뿐..$c = 2 ^ n$ 일 때, $$\sum_{x=0}^{c} f(x) = \frac{n * c}{2} + 1$$ 이다.따라서, $x$ 보다 작은 ..
Every CS - Hardware 01 - 컴퓨터 구조 Hardware 01 - 컴퓨터 구조1. 컴퓨터가 이해하는 정보컴퓨터는 사람이 이해하는 방식과는 다르게 정보를 처리한다.컴퓨터는 모든 데이터를 이진수로 변환하여 처리한다.이진수는 0과 1로 이루어진 수로, 전기 신호의 ON(1)과 OFF(0) 상태를 나타내는 방법이다.따라서, 컴퓨터는 모든 정보를 이진수로 변환하고, 연산과 저장을 이진수 형태로 수행한다.이진수는 비트(bit) 단위로 표현되며, 여러 비트들이 모여 바이트(byte)가 된다.1 바이트는 8 비트로 구성되며, 컴퓨터는 이 바이트를 단위로 데이터를 다룬다.예를 들어, 1 바이트는 256가지의 서로 다른 값을 표현할 수 있다.컴퓨터는 텍스트, 이미지, 비디오 등 다양한 정보를 모두 이진수로 바꿔 처리한다.2. 컴퓨터의 핵심 부품컴퓨터의 핵심 부품..
알고리즘 유형공부 - 다익스트라 (Dijkstra) 다익스트라 (Dijkstra)1. 개요다익스트라 알고리즘은 가중치가 양수인 그래프에서 특정 시작점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 2. 알고리즘의 원리시작 정점을 기준으로 초기 거리를 설정하며, 시작 정점의 거리는 0으로 설정한다.방문하지 않은 정점 중에서 가장 가까운 정점을 선택한다.선택한 정점을 기준으로 인접한 정점들의 거리를 갱신한다.모든 정점이 반복될 때까지 반복한다.3. 구현3-1. 구현 1 - 인접 행렬 방식설명동작 방식그래프를 인접 행렬로 표현하며, 각 정점 간의 연결 여부와 가중치를 행렬로 나타냄방문 여부를 저장하는 배열과 현재까지의 최소 서리를 저장하는 배열 사용모든 정점을 순회하며, 최소 거리를 갱신시간복잡도시간복잡도는 O(V ^ 2)이다.코드파이썬 코드im..
Baekjoon 17143. 낚시왕 / Python 17143. 낚시왕난이도 : 골드 1소요 시간 : 50분날짜 : 2024.12.26언어 : 파이썬알고리즘 유형 : 구현, 시뮬레이션설명 보기전에 문제 풀어보러 가기1. 문제 설명낚시왕이 오른쪽으로 한 칸 이동한다.낚시왕이 있는 열에 있는 상어 중 제일 가까운 상어를 잡는다.잡힌 상어는 사라진다.상어가 이동한다.상어진 주어진 속도로 이동하고, 경계와 만나면 방향을 반대방향으로 바꾸어 이동한다.방향이 바뀌어도 속력은 유지한다.상어가 이동을 마친 후에, 한 칸에 상어가 두 마리 이상 있다면, 크기가 큰 상어가 작은 상어를 모두 잡아먹는다.낚시왕이 잡은 상어의 크기의 합을 구한다.2. 해결 방식입력격자판의 크기 R, C, 상어의 수 MM개의 줄에 입력상어의 위치 r,c, 속력 s, 이동방향 d, 크기 z해결상어..

티스토리툴바