Study

2024년 2월 29일 알고리즘 문제풀이 문제 하샤드 수 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(x): answer = True arr = list(map(int, str(x))) tmp = sum(arr) if x % tmp != 0: answer = False return answer 반복문보단 map 함수를 이용하려고 했다.

2024년 2월 27일 알고리즘 문제풀이 문제 프렌즈4블록 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 def solution(m, n, board): answer = 0 # 시계방향으로 90도 회전하는 함수 # 따라서 n x m 인 배열이 된다. # 블록의 추락도 아래가 아닌 왼쪽으로 발생해야 한다. arr = [[] for _ in range(n)] for k in range(n): for i in range(m-1,-1,-1): arr[k].append(board[i][k]) # 점을 기준으로 오른쪽, 아래, 오른쪽 아래가 모두 동일한지 확인하는 함수 def check(a,b): result = False tmp = arr[a][b] if arr[a+1][b] == tmp and arr[a][b+1] == tmp and arr[a+1][b+1] == tmp: result = True return result # 점을 기준으로 오른쪽, 아래, 오른쪽 아래 4개를 지우는 함수. # 지워지는 블록이 다른 곳과 겹칠 경우를 대비하여, 실제 지워진 갯수를 계산하여 반환 def delete(a,b): result = 0 if arr[a][b] != '0': arr[a][b] = '0' result += 1 if arr[a+1][b] != '0': arr[a+1][b] = '0' result += 1 if arr[a][b+1] != '0': arr[a][b+1] = '0' result += 1 if arr[a+1][b+1] != '0': arr[a+1][b+1] = '0' result += 1 return result # 90도 회전하였기 때문에, 왼쪽으로 블록이 떨어지는 함수 구현 # 각 행마다, 비어있는 열을 발견할 경우 오른쪽을 탐색하여 떨어질 블록을 찾아 바꿔준다. # 한 칸씩 떨어뜨리면, 여러 블록을 떨어뜨리는 경우가 복잡해진다. def fall(): for i in range(n): for j in range(m): if arr[i][j] == '0': for k in range(j+1,m): if arr[i][k] != '0': arr[i][j] = arr[i][k] arr[i][k] = '0' break # '0'이 아니라는 조건을 추가하지 않으면 무한루프가 실행된다. while True: delete_list = [] for i in range(n-1): # 여기가 1,m 이면 테스트 5가 실패함 for j in range(m-1): if arr[i][j] != '0' and check(i,j): delete_list.append([i,j]) if not delete_list: break for a,b in delete_list: tmp = delete(a,b) answer += tmp fall() return answer 겁나 힘들게 풀었다… 기존에는 위와 같이 풀되, 90도로 회전하지 않았다. 이떄 발생하는 어려움은 블록을 부수고 떨어뜨리는 것을 구현하기 힘들었다. 위에서 아래로 떨어뜨릴 경우 같은 열이지만 다른 행인 원소들간의 비교가 이루어져야 한다. 위 각주에서도 말했지만 한 칸씩 옮길 경우 2개가 같이 떨어질 떄나, 여러 칸을 떨어뜨리는 경우의 수는 상당히 복잡하기 때문에 구현이 힘들었다. 추락을 같은 List 안에서 발생하도록 하면 훨씬 편해질 것이라고 생각해서 배열을 90도 회전하였다. ...

2024년 2월 26일 알고리즘 문제풀이 문제 크레인 인형뽑기 게임 난이도 Lv.1 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 def solution(board, moves): n = len(board) stk = [] answer = 0 # 열에서 가장 위에 있는 인형을 찾는 함수 # 찾으면 board에서 0으로 바꾸고 반환 def first_target(row): for i in range(n): if board[i][row]: result = board[i][row] board[i][row] = 0 break else: result = False return result # 인형이 있을 때, 이미 들어있는 인형과 동일하면 2개 제거, 아니면 추가 for x in moves: row = x-1 tmp = first_target(row) if tmp: if stk: if stk[-1] == tmp: stk.pop() answer += 2 continue stk.append(tmp) return answer

2024년 2월 23일 알고리즘 문제풀이 문제 짝지어 제거하기 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 def solution(s): arr = list(s) stk = [] for i in range(len(s)): if not stk: stk.append(arr[i]) continue else: if stk[-1] == arr[i]: stk.pop() else: stk.append(arr[i]) if not stk: answer = 1 else: answer = 0 return answer

2024년 2월 22일 알고리즘 문제풀이 문제 정수 내림차순으로 배치하기 난이도 Lv.1 코드 1 2 3 4 5 6 7 def solution(n): arr = list(str(n)) map(int,arr) arr.sort(reverse=True) map(str,arr) answer = ''.join(arr) return int(answer)

2.3 인터넷 전자메일 인터넷 메일 시스템의 상위 요소에는 다음 3가지가 있다. 사용자 에이전트(user agent) 사용자의 메시지 읽기, 전달, 저장, 구성을 담당 ex) 지메일, 마이크로소프트 아웃룩, 스파트몬용 지메일 앱 메일 서버(mail server) 각 수신자는 메일 서버 안에 **메일박스(mailbox)**를 갖고 있다. 메일박스는 수신한 메시지를 유지하고 관리한다. 송신자의 사용자 에이전트 → 송신자의 메일 서버 → 송신자의 메일 서버의 메시지 큐 → 수신자의 메일서버 → 수신자의 메일 서버 내 메일박스 수신자의 서버 고장으로 전달할 수 없으면 메시지를 **메시지 큐(message queue)**에 보관하고 나중에 전달을 재시도한다. SMTP(Simple Mail Transfer Protocol) 인터넷 전자메일을 위한 주요 애플리케이션 계층 프로토콜 TCP의 신뢰적인 데이터 전송 서비스를 이용 송신자의 메일 서버에서 수행하는 클라이언트와 수신자 메일 서버에서 수행되는 서버를 갖고 있음. 메일 서버가 송신할 때 : SMTP의 클라이언트로 동작 메일 서버가 수신할 때 : SMTP의 서버로 동작 2.3.1 SMTP A가 B에게 메일을 보내는 과정 A는 네이버의 전자메일 사용자 에이전트에게 B의 전자메일 주소(B@gmail.com)를 제공하고 메시지를 작성하여 메시지를 보내라고 명령한다. A의 사용자 에이전트(네이버)는 메시지를 A의 메일 서버에게 보내고 그 메시지는 서버에서 메시지 큐에 들어간다. A의 메일 서버에서 동작하는 SMTP의 클라이언트 측은 메시지 큐에서 메시지를 확인한다. 이후 B의 메일 서버에서 수행되는 SMTP 서버에게 TCP 연결을 설정한다. 이때 포트는 25. 초기 SMTP 핸드셰이킹 이후에 SMTP 클라이언트는 A의 메시지를 TCP 연결로 보낸다. B의 메일 서버 호스트에서 SMTP의 서버 측은 메시지를 수신한다. 이 메시지는 B의 메일 서버의 메일박스에 저장된다. B은 사용자 에이전트를 이용해 그 메시지를 읽는다. A와 B의 메일 서버가 물리적으로 거리가 멀더라도, 중간 메일 서버는 사용하지 않는다. 따라서 B의 서버가 죽어 있으면 전달하지 못한다. 이 떄, A 서버의 메시지 큐에 두고 지속적으로 재발송한다. 일정시간이 지나면, 폐기하고 A에게 발송이 실패했음을 알린다. 두 서버의 TCP 연결이 설정되면, SMTP의 서버와 클라이언트는 애플리케이션 계층 핸드셰이킹을 수행한다. 핸드셰이킹에서 서로에 대한 정보를 알게 되는 것처럼, 이때 클라이언트는 서버에게 두 사람(송신자와 수신자)의 전자메일 주소를 제공한다. 2.3.2 메일 메시지 포맷 우편을 보낼때, 편지 봉투에는 여러 정보가 담기게 된다(발신자, 수신자 등) 전자 메일에서는 메시지 몸체 앞에 있는 헤더에 담긴다. 2.3.3 메일 접속 프로토콜 메일 서버가 개인의 로컬호스트에 있다면, 항상 메일을 받기 위해 서버가 켜져있어야 한다. 따라서, 일반 사용자는 로컬 호스트에서 사용자 에이전트를 수행하고 늘 켜져 있는 공유 메일 서버에 저장된 메일박스에 접근한다. 즉, 메일 서버는 보통 사용자들과 공유한다. 송신자의 사용자 에이전트는 메일 서버를 통해 수신자의 메일 서버로 메시지를 전송한다. 왜 송신자의 사용자 에이전트가 직접 수신자의 메일 서버로 메시지를 전송하지 않을까? 송신자의 사용자 에이전트는 수신자의 메일 서버에 도달할 수 없기 때문 이유는 보안 문제, SMTP의 규약, 스팸 방지, 신뢰성 보장 등 다양하다. 수신자의 사용자 에이전트는 받은 메시지를 보기 위해 SMTP를 사용할 수 없다. SMTP는 push지만 메시지는 pull 해야 하기 때문 메시지를 받는 방법 HTTP를 통해 요청 인터넷 메일 접근 프로토콜(Internet Mail Access Protocol, IMAP) 사용 이 둘 모두 메일 서버에 의해 유지되는 폴더를 관리하게 된다.

2.2.3 HTTP 메시지 포맷 HTTP 요청 메시지 ex) 1 2 3 4 5 GET /somedir/page.html HTTP1.1 Host: www.abc.com Connection: close User-agent: Mozilla/5.0 Accept-language: fr 메시지가 일반 아스키 텍스트로 쓰여있어 우리가 읽을 수 있다. 메시지는 5줄로 되어있고 각 줄은 CR(carriage return, \r)과 LF(line feed, \n)로 구별된다. CR : \r, 맨 앞으로 이동하라는 뜻 LF: \n, 새로운 라인 첫 줄을 **요청 라인(request line)**이라고 부른다. 3개의 필드로 구성 : method(GET), URL(/somedir/page.html), HTTP 버전(HTTP1.1) 이후의 줄들은 **헤더 라인(header line)**이라고 부른다. 요청하는 객체가 존재하는 호스트(Host) 명시 TCP 연결에서 이미 알게 되었지만, 웹 프록시 캐시에서 필요함 비지속 연결 명시(Connection) 요청을 보내는 브라우저 타입(User-agent) 객체의 언어 버전(Accept-language) : 서버에 있다면 프랑스어로 보낼 것 헤더라인 이후에 개체 몸체(entity body)가 있음. POST 방식에서만 존재하는, 클라이언트가 채워 넣는 곳 GET요청에서는 body 대신 URL 끝에 parameter로 추가됨(https://url.com?…) HEAD 방식 HTTP 메시지로 응답하고, 요청 객체를 보내지 않음 개발자의 디버깅에 많이 사용 PUT, DELETE, … HTTP 응답 메시지 ex) ...

AWS 이 글은 누군가 AWS를 다룰 때 조금이나마 덜 고생하길 바라는 마음으로 작성하며, 부정확한 정보에 대한 지적, 정정을 환영하고 자신이 아는 바가 있다면 얼마든지 추가해주길 바랍니다. 앞으로 지속적으로 추가할 예정입니다. What is AWS? 아마존 웹 서비스(AWS, Amazon Web Service)는 아마존닷컴의 클라우드 컴퓨팅 사업부이다. 아마존 웹 서비스는 다른 웹 사이트나 클라이언트측 응용 프로그램에 대해 온라인 서비스를 제공하고 있다. Region 아마존은 클라우드 컴퓨팅을 제공하기 때문에, 데이터센터를 곳곳에 보유하고 있다. 주 고객층을 생각해 물리적으로 가까운 리전을 선택한다. ...

2.2 웹과 HTTP(1) 2.2.1 HTTP 개요 웹의 애플리케이션 계층 프로토콜인 **HTTP(HyperText Transfer Protocol)**는 웹의 중심이다. **웹 페이지(Web page, 문서)**는 객체(object)들로 구성된다. **객체(object)**는 단순히 단일 URL로 지정할 수 있는 하나의 파일(HTML 파일, JPEG 이미지, 자바스크립트, CCS 스타일 시트 파일, 비디오 클립 등)이다. 대부분의 웹 페이지는 기본 HTML 파일과 여러 참조 객체로 구성된다. 각 URL은 2개의 요소를 갖고 있다. 객체를 갖고 있는 서버의 호스트 이름 객체의 경로 이름 **웹 브라우저(Web browser)**는 HTTP의 클라이언트 측을 구현하기 떄문에 웹의 관점에서 클라이언트와 브라우저는 혼용된다. HTTP는 TCP를 전송 프로토콜로 사용한다. 과정 HTTP 클라이언트가 먼저 서버에 TCP 연결을 시작 브라우저와 서버 프로세스는 각자의 소켓 인터페이스를 통해 TCP로 접속. 소켓 인터페이스는 각 프로세스와 TCP 연결 사이에서의 출입구다. 서버와 클라이언트는 메시지를 소켓 인터페이스에게 보낸다. 이후 부터는 TCP의 몫이다. HTTP는 **비상태 프로토콜(stateless protocol)**이다. 클라이언트에 대한 정보를 유지하지 않기 떄문이다. 2.2.2 비지속 연결과 지속 연결 클라이언트-서버 상호작용이 TCP상에서 발생할 때, 각 요구/응답 쌍이 분리된 TCP 연결을 통해 보내지면 비지속 연결(non-persistent connection) 모든 요구와 해당하는 응답들이 같은 TCP 연결상으로 보내지면 지속 연결(persistent connection) HTTP/1.0가 디폴트 모드로 지속 연결을 사용하지만 HTTP 클라이언트와 서버는 비지속연결을 사용하도록 설정될 수 있다. 비지속 연결 HTTP 클라이언트가 서버에게 URL을 통해 html 파일을 요청한다고 가정해보자. HTML 파일은 여러 개의 참조 객체 이미지를 가진다. HTTP 클라이언트는 HTTP 기본 포트 번호 80을 통해 서버로 TCP 연결을 시도한다. 그 결과 클라이언트와 서버는 각각 소켓을 가진다. 클라이언트가 자신의 소켓을 통해 HTTP 요청 메시지를 보낸다. 이 요청에는 필요한 html의 경로 이름을 포함한다. 서버는 소켓으로 요청 메시지를 받고 필요한 html 객체를 추출한다. 응답 메시지에 객체를 캡슐화하고 소켓을 통해 클라이언트로 보낸다. HTTP 서버는 TCP에게 TCP 연결을 끊으라고 한다(하지만 실제로는 클라이언트가 응답을 올바로 받을 때까지 끊지 않는다). 클라이언트가 응답 메시지를 받으면 TCP 연결이 중단된다. 필요한 참조 객체(이미지) 10개를 가져오기 위해 각각의 객체에 대한 TCP 연결이 시작된다(1~4 반복). 비지속 연결에선 총 11개의 TCP 연결이 발생한다. 순차적으로 하지 않고 동시 연결(동시에 11개의 연결을 구성하여 각각 처리)로 응답 시간을 줄일 수 있다. 세 방향 핸드셰이크(three-way handshake) SYN(Synchronize) : 클라이언트가 서버에 연결을 요청하는 메시지를 보냄 SYN-ACK(Synchronize-Acknowledment) : 서버가 클라이언트의 연결 요청을 수락하고, 클라이언테에게 확인 응답을 보냄 ACK(Acknowledgment) : 클라이언트가 서버의 확인 응답을 받고, 다시 서버에 확인 메시지를 보내 연결을 완료한다. RTT(round-trip time) : 패킷이 클라이언트로부터 서버까지 가고, 다시 클라이언트로 돌아오는 데 걸리는 시간 세 방향 핸드셰이크 중 2단계가 완료될때 까지의 시간이 RTT다. ACK는 2단계가 완료된 후 요청 메시지를 보낼 때 같이 보낸다. 서버에 요청을 보낼 떄는 (TCP 연결 + 요청)이 필요하다. 따라서 서버의 응답시간은 (2RTT + 파일 전송 시간)이다. 지속 연결 HTTP 비지속 연결의 단점 각 요청 객체에 대한 새로운 연결이 설정되고 유지되어야 함. 이를 위해 필요한 TCP 버퍼는 서버에게 부담이 될 수 있음. 응답시간 (2 RTT) 지속 연결은 하나의 지속 TCP 연결로 여러 웹페이지와 관련 객체를 통신할 수 있다. 파이프라이닝(pipelining) : 각 객체에 대한 요구는 진행 중인 요구에 대한 응답을 기다리지 않고 연속해서 만들어질 수 있음. HTTP 서버는 타임아웃 기간동안 사용되지 않으면 연결을 닫기 떄문에, HTTP 디폴트 모드는 파이프라이닝을 이용해 지속 연결한다.

2024년 1월 30일 알고리즘 문제풀이 문제 뉴스 클러스터링 난이도 Lv.2 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 def solution(str1, str2): def check(x): if x[0].islower() and x[1].islower(): return True else: return False str1 = list(str1) str2 = list(str2) arr1 = [] arr2 = [] for i in range(len(str1) - 1): if str1[i].isupper(): str1[i] = str1[i].lower() if str1[i + 1].isupper(): str1[i + 1] = str1[i + 1].lower() if check(str1[i] + str1[i + 1]): arr1.append(str1[i] + str1[i + 1]) for i in range(len(str2) - 1): if str2[i].isupper(): str2[i] = str2[i].lower() if str2[i + 1].isupper(): str2[i + 1] = str2[i + 1].lower() if check(str2[i] + str2[i + 1]): arr2.append(str2[i] + str2[i + 1]) arr_all = arr1 + arr2 arr_set = set(arr_all) n_max = 0 n_min = 0 for i in arr_set: n_max += max(arr1.count(i), arr2.count(i)) if i in arr1 and i in arr2: n_min += min(arr1.count(i), arr2.count(i)) if str1 == str2: answer = 65536 elif not n_max and not n_min: answer = -1 else: answer = int((n_min / n_max) * 65536) return answer 우선 문자열을 배열로 만들었다. 이후 각 원소가 대문자라면 소문자로 만들어주었다. 대문자, 소문자 구별이 없기 때문에 비교를 수월하게 하기 위함이다. 리스트의 두 원소를 붙여서 check 함수를 통해 둘다 소문자로 이루어진 알파벳인지 확인한다. 앞서서 대문자를 모두 소문자로 바꿔서 대문자일 가능성은 없다. 굳이 두개를 나눠야 하는 이유는, “%a” 에게 islower() 메서드를 사용하면 a가 소문자라 True를 반환하기 떄문이다. 앞에 %는 무관하다. 물론 “%” 처럼 알파벳이 없다면 False를 반환하다. 따라서 둘 다 알파벳으로 이루어졌는지 확인하기 위해 check() 함수에서는 둘을 나눴다. 이후 합집합의 갯수와 교집합의 갯수를 확인하기 위해 알파벳 2개가 원소인 리스트를 합쳐 set로 만들었다. 중복된 원소를 제거하여 교집합과 합집합 계산에 경우의 수를 낮추기 위해서다. 둘 다 공집합이면 -1을 반환해야하는데, 합집합 교집합이 0일 떄로 확인했다. 다만 예시 3번처럼, “%a!” 와 “%A!” 는 실제로 2개씩 잘랐을 때 모두 알파벳 2개로 이루어지지 않아(%a, a!) 집합이 없게 표시되지만 자카드 유사도는 1이다. 알파벳의 대문자 소문자 여부를 따지지 않기 때문에 완전히 동일한 두 문자열이기 떄문이다. 이럴 때를 확인하기위해 소문자로 바꾸고 리스트화 한 이후 둘이 같다면 자카드 유사도가 1이라 66536을 곱하여 나눈 정수부분을 그대로 출력하도록 했다.