CS/Algorithm
[백준(Python/Java)] 1987_알파벳 - DFS
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 깊이 우선 탐색(DFS)을 통해 가장 긴 알파벳을 찾는 문제였습니다. 기존에 풀었던 많은 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)를 문제에서는 방문한 곳을 true로 체크하여 재방문을 하지 않도록 알고리즘을 설계했습니다. 하지만 이 문제에서는 깊이 우선 탐색을 하여 방문한 곳들이 최적해가 되지 않을 때, 다시 그 곳들의 방문 여부를 false로 복원하여 다음 탐색에서 방문할 수 ..
CS/Database
[데이터베이스/DB] 정규화에 대해서(1) - 이상(Anomaly)과 함수적 종속성(FD)
0. 오버뷰(Overview) 관계형 데이터베이스에서 설계 시 중복을 최소화하기 위해 데이터를 구조화하는 작업을 정규화(Normalization)라고 합니다. 정규화가 왜 필요한지에 대해 이야기하기 위해서, 아래 간단한 예시를 보겠습니다. 학번 이름 단과대학 과목코드 중간 성적 2016000001 조성현 공과대학 CSE123 A 2016000002 김영희 상경대학 CSE124 B 2016000001 조성현 공과대학 CSE125 C 2016000003 이철수 문과대학 CSE126 F 위 표는 학번, 이름, 단과대학, 과목, 중간 성적을 저장하고 있는 하나의 데이터베이스 스키마입니다. 그리고 학번과 과목코드가 기본 키(Primary Key)로 역할을 하고 있습니다. 학번과 과목코드를 통해 중간 성적을 결정지..
CS/Algorithm
[백준(Python/Java)] 2234_성곽(DFS, 비트마스킹)
https://www.acmicpc.net/problem/2234 2234번: 성곽 첫째 줄에 두 정수 n, m이 주어진다. 다음 m개의 줄에는 n개의 정수로 벽에 대한 정보가 주어진다. 벽에 대한 정보는 한 정수로 주어지는데, 서쪽에 벽이 있을 때는 1을, 북쪽에 벽이 있을 때는 2를, www.acmicpc.net 약간의 비트마스킹을 사용해서 푸는 문제인데, 비트마스킹이 중심인 문제는 아니라고 생각합니다. 단순히 각 방에 위치하는 벽의 정보를 이진수로 바꾸고 남동북서 방향으로 바꿔서 읽어주면 되는 것이죠. 예를 들어, 어떤 방의 벽에 대한 값이 11이라면 11을 2진수로 바꾼 뒤 남동북서 방향으로 네 자릿수를 채우면 0111이 됩니다. 즉, 남쪽에 대한 값만 0로 이동가능하고, 동북서에 대한 값은 1로..
CS/Algorithm
[백준(Python/Java)] 2206_벽 부수고 이동하기(BFS)
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 일반적인 BFS 문제에서 "벽을 부술 수 있는 기회가 1회" 추가된 문제입니다. 따라서 이 문제를 해결하기 위해서는 "어느 벽 하나를 부술 것인가?"를 정할 수 있어야 합니다. 하지만, 임의의 벽을 하나 제거하고 BFS를 수행하는 행위를 반복하면 시간초과가 발생하기 때문에 한 번의 BFS를 진행하는동안 "벽을 부순 상태인지, 부수지 않은 상태인지'를 큐에 담고 다녀야 합니..
CS/Network
[네트워크/Network] TCP는 어떻게 신뢰적인 데이터 전달을 할까?
👀 0. 들어가면서 이번 시간에는 트랜스포트 계층의 프로토콜은 TCP에 대해 이야기해보려고 합니다. UDP에 대한 정리는 아래 포스팅에 있으니 참고해주세요. [네트워크/Network] 비연결형 트랜스포트 UDP 정리 💡0. 들어가면서 이전 포스팅에서 OSI 7계층에 대해 정리를 했었는데요. 트랜스포트 계층의 기본적인 역할은 네트워크 계층과 애플리케이션 레벨 프로세스 간의 데이터를 넘겨주기 위해서 다중 studyandwrite.tistory.com 한편, TCP는 신뢰적인 데이터 전송, 혼잡 제어 등 여러가지 기능을 제공하는 프로토콜이기 때문에 설명할 내용이 굉장히 많습니다. 그래서 앞으로 몇 개의 포스팅에 걸쳐 이러한 내용들을 다뤄보도록 하겠습니다. 우선, 이번 포스팅에서는 TCP의 가장 기본적이면서도 ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 숫자 문자열과 영단어(2021 카카오 인턴십)
https://programmers.co.kr/learn/courses/30/lessons/81301 코딩테스트 연습 - 숫자 문자열과 영단어 네오와 프로도가 숫자놀이를 하고 있습니다. 네오가 프로도에게 숫자를 건넬 때 일부 자릿수를 영단어로 바꾼 카드를 건네주면 프로도는 원래 숫자를 찾는 게임입니다. 다음은 숫자의 일부 자 programmers.co.kr replace 메서드를 사용해서 정말 쉽게 풀 수 있는 문제입니다. 파이썬의 replace 내장 함수는 자바의 replaceAll 함수처럼 해당되는 모든 문자열을 다른 문자열로 치환해주기 때문에, 아래 풀이처럼 number 배열에 있는 문자열이 존재한다면 해당 문자열의 인덱스를 이용하여 숫자로 바꿔주면 됩니다. [풀이] def solution(s): ..
CS/Algorithm
[프로그래머스(파이썬/Python)] 복서 정렬하기(위클리 챌린지 6주차)
https://programmers.co.kr/learn/courses/30/lessons/85002 코딩테스트 연습 - 6주차 복서 선수들의 몸무게 weights와, 복서 선수들의 전적을 나타내는 head2head가 매개변수로 주어집니다. 복서 선수들의 번호를 다음과 같은 순서로 정렬한 후 return 하도록 solution 함수를 완성해주세요 programmers.co.kr 문제에서 요구한 4가지 기준값을 정확히 구하고 해당 기준에 따라 정렬을 수행하면 되는 문제입니다. 특히 이 문제에서는 주어진 weights 배열과 head2head배열 내 원소의 문자열 길이가 동일했기 때문에 인덱싱을 쉽게 할 수 있다는 이점이 있었습니다. 다만, 많은 기업의 코딩테스트 문제들과 마찬가지로 테스트케이스가 모두 통과..
CS/Network
[네트워크/Network] 인터넷은 어떻게 URL 주소의 서버를 찾아갈까? - DNS의 동작 원리
💡 0. 문제 "내가 나인지 증명할 수 있는 방법은 무엇일까요? 가장 쉽게 떠올릴 수 있는 방법은 자신의 주민등록번호를 가지고 이야기하는 것입니다. 하지만 우리는 일상생활에서 자신을 표현할 때 "안녕하세요 저는 960918-1******" 입니다." 라고 표현하지는 않습니다. 복잡하기 때문이죠. 대신에 우리는 "안녕하세요, 저는 조성현입니다"라고 자신의 이름을 가지고 소개를 합니다. 인터넷도 마찬가지입니다. www.naver.com, www.google.com처럼 호스트 네임(Host name)을 통해 자신을 표현합니다. 하지만 우리 사회와는 다르게 문제가 하나 생깁니다. 그것은 바로, "네트워크 통신에서는 IP Address를 통해 인터넷의 위치에 대한 정보를 얻는데, 호스트 네임에는 IP Addres..
CS/Network
[네트워크/Network] 네트워크의 기본: OSI 계층 구조와 캡슐화
🤔 0. 개요 "OSI 7계층이 무엇인가요?" "컴퓨터 네트워크를 왜 7계층으로 나누나요?" "메시지, 데이터그램, 세그먼트의 차이와 캡슐화는 무엇인가요?" CS를 공부해본 사람이라면 한 번쯤은 OSI 7계층에 대해 들어보았을겁니다. 저 역시 전공 수업에서도 배웠고 인터넷에서도 많이 보았던 내용입니다. 하지만 7개의 계층을 외우려고만 했던 시기에 왜 OSI 7계층이 존재하는지, 어떤 모습으로 존재하는지에 대한 이해는 잠시 뒤로 미뤄뒀던 것 같습니다. 그래서 이번 기회에는 OSI 계층 구조, 그리고 이 맥락과 이어지는 캡슐화에 대한 내용에 대해 이해를 해보려고 합니다. (외우지 말고!) 아래는 [컴퓨터 네트워크 하향식 접근]이라는 전공 서적에 있는 그림입니다. 이 그림이 OSI의 계층 구조를 이해하기 쉽게..
CS/Network
[네트워크/Network] TCP 연결 관리와 2, 3, 4 Way Handshaking(핸드쉐이킹)에 대해
📋 1. 오버뷰(Overview) 아래 간략한 설명을 보면서 TCP 핸드셰이킹에 대해 감을 잡아보겠습니다. TCP는 애플리케이션 프로세스가 데이터를 다른 프로세스에게 보내기 전에, 두 프로세스가 서로 "핸드셰이크"를 먼저 해야 한다는 것에서부터 연결지향형(connection-oriented)이라는 특징을 갖고 있습니다. 한 호스트에서 동작하는 프로세스가 다른 호스트의 프로세스와 연결하고 싶다고 해볼까요? 이 때, 연결을 초기화하는 프로세스를 클라이언트 프로세스, 다른 프로세스를 서버 프로세스라고 하겠습니다. 클라이언트 애플리케이션 프로세스는 서버 측의 프로세스와 연결을 설정하기를 원한다고 TCP 클라이언트에게 먼저 말합니다. 그러면 첫번째 TCP 세그먼트를 통해 서버 측 프로세스에게 알림이 가겠죠. "A..
