본문 바로가기

전체 글

[자료구조] 그래프(Graph) 개념 정리 그래프란? 그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조이다. 정확히는 정점(Vertex)간의 관계를 표현하는 조직도라고 볼 수 있다. 이러한 면에서 트리는 그래프의 일종인 셈이다. 하지만 그래프는 트리와는 달리 정점마다 간선이 있을 수도 있고 없을 수도 있으며, 루트노드와 부모와 자식이라는 개념이 존재하지 않는다. 그래프와 트리의 차이점에 대해서는 아래의 표로 좀 더 자세하게 설명하겠다. 그래프와 트리의 차이 그래프와 관련된 용어 정점(Vertex) : 노드(node) 라고도 하며 정점에는 데이터가 저장된다. (0, 1, 2, 3) 간선(Edge) : 정점(노드)를 연결하는 선으로 link, branch 라고도 부른다. 인접 정점(adjacent Vertex) : 간선에 의해 직접.. 더보기
[백준] 11286 절댓값 힙 (Python 파이썬) https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 문제 설명 절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다. 배열에 정수 x (x ≠ 0)를 넣는다. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 풀이 과정 이 문제는 두 가지 풀이방법을 이용하여.. 더보기
[백준] 1339 단어 수학 (Python 파이썬) https://www.acmicpc.net/problem/1339 문제 설명 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 풀이 과정 단어에 등장하는 알파벳을 0~9중의 숫자 중 .. 더보기
[백준] 1080 행렬 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1080 0과 1로 이루어진 행렬 A 와 행렬 B가 주어질 때, 행렬 A를 행렬 B로 전환하는데 필요한 횟수를 구하는 문제이다. 이 때, 1회 전환하다는 것은 3x3의 행렬을 뒤집는 것이다. 예를 들어, 000 111 010 101 111 을 뒤집으면 000 이 된다. 풀이 과정 이 문제는 그리디 알고리즘으로 접근할 수 있다. 변환 전의 행렬을 A, 전환 후의 행렬을 B라고 하자. 현재 A 행렬의 내 위치에서 B 행렬과 일치하지 않는 부분이 있다면 그 부분부터 3x3 범위안의 행렬을 뒤집어주면 된다. 즉, 현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집는 것이기 때문에 그리디 알고리즘이라고 볼 수 .. 더보기
[자료구조] 배열과 연결리스트 (Array & LinkedList) 배열 vs 연결리스트 배열 배열은 입력된 데이터들이 메모리 공간에서 연속적으로 저장되어 있는 자료구조이다. 메모리상에서 연속적으로 저장되어 있는 특징을 갖기때문에, index를 통한 접근이 용이하다. 배열의 크기는 처음 생성할 때 정하며 이후에는 변경할 수 없다. 시간복잡도 탐색: O(1) 단, 접근하고자 하는 인덱스를 알고있어야 한다. 순차적으로 탐색시에는 O(n) 삽입 및 삭제: 배열의 처음 또는 중간에 삽입 및 삭제: O(n) 삽입 지점 이후의 데이터를 옮겨야 하기 때문이다. 배열의 끝에 삽입 및 삭제: O(1) 연결리스트 연결리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조이며, 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail) 이라고 한다. 각 노드는 데이터와 다음.. 더보기
[백준] 18352 특정 거리의 도시 찾기(Python 파이썬) https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 설명 도시들의 번호와 각 도시 사이의 거리가 주어지며 목표 거리가 주어질 때, 출발 도시에서 도착도시 까지의 최단거리가 목표거리인 도시들을 출력하는 문제이다. 예를 들어, 출발 도시가 1이고 목표 거리가 5일 때, 도시 2,3,4 까지의 최단거리가 5이면 2,3,4를 출력하면 된다. 아무 도시도 없으면 -1을 출력한다... 더보기
[백준] 1012 유기농 배추 (Python 파이썬) www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 문제 설명 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추.. 더보기
[백준] 2667 단지번호붙이기 (Python 파이썬) www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 문제 설명 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단.. 더보기

티스토리툴바