분류 전체보기

[백준(BOJ)] #2263- 트리의 순회 (파이썬, Python3)

문제 https://www.acmicpc.net/problem/2263 2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제 풀이 이 문제를 풀 때 생각보다 방법이 쉽게 생각나서 빨리 풀겠다 생각했는데 구현에서 애먹어서 성공까지 가는데 오래 걸렸네요..ㅋㅋㅋㅋㅋㅋ 방법 자체는 트리 순회의 특징과 재귀 호출에 대해 어느 정도 알고 있으면 그렇게 어렵지는 않습니다! 트리 --> 2022.07.08 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 트리(Tree) [파이썬으로 배우는 자료구조] 트리(Tree) 1. 트리(Tree)란? ..

[파이썬으로 배우는 자료구조] 우선순위 큐(Priority Queue), 힙(Heap)

우선순위 큐(Priority Queue)란? 일반적인 큐(Queue) 자료구조는 FIFO 구조라는 것을 배웠습니다. 큐 배우기 --> 2022.06.29 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) [파이썬으로 배우는 자료구조] 스택(Stack), 큐(Queue) 1. 스택(Stack) 1.1. 스택이란? 스택은 후입선출의 자료구조로 LIFO(Last In First Out)라고 불리기도 합니다. 실생활에서 예를 들어볼까요? 우리가 보통 접시를 선반에 차곡차곡 쌓아올린 후 쌓여있는 c4u-rdav.tistory.com 그렇다면 우선순위 큐는 무엇을 의미할까요?? 먼저 들어온 데이터를 무작정 먼저 처리하는 구조가 아니라 데이터에 우선순위에 따라 우선순위가 높은..

[파이썬으로 배우는 알고리즘] 그리디(Greedy) 알고리즘

그리디(Greedy) 알고리즘이란? Greedy는 '탐욕스러운'이라는 뜻을 가진 단어로 탐욕 알고리즘이라고도 불리며 말 그대로 선택의 순간마다 당장 좋은 것만 고르는 방법을 의미합니다. 순간의 가장 좋아 보이는 것만 선택하기 때문에 나중에 미칠 영향은 고려하지 않아 지역적으로는 최적이지만 최종적(전역적)인 답에 도달했다고 해서 그것이 최적해라는 보장은 없습니다. 만약 그리디 알고리즘을 적용하여 위와 같은 트리에서 거쳐 가는 노드 값의 합을 최대로 만든다고 하면 순간의 선택만 고려하기 때문에 3 -> 7 -> 9라는 경로로 해는 19가 됩니다. 하지만 실제 최적해는 21(3 -> 5 -> 13)로 이는 그리디 알고리즘이 최적의 해를 보장할 수 없음을 보여줍니다. 따라서 그리디 알고리즘을 적용하려면 지역적으..

[백준(BOJ)] #1285- 동전 뒤집기 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기 첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위 www.acmicpc.net 문제 풀이 저는 이 문제를 해결하기 위해 먼저 행 또는 열을 기준으로 선택하여 뒤집는 모든 경우의 수를 구했습니다. 이때 행을 뒤집는 연산을 할 때 비트마스킹을 적용하여 행을 뒤집는 경우의 수를 구했습니다. 2022.07.15 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] 비트마스크(BitMask) [파이썬으로 배우는 알고리즘] 비트마스크(BitMask) 1. 비트마스크(BitM..

C언어 독학 #10. 조건문

다들 반복문 글에서 다룬 예제는 풀어보셨나요?? 다들 해결하셨을 거라 믿을게요 ㅎㅎ 더보기 #include int main(void) { for (int i = 0; i 2020.07.18 - [프로그래밍언어/c언어] - C언어 독학 #8. 자료형 1. 반복문이란? 반복문이란 말그대로 반복되어 실행되는 문장을 말합니 c4u-rdav.tistory.com 조건문이란? 우리는 보통 어떤 선택에 있어서 기준을 정하고, 이러한 기준을 바로 조건이라고 합니다. 이전 글에서 다룬 반복문에서도 반복을 하기 위해 조건식이라는 것을 사용하여 조건을 충족시키면 반복을 시켰는데, ..

[파이썬으로 배우는 알고리즘] 비트마스크(BitMask)

비트마스크(BitMask)란? 컴퓨터는 내부적으로 모든 데이터를 이진수로 표현을 합니다. 예전에 c언어로 비트 체계와 비트 연산자를 간단히 다룬 적이 있는데 비트에 대해서 궁금하신 분들은 참고하시면 될 것 같아요. 2020.07.17 - [프로그래밍언어/c언어] - C언어 독학 #7. 비트 체계와 비트 연산자 C언어 독학 #7. 비트 체계와 비트 연산자 인삿말 안녕하세요 알다브입니다. 저번 시간에 연산자에 대해서 알아봤습니다. 사실 저번 시간에 비트 연산자까지 다 끝내려했는데 비트 연산자까지 다루면 너무 길어질까봐 이번 글에서 따로 c4u-rdav.tistory.com 비트의 특성을 이용해서 이진수 표현을 자료구조로 쓰는 기법을 비트마스크라고 하며 엄밀히 말하면 알고리즘이라기보다는 일종의 테크닉이라고 볼..

[파이썬으로 배우는 알고리즘] BFS(너비 우선 탐색)

BFS란? BFS(Breadth First Search)는 DFS와 마찬가지로 그래프의 모든 노드를 탐색하는 방법 중 하나로, 너비를 우선으로 탐색한 후 인접한 노드부터 탐색하는 알고리즘입니다. 스택 자료구조를 활용하는 DFS와 달리 BFS에서는 일반적으로 큐 자료구조를 이용합니다. DFS 배우기 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) 1. DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 탐색 알고리즘입니 c4u-rdav.tistory.c..

[백준(BOJ)] #19236- 청소년 상어 (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/19236 19236번: 청소년 상어 첫째 줄부터 4개의 줄에 각 칸의 들어있는 물고기의 정보가 1번 행부터 순서대로 주어진다. 물고기의 정보는 두 정수 ai, bi로 이루어져 있고, ai는 물고기의 번호, bi는 방향을 의미한다. 방향 bi는 www.acmicpc.net 문제 풀이 이 문제는 구현 문제로 DFS 알고리즘을 적용하여 풀었습니다. DFS 알고리즘 --> 2022.07.12 - [알고리즘/개념] - [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) [파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색) 1. DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로..

[파이썬으로 배우는 알고리즘] DFS(깊이 우선 탐색)

DFS란? DFS(Depth First Search)는 그래프의 모든 노드를 탐색하는 방법 중 하나로, 깊이를 우선으로 탐색한 후 더 이상 탐색할 노드가 없다면 이전으로 돌아가 탐색을 이어나가는 탐색 알고리즘입니다. 이 과정에서 재귀 알고리즘을 사용하게 됩니다. 그래프 배우기 --> 2022.07.04 - [CS/자료구조] - [파이썬으로 배우는 자료구조] 그래프(Graph) [파이썬으로 배우는 자료구조] 그래프(Graph) 1. 그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 c4u-rdav.tistory.com 재귀 알고리즘 배우기 --> 2022.07.0..

[백준(BOJ)] #17144- 미세먼지 안녕! (파이썬, PyPy3)

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 문제 풀이 우선 이 문제는 구현 문제로 문제 이해를 이해하고, 문제를 어떻게 코드로 작성할 수 있는지를 확인하는 것으로 느껴졌습니다. 조건을 조금이라도 놓치고 문제를 풀게 되면, 원치 않은 결과를 얻을 수 있으므로 문제를 꼼꼼하게 읽어보는 것이 필수입니다! 미세먼지 확산 과정 미세먼지의 확산은 미세먼지가 있는 모든 칸에서 동시에 일어나기 때문에 2차원 리스트를 순차적으로 돌면서 무턱대고 확..