Study

2024년 3월 5일 알고리즘 문제풀이 문제 방금그곡 난이도 Lv.2 코드 언제나 카카오 문제는 일단 문제 이해가 힘들다. 1차 62.9/100 점 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(m, musicinfos): # 정답 음악 제목 answer = '' # 정답 음악이 라디오에서 재생된 시간 answer_t = 0 for x in musicinfos: # 시작 시간, 종료 시간, 음악 제목, 악보 start,end,title,content = x.split(",") # 시작 시와 분 start_h, start_m = start.split(":") # 종료 시와 분 end_h, end_m = end.split(":") # 재생된 시간 계산 playtime = 60*(int(end_h)-int(start_h)) + (int(end_m) - int(start_m)) # 악보를 list화 tmp = list(content) # 재생된 시간이 악보보다 길다면, 악보를 반복한다. while len(tmp) < playtime: tmp += list(content) # 가장 처음부터 len(m)글자씩 보기 위한 반복 for i in range(len(tmp)-len(m)): # i번째글자부터 i+m번째 글자까지 합쳐, 길이가 m과 같은 글자를 만든다 k = "".join(tmp[i:i+len(m)]) if k == m: # 만든 글자가 m과 같지만, 맨마지막에 #이 온다면 정답이 아니다. # "ABC" 를 찾았지만 악보상 "ABC#"으로 되어있다면 찾은 것으로 되겠지만 실제론 찾은게 아니기 때문 # 첫번째 조건문은 그 다음이 #인지 확인할 때, 그 다음이 없을 경우를 위한 설정 if i+len(m)+1 < len(tmp) and tmp[i+len(m)] != "#": # 처음으로 찾은 음악이라면 정답으로 설정 if not answer_t: answer = title answer_t = playtime # 이미 찾은 음악이 있다면, 재생된 시간이 더 길 때만 업데이트한다. # 짧다면 업데이트할 필요가 없다. # 같다면 이미 찾은 음악이 더 먼저 재생되었기 때문에 업데이트할 필요가 없다. else: if answer_t < playtime: answer = title return answer 진짜 너무 복잡하다.. 풀면서도 이게 정답일 것 같지는 않다고 느꼈는데 역시나였다. 조건을 단순화해야한다. #이 붙었을 때를 제대로 처리하지 않은게 문제인듯 하다. ...

2024년 3월 4일 알고리즘 문제풀이 문제 점프와 순간 이동 난이도 Lv.2 코드 일반적인 DP문제라고 생각했다. 조금 어려운 편이긴 하지만, 기존에 충분히 풀어봤던 유형이라 금방 풀 수 있었다. 도착지로 이동하는 마지막 방법을 점프라고 고정하고 생각했다. 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 31 def solution(n): # 3칸까지는 고려할 필요 없음 if n <= 3: dp = [0, 1, 1, 2] return dp[n] # 그 이상일 때는 DP # 가장 최대 건전지 사용량은 그곳까지 점프로만 도달했을 때이므로 모든 곳을 최댓값으로 초기화한다. dp = [] for i in range(n + 1): dp.append(i) # 2,3일 때는 알맞게 초기화 dp[2] = 1 dp[3] = 2 # 4 이상일 때부터 DP for i in range(4, n + 1): # 반으로 나누었을 때 몫 k = i // 2 # 홀수여서 딱 절반인 곳이 존재하지 않을 때 if i % 2: # i까지 도달 비용 = 몫까지 도달하는 비용(dp[j]) + 몫부터 i까지 점프하는 비용(i-j) for j in range(k, i): dp[i] = min(dp[i], dp[j] + i - j) # 짝수여서 절반인 곳이 존재할 때 else: # 절반인 곳에서 순간이동하면 도착할 수 있으므로 절반에 도착하는 것과 같은 값 dp[i] = min(dp[i], dp[k]) for j in range(k + 1, i): dp[i] = min(dp[i], dp[j] + i - j) return dp[n] n칸 까지 갈 때, 절반인 n//2를 기준으로 생각하면 된다. 절반도 오지 못했을 떄 점프를 하는 것은 거기서 순간이동 하는 것보다 더 건전지 사용량이 소모될 것이기 때문이다. 예를 들어, 10 칸을 이동한다고 했을 때 ...

2024년 3월 1일 알고리즘 문제풀이 문제 둘만의 암호 난이도 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 def solution(s, skip, index): answer = [] alphabet = list('abcdefghijklmnopqrstuvwxyz') n = len(alphabet) def check(num,x): idx = alphabet.index(x) while num: idx += 1 # 알파벳의 끝에 도달하면 맨 처음으로 보냄 if idx == n: idx = 0 result = alphabet[idx] # skip에 포함되지 않을때만 갯수를 셈 if result not in skip: num -= 1 return result arr = list(s) for i in arr: answer.append(check(index,i)) return ''.join(answer)

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) ...