본문 바로가기

분류 전체보기239

http VS https 에 대하여 오늘의 주제 http 와 https 에 대한 내용은 http에한 개념적인 내용은 생략하고, http를 알고 있다는 가정하에 설명을하도록 하겠습니다. http 에 대한 내용이 궁금하시거나? 잘 모르시겠다면 아래에 제가 정리한 블로그 글을 읽고 오시면 좋을 거 같습니다 https://devnuts.tistory.com/71?category=1003683 HTTP 란? HTTP(HyperText Transfer Protocol)는 인터넷에서 데이터를 주고 받을 수 있는 프로토콜입니다. 이번 주제를 알아보기 전에, 프로토콜에 대해서 먼저 설명하도록 하겠습니다. 프로토콜 공통 데이터 교환 devnuts.tistory.com https://devnuts.tistory.com/72?category=1003683 HT.. 2022. 4. 30.
TDD란? 테스트 주도 개발(Test Driven Development) 에 대한 프로그래머들의 의견은 늘 엇갈렸습니다. TDD의 실효성을 업무로 경험한 사람들은 TDD를 더 효과적으로 실무에 적용하기 위해 고민을 합니다. 반면, 회사마다 일하는 방식이나 처한 업무 환경이 다르고 편차가 있다보니, 일각에서는 실무에서 TDD를 사용하는 건 사실상 현실과 괴리감이 크다는 의견도 있습니다. 지금부터 TDD가 무엇인지 알아봅시다. TDD 실제 동작하는 코드를 작성하기 전에, 테스트를 먼저 작성함으로 개발의 흐름을 테스트로 끌고 가는 개발 방법입니다. 개발자는 먼저 자신이 구현할 기능에 대해서 테스트를 작성하고, 테스트를 통과하는 코드를 작성함으로 수행 결과가 보증된 소프트웨어를 개발해 갑니다. 반복 테스트를 이용한 소프트.. 2022. 4. 30.
[백준 *Java] - 이모티콘(14226) 이모티콘 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초가 걸린다. 또, 클립보드에 이모티콘을 복사하면 이전에 클립보드에 있던 .. 2022. 4. 27.
[백준 *Java] - BFS 스페셜 저지 (16940) BFS 스페셜 저지 16940번: BFS 스페셜 저지 올바른 순서는 1, 2, 3, 4와 1, 3, 2, 4가 있다. www.acmicpc.net 👇 문제보기 더보기 문제 설명 BOJ 에서 정답이 여러가지인 경우에는 스페셜 저지를 사용합니다. 스페셜 저지는 유저가 출력한 답을 검증하는 코드를 통해서 정답 유무를 결정하는 방식입니다. 오늘은 스페셜 저지 코드를 하나 만들어 보려고 합니다. 정점의 개수가 N이고, 정점에서 1부터 N까지 번호가 매겨져 있는 양방향 그래프가 있을 때, BFS 알고리즘은 다음과 같은 형태로 이루어져 있습니다. 큐에 시작 정점을 넣는다. 이 문제에서 시작 정점은 1이다. 1을 방문했다고 처리한다. 큐가 비어있지 않은 동안 다음을 반복한다 큐에 들어있는 첫 정점을 큐에서 꺼낸다. 이.. 2022. 4. 25.
최단거리 문제에 대한 고찰 최단 경로 문제는 가중치 없는 그래프에서는 보통 두 정점을 잇는 가장 적은 간선의 개수를 뜻합니다. 반대로 가중치가 있는 그래프에서는 두 정점을 잇는 간선들의 가중치의 합 중 최소 가중치 합을 의미합니다. 알고리즘 공부하고, 코딩테스트 문제를 접하다보면? 가중치 없는 그래프(unweighted graph)인 경우 BFS를 사용하고, 가중치가 0과 1이 존재할 때 역시 BFS를 사용한다고 생각합니다. 그리고 가중치가 여러 개가 존재한다면 다익스트라 알고리즘을 사용하라고 합니다. 이번 주제에선, 왜 최단거리에선 DFS를 사용하지 않고 BFS를 사용하는 지? 와 간선이 0과 1일 때는 다익스트라 알고리즘을 사용하기보단, 0-1 알고리즘을 사용하는 지? 에대한 설명을 드릴 생각입니다. 최단 경로를 탐색할 때 D.. 2022. 4. 25.
너비 우선 탐색(Breadth-First-Search) BFS 그래프 전체를 탐색하는 방법 중 하나로, 루트 노드 또는 다른 임의의 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점을부터 가까운 정점을 먼저 방문하고, 멀리 떨어져 있는 정점을 나중에 순회함으로 써 노드를 넓게(wide)하게 탐색을 합니다. 더 설명하자면, BFS는 해를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색(Uniformed search)입니다. 달리 말하자면, 목표에 대한 고려없이 목표가 발견될 때까지 전체 트리 또는 그래프를 전부 탐색하고, BFS는 휴리스틱을 사용하지 않습니다. (반대로 휴리스틱을 사용하는 알고리즘은 ex) Greedy best-first search 또는 A*) 👇 search 의 두 분류 더보기 Uniformed search .. 2022. 4. 24.
[백준 *Java] - 트리의 지름(1167) 트리의 지름 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오. 입력 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다. 먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 .. 2022. 4. 22.
트리의 지름 구하기 [증명] 트리의 지름 트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은, 먼 두 정점을 연결하는 경로를 의미합니다. 선형 시간안에 트리에서 지름을 구하는 방법은 아래 Flow를 기억해두시면 좋습니다. 트리에서 임의의 정점 x를 잡습니다. 정점 x에서 가장 먼 정점 y를 찾습니다. (dfs / bfs 사용) 정점 y에서 가장 먼 정점 z를 찾습니다. (dfs / bfs 재사용) 이렇게 위 flow 대로 생각하면, 트리의 지름은 정점 y와 정점 z를 연결하는 경로가 됩니다. 여기서 이렇게하면 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 일컫게 됩니다. 증명을 하자면, 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하겠습니다. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y.. 2022. 4. 22.

티스토리툴바