본문 바로가기

전체 글158

객체 지향 프로그래밍이란 무엇인가 객체 지향 프로그래밍(Object Oriented Programming). 학교 수업에서도 회사 면접에서도 중요하게 다루지만 객체 지향 프로그래밍이 뭔지 아직도 정확히 이해하지 못했다. OOP에 대해 한번 알아보자. 객체 지향 프로그래밍이란 인간 중심적 프로그래밍 패러다임이다. 현실 세계를 프로그래밍으로 가져와서 사용하는 것을 말한다. 현실 세계의 사물들을 객체라고 보고 그 객체로부터 개발하고자 하는 어플리케이션에 특징들을 뽑아와 프로그래밍 하는 것이다. 이것을 추상화라고 한다. OOP로 코드를 작성하면 재사용성이 높다. 로직을 라이브러리로 만들어 두면 계속해서 사용할 수 있고, 신뢰성을 확보할 수 있다. 또한 각각의 라이브러리의 예외상황을 잘 만들어 두면 버그 발생도 줄일 수 있고, 내부의 세밀한 동작.. 2021. 10. 12.
백준 16958번 - 텔레포트 https://www.acmicpc.net/problem/16958 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 플로이드-와샬 알고리즘으로 해결 가능한 문제입니다. N이 1000이라 플로이드 알고리즘을 사용하면 시간복잡도가 O(n^3) 이기 때문에 사용하지 못할줄 알았으나 가능했습니다. 텔레포트로 이동하는경우와 맨허튼거리계산과 비교해서 작은 값을 먼저 넣어줍니다. 그 다음에 플로이드 알고리즘을 사용하면 끝~ #include #include #include usin.. 2021. 10. 6.
Spring Boot - Getter, Setter 스프링 프로젝트를 진행할때 Getter Setter 메소드를 일일이 입력해주는 것은 아주 귀찮은 일이다. 이때 Lombok을 이용하면 쉽게 이 메소드들을 구현할 수 있다. 먼저 Lombok을 다운로드 받은 후에 아래와 같이 build.gradle의 기입하고 rebuild 해준 뒤에, dependencies { compileOnly 'org.projectlombok:lombok:1.18.12' annotationProcessor 'org.projectlombok:lombok:1.18.12' testCompileOnly 'org.projectlombok:lombok:1.18.12' testAnnotationProcessor 'org.projectlombok:lombok:1.18.12' } 아래처럼 사용해주면.. 2021. 10. 5.
웹 통신의 큰 흐름 https://www.google.com/을 을 접속하면 무슨 일이 일어날까? 면접 단골 문제라고 합니다. 브라우저는 URL에 적힌 값을 파싱해서 HTTP Request Message를 만들고, OS에 전송 요청을 합니다. 이 때, Domain으로 요청을 보낼 수 없기 떄문에 DNS Lookup을 수행합니다. DNS 룩업 과정은 도메인에 매칭되는 ip를 찾는 과정입니다. DNS Lookup은 루트 도메인서버에서부터 서브도메인서버 순으로 Domain을 찾게됩니다. OS에 전송 요청한 것은 프로토콜 스택이라는 OS에 내장된 네트워크 제어용 소프트웨어에 의해 패킷에 담기고 패킷에 제어정보를 덧붙여 LAN 어댑터로 전송하고, LAN 어댑터는 이를 전기신호로 변환시켜 송출합니다. 패킷은 스위칭, 허브 등을 경유하.. 2021. 10. 4.
그래프 정점과 간선의 집합을 그래프라고 한다. 트리는 사이클이 허용되지 않는 그래프이다. 정점(vertex)와 간선(edge)의 연결관계에 있어서 방향성이 없는 그래프를 Undirected Graph, 방향성이 있는 그래프를 Directed Graph라고 한다. 또한 간선에 가중치가 있는 그래프를 가중치 그래프라고 부른다. 그래프를 구현하는 방법은 두가지가 있다. 하나는 인접행렬을 통해서 구현하는 방법, 하나는 인접리스트를 통해 구현하는 방법이 있다. 인접 행렬로 그래프를 구현할 경우에는 정점 i와 j가 연결되어있는지 확인하려면 단순히 graph[i][j]를 확인해주면 된다. 즉 O(1)의 시간동안 연결관계를 파악할 수 있다. 하지만 간선(edge)의 갯수와 관계없이 V^2의 공간 복잡도를 갖는다는 단점이 있다.. 2021. 10. 4.
TCP와 UDP TCP란? TCP는 Transmission Control Protocol의 약자로 전송제어 프로토콜을 뜻합니다. TCP는 3-way handshake를 통해서 신뢰할 수 있고 정확한 데이터를 전달하는 프로토콜입니다. 데이터를 패킷(세그먼트)이라는 여러 개의 작은 조각으로 분할 해서 수신지에 보내고, 패킷의 도착을 ACK를 통해 확인하고, 수신한 패킷을 재조립해서 전체 데이터의 순서를 올바르게 조정합니다. TCP에서 데이터를 분할하는 단위를 MSS(Maximum Segment Size)라고 합니다. 그리고 분할된 데이터에 순서 번호를 부여하여 재조립할 수 있게 합니다. TCP는 연결 중심형이기 때문에 connection마다 buffer를 할당해서 connetion마다 순서를 조립합니다. 세그먼트는 MSL(.. 2021. 10. 4.
백준 20500번 - Ezreal 여눈부터 가네 ㅈㅈ https://www.acmicpc.net/problem/20500 20500번: Ezreal 여눈부터 가네 ㅈㅈ 문제의 답을 $1\,000\,000\,007$로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명이 아주 깔끔해서 맘에 드는 문제다. 1과 5로만 구성된 n자리의 수가 15의 배수가 되는 경우의 수를 구해야 한다. 15는 3*5이므로 15의 배수는 5,0으로 끝나면서 자릿수의 합이 3의 배수여야한다. 즉 이 문제의 경우에는 1의 자릿수가 5가 되면서 총 자릿수들의 합이 3의 배수가 되면 된다. 자릿수가 3의 배수가 되는 경우에 한해 5151515, 1111115 같은 경우의 수를 계산해줘야 한다. 1의 자릿수는 5 고정이므로 앞의 n-1개의 자리에 5가 어디어디에 들어갈지 고려.. 2021. 10. 4.
백준 14852번 - 타일 채우기(3) https://www.acmicpc.net/problem/14852 14852번: 타일 채우기 3 첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net DP문제의 기본형에서 1*1의 타일이 생기면서 조금 더 생각을 할 필요가 있는 문제였다. 원래는 간단하게 DP[i]=DP[i-1]+DP[i-2] 의 형식으로 해결이 가능하지만, 1*1의 경우가 생김으로써 DP[i]=DP[i-1]*2 + DP[i-2]*3 의 경우를 생각해야 한다. ㅁㅁㅁㅇ ㅁㅁㅁ| ㅁㅁ-- ㅁㅁ-- ㅁㅁㅇㅇ ㅁㅁㅁㅇ ㅁㅁㅁ| ㅁㅁ-- ㅁㅁㅇㅇ ㅁㅁ-- 여기에 밑에 경우를 생각해 줘야 한다. 즉, DP[i-3]*2의 경우, DP[i-4]*2의 경우, ... , D[0]*2의 경우를 생각해줘야.. 2021. 10. 4.
소수점 개수 조절하기 백준에서 문제를 풀다 보면 소수점 개수를 조절해야할 필요가 있을 때도 있다. 그럴때는 아래의 코드처럼 사용하면 된다. #include using namespace std; int main(){ double answer=123.4567 cout 2021. 10. 4.
해시 테이블 해시 테이블(Hash Table) 해시는 내부적으로 배열을 사용해서 데이터를 저장한다. 그래서 평균적으로 O(1)의 시간 복잡도로 검색이 가능하다. (collision때문에 평균적으로 라는 말이 붙는다.) 하지만 문제는 이 인덱스로 저장되는 키(key)값이 불규칙하다는 것이다. 그래서 특별한 알고리즘을 이용하여 저장할 테이터와 연관된 고유한 숫자를 만들어 내 이를 인덱스로 사용한다. 이 특별한 알고리즘을 해시 함수(hash function)이라고 한다. 좋은 해시 함순는 키 전체를 참조해서 해시 값을 만들어 낸다. 해시 함수를 무조건 1:1로 만드는 것보다 Collision을 최소화하는 방향으로 설계하고 발생하는 Collision에 대비해 어떻게 대응할 것인가가 중요하다. Collision이 많아질 수록.. 2021. 9. 29.

티스토리툴바