백준 16929번: Two Dots 16929번: Two Dots 각각의 칸은 색이 칠해진 공이 하나씩 있다. 이 게임의 핵심은 같은 색으로 이루어진 사이클을 찾는 것이다. 다음은 위의 게임판에서 만들 수 있는 사이클의 예시이다. 점 k개 d 1 , d 2 , ..., d k 로 이루어진 사이클의 정의는 아래와 같다. 모든 k개의 점은 서로 다르다. k는 4보다 크거나 같다. 모든 점의 색은 같다. 모든 1 ≤ i ≤ k-1에 대해서, d i 와 d i+1 은 인접하다. 또, d k 와 d 1 도 인접해야 한다. 두 점이 인접하다는 것은 각각의 점이 들어있는 칸이 변을 공유한다는 의미이다. 게임... www.acmicpc.net 접근 방법 (핵심 아이디어) DFS로 길이 4 이상의 사이클 여부를 확인한다. 문제를 요약하면, 길이 4 이상의 사이클을 찾는 문제입니다. 시작위치를 가지고 DFS를 돌면서 4개 이상 지나왔고, 자기 자신으로 돌아오면 True를 반환하여줍니다. 한 점에서 갈

빌더 패턴 예제 public class Cat { int size; int age; String name; private Cat(int size, int age, String name) { this.size = size; this.age = age; this.name = name; } public static class Builder { int size = 0; int age = 0; String name = null; public Builder setAge(int age) { this.age = age; return this; } public Builder setName(String name) { this.name = name; return this; } public Builder setSize(int size) { this.size = size; return this; } public Cat build() { return new Cat(size, age, name); } } }

백준 6593번: 상범 빌딩 6593번: 상범 빌딩 문제 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 지나갈 수 없거나, 비어있어서 지나갈 수 있게 되어있다. 당신은 각 칸에서 인접한 6개의 칸(동,서,남,북,상,하)으로 1분의 시간을 들여 이동할 수 있다. 즉, 대각선으로 이동하는 것은 불가능하다. 그리고 상범 빌딩의 바깥면도 모두 금으로 막혀있어 출구를 통해서만 탈출할 수 있다. 당신은 상범 빌딩을 탈출할 수 있을까? 만약 그렇다면 얼마... www.acmicpc.net 접근 방법 (핵심 아이디어) 3차원 탐색(BFS/DFS) 3차원 탐색입니다. 2차원 배열을 탐색할때, 상하좌우 4개의 방향만 인접한 노드로 보고 탐색했다면 높이를 고려한 6개의 방향을 모두 인접한 노드로 보고 탐색해주면 됩니다. 입력받는 배열이 3차원이라는 것만 조심하면

백준 2564번: 경비원 2564번: 경비원 문제 동근이는 무인 경비 회사 경비원으로 항상 대기하고 있다가 호출이 들어오면 경비차를 몰고 그 곳으로 달려가야 한다. 동근이가 담당하고 있는 곳은 직사각형 모양의 블록으로 블록 중간을 가로질러 차가 통과할만한 길이 없다. 이 블록 경계에 무인 경비를 의뢰한 상점들이 있다. 예를 들어 가로의 길이가 10, 세로의 길이가 5인 블록의 경계에 무인 경비를 의뢰한 3개의 상점이 있다고 하자. <그림 1>과 같이 이들은 1, 2, 3으로 표시되어 있고, 동근이는 X로 표시한 위치에 있다. < 그림 1 > 1번 상점에서 호출이 들어 왔을 때... www.acmicpc.net 접근 방법 (핵심 아이디어) 어처피 테두리만 걸어다닐거니까, 테두리만 1자로 펴보자 그냥 구현문제인데, 각 테두리를 아래 그림처럼 1자로 펴주자. 그러면 그냥 좌표값 차이로 바로 거리를 구할수 있음. 왼쪽, 오른쪽 두개 다 가봐야 하니까 (거리차이의 절댓값, 테두리길이 - 거리

백준 2234번: 성곽 2234번: 성곽 문제 대략 위의 그림과 같이 생긴 성곽이 있다. 굵은 선은 벽을 나타내고, 점선은 벽이 없어서 지나다닐 수 있는 통로를 나타낸다. 이러한 형태의 성의 지도를 입력받아서 다음을 계산하는 프로그램을 작성하시오. 이 성에 있는 방의 개수 가장 넓은 방의 넓이 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 위의 예에서는 방은 5개고, 가장 큰 방은 9개의 칸으로 이루어져 있으며, 위의 그림에서 화살표가 가리키는 벽을 제거하면 16인 크기의 방을 얻을 수 있다. 성은 M × N(1 ≤ M, N ≤ 50)개의 정사각형 칸으로 이루어... www.acmicpc.net 접근 방법 (핵심 아이디어) 모든 벽을 부수어보는 Brute Force + 벽으로 둘러쌓여진 방의 크기를 구하는 BFS/DFS. 방의 크기를 구하는 그래프 탐색은 웰-논 설명을 생략한다. 사실 모든 벽을 부수어 보는게 TLE를 의심해서 최적화를 시도해보았는데, 다시 생각해보니 완탐

SSL이 사용하는 암호화 방식 SSL은 성능과 보안상의 이유로 대칭키 암호화 방식과 비대칭키 암호화 방식을 동시에 사용한다. 그러므로 우리는 각 암호화 방식의 작동원리를 알아야만 합니다! 대칭키 암호화 방식 뭐가 대칭이란 것일까? 그것은 바로 암호화 할때 쓰는 키와 복호화 할때 쓰는 키가 대칭이란 것이다 ~~ “I LOVE YOU”를 “0987”이라는 키로 암호화 한 결과가 “oAK1#jp3” 이라고 가정해보자. 암호화된 “oAK1#jp3” 에서 원래 값(평문)을 얻어오기 위해서는 반드시 암호화 할때 사용하였던 “0987” 이라는 키를 알아야만 한다. 암호화, 복호화 할때 비교적 컴퓨터 자원을 적게 잡아먹는다. 그러나 키를 탈취당하면 그대로 평문이 노출되므로, 키 자체를 비밀리에 관리해야 할 필요가 있다. 클라이언트와 서버가 대칭키로 암호화/복호화를 하기 위해서는 키를 주고받는 과정은 필수적인데, 이때가 위험함. 다시 말하자면 암.복호화 속도는 빠르지만, 키를 건네는 과정 자체가 어

백준 2660번: 회장뽑기 2660번: 회장뽑기 2660번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 회장뽑기 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 8177 4405 3488 54.637% 문제 월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다.... www.acmicpc.net 접근 방법 (핵심 아이디어) 다른 모든 사람까지의 거리중 최댓값이 점수입니다. 기본 BFS 문제. DFS로도 가능. 연결된 모든 정점들을 탐색하면서 원래 정점과의 거리를 저장하여 둡니다. 거리 중 최댓값이 문제에서 말하는, "회장뽑기"에 사용될 점수입니다. 전체 코드 fro

백준 2661번: 좋은수열 2661번: 좋은수열 2661번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 좋은수열 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 12075 5889 4515 49.845% 문제 숫자 1, 2, 3으로만 이루어지는 수열이 있다. 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다. 다음은 나쁜 수열의 예이다. 33 3 2121 323 123123 213 다음은 좋은 수열의 예이다. 2 32 32123 1232123 길이가 N인 ... www.acmicpc.net 접근 방법 (핵심 아이디어) 백트래킹. 조건을 만족하는 순간 모든 재귀를 탈출하도록 구현해야됨. 어렵지 않은 백트래킹입니다. [1, 2, 3] 순서로 탐색한다면 가장 먼저 N자리가 만들어졌을때가 가장 작은 좋은수열입니다. 문제에서 가장 작은 좋은수열을 출력하라고 했으므로 더

먼저 HTTP를 알아보자 Hypertext Transfer Protocol의 약자. 주로 HTML을 전송하기 위한 통신규약 데이터 통신할때 따로 암호화를 하지 않음. 로그인을 하려고 서버로 비밀번호를 전송할때, 비밀번호가 암호화되지 않고 그대로 네트워크 망을 거쳐서 서버로 전송되는데, 굉장히 위험함. 그래도 등장한 것이 HTTPS. 그래서 HTTPS가 무엇이냐면 HTTP over SSL, HTTP Secure 등으로 불린다! HTTP에 데이터 암호화가 추가된 프로토콜이다. 기존 HTTP에 비해 안전함. HTTP가 TCP/UDP 등의 프로토콜을 사용한다면 HTTPS는 추가로 SSL/TLS의 프로토콜을 사용하여 보안성을 높인 것이다! SSL과 TLS. 네스케이프에서 SSL을 개발했고, 표준화 기구인 IETF에서 관리하기로 하면서 TLS로 이름이 바뀐것 뿐. TLS 1.0은 SSL 3.0을 계승한다.

백준 1303번: 전쟁 - 전투 1303번: 전쟁 - 전투 1303번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 질문 게시판 전쟁 - 전투 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 2 초 128 MB 10954 4254 3395 37.967% 문제 전쟁은 어느덧 전면전이 시작되었다. 결국 전투는 난전이 되었고, 우리 병사와 적국 병사가 섞여 싸우게 되었다. 그러나 당신의 병사들은 흰색 옷을 입고, 적국의 병사들은 파란색 옷을 입었기 때문에 서로가 적인지 아군인지는 구분할 수 있다. 문제는 같은 팀의 병사들은 모이면 모일수록 강해진다는 사실이다. N명이 뭉쳐있을 때는 N 2... www.acmicpc.net 접근 방법 (핵심 아이디어) DFS, BFS 중 아무거나 사용해서 인접한 칸의 개수를 세면 된다. 오랜만에 쉬운 문제. 어떤 방법을 사용해서든, 인접한 칸의 개수를 세주면 됩니다. 이번 문제에서는 dfs로 푸는게 코드가 깔끔한 느낌이 강해서 사용해보았습니당. 전체

백준 23289번: 온풍기 안녕! 23289번: 온풍기 안녕! 유난히 추운 날씨가 예상되는 이번 겨울을 대비하기 위해 구사과는 온풍기를 설치하려고 한다. 온풍기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사과는 뛰어난 코딩 실력을 이용해 각 칸 (r, c)의 온도를 실시간으로 모니터링하는 시스템을 개발했다. (r, c)는 r행 c열을 의미한다. 구사과의 성능 테스트는 다음과 같은 작업이 순차적으로 이루어지며, 가장 처음에 모든 칸의 온도는 0이다. 문제의 그림에서 빈 칸은 온도가 0인 칸을 의미한다. 집에 있는 모든 온풍기에서 ... www.acmicpc.net 접근 방법 (핵심 아이디어) 플레5 구현. 온풍기에서 바람이 나오는 로직이 젤 어렵지롱 오랜만에 만나는 빡구현 문제입니다. 파이썬 아니였으면 엄두도 안났을 문제 ㅋㅋ. 크게 다섯 스텝으로 문제가 나눠지는데, 온풍기에서 바람이 나오는 로직이랑 온도가 조절되는 로

CORS 작동방식 1. 예비요청 ( preflight request ) 브라우저의 요청이 특정 조건을 만족하지 않는다면, 대부분의 경우 예비 요청을 먼저 보낸다.! 먼저 브라우저는 OPTION 메소드로 자신의 출처와 본 요청에 사용할 메소드와 헤더를 서버로 보낸다. 서버는 이 예비요청에 대한 응답으로 허용되는 Origin 목록, 허용되는 메소드와 헤더 목록, 해당 예비 요청이 브라우저에 남아있을수 있는 시간 등을 보낸다. 브라우저는 이 응답을 보고, 본 요청을 보내도 된다고 판단하면 그때 본 요청을 보낸다. 브라우저의 예비요청 OPTIONS Origin : http://front-server.com Access-Control-Request-Method : GET Access-Control-Request-Header : Content-Type 예비요청에 대한 서버의 응답 Access-Control-Allow-Origin : * Access-Control-Allow-Methods : G

CORS 그런데 다른 출처에도 자원을 요청할 일이 생겼다면??? 그래서 등장한 것이 CORS(Cross Origin Resource Sharing) 원래대로라면 SOP에 의해 다른 출처로 요청을 보내는 것이 막혔어야 하지만, 요청을 보낼수 있도록 풀어주는 정책이 CORS이다. 다시 말해, CORS 조항을 지킨 요청에 대한 응답은 예외적으로 브라우저가 막지 않고 허용한다는 의미 브라우저의 CORS 기본 동작 원리를 살펴보자 클라이언트에서 HTTP 요청의 헤더에 자신의 Origin을 담아서 전달 HTTP 프로토콜을 사용해서 요청을 보낼때, 요청의 헤더에 Origin이라는 필드에 자신의 출처를 함께 담아서 보냄 서버는 요청에 대한 응답을 할때 헤더에 Access-Control-Allow-Origin을 담아 클라이언트에 전달함 이 헤더에는 “이 리소스에 접근하는 것이 허용된 출처”가 담겨있음 클라이언트에서는 자신의 보냈던 Origin과 응답의 헤더인 Access-Control-Allow-O

파이썬에서 psutil 라이브러리로 사용중인 메모리의 양을 알수 있다. psutil 라이브러리를 사용하면 현재 실행중인 프로세스의 정보를 얻어올수 있는데, 여기서 memory_info를 부르면 메모리 정보를 알수 있다. 여러 메모리 정보중에 rss(resident set size), 즉 실제 할당된 물리 메모리 양을 얻을수 있다. 단위는 byte임. KB 로 변환하려면 2^10 으로 나눠주면 됨 MB 로 변환하려면 2^20 으로 나눠주면 됨 추가 ) 0으로 초기화된 10000 * 10000 배열을 선언하면 약 800MB 정도의 메모리가 할당됨. 파이썬으로 알고리즘 문제 풀때, MLE를 피하기 위해 참고하면 좋을듯. import psutil N = 10000 M = 10000 arr = [[0] * M for _ in range(N)] memory = psutil.Process().memory_info().rss / 2 ** 20 print(f'{N}*{M} arr, use memor

백준 17435번: 합성함수와 쿼리 17435번: 합성함수와 쿼리 17435번 제출 맞힌 사람 숏코딩 재채점 결과 채점 현황 강의 질문 게시판 합성함수와 쿼리 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 512 MB 4143 2258 1471 52.479% 문제 함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 f n : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f 1 (x) = f(x) f n+1 (x) = f(f n (x)) 예를 들어 f 4 (1) = f(f(f(f(1))))이다. n과 x가 주어질 때 f ... www.acmicpc.net 접근 방법 (핵심 아이디어) sparase matrix (희소 행렬)을 사용하여 f^n(x)를 logN에 구할수 있다. 희소행렬 기본문제. 일단, 이 문제를 막 풀면 어떻게 되는지부터 설명하겠음. N이 50만, Q가 20만임. 각각의 쿼리마다 f^n(x)를

TCP 혼잡제어 혼잡(체증) 망에 입력되는 트래픽 양이 망이 처리할수 있는 한도를 초과할 경우 체증이 발생한다. input 되는 패킷량보다 output되는 패킷량이 현저히 적은 상황임. 혹은 입력된 패킷량이 응답되는데에 delay시간이 늘어나는 상황. 패킷망에서는 트래픽의 흐름이 일정하지 않음. 혼잡제어는 혼잡을 완화하기 위한 수단이지, 근본적인 해결은 망의 처리용량 자체를 늘려야됨 흐름제어와의 차이점 흐름제어는 송신측 전송속도와 수신측 처리속도의 차이가 주 원인임. 하지만 혼잡제어는 그 원인이 이루 말할수 없이 복잡하다. 네트워크 전체 망에서 원인을 찾아야 하기 때문. 어느 한 라우터에서 흐름이 원활하지 않다던가 등. 어떻게 혼잡(체증)을 제어할수 있을까? 예방적 혼잡제어 사전에 망에 입력되는 트래픽 양을 조절한다. 망 사업자와 사용자 사이에 계약을 통해 사전에 전송할 데이터의 양을 정한다. (call admission control) 망 사업자는 사용자가 사전에 약속된 트래픽 양

백준 2250번: 트리의 높이와 너비 2250번: 트리의 높이와 너비 문제 이진트리를 다음의 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 그리려고 한다. 이때 다음의 규칙에 따라 그리려고 한다. 이진트리에서 같은 레벨(level)에 있는 노드는 같은 행에 위치한다. 한 열에는 한 노드만 존재한다. 임의의 노드의 왼쪽 부트리(left subtree)에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree)에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다. 이... www.acmicpc.net 접근 방법 (핵심 아이디어) 노드의 "너비"는 중위순회되는 순서와 같습니다. 노드의 너비에 할당된 값을 천천히 살펴보다 보면 중위순회에서 탐색되는 순서과 같다는 사실을 발견할수 있게 됩니다. cur_width를 1부터 시작하여 중위순회 될때마다 1씩 늘

출처 : 유튜브 이산수학

출처 : 유튜브 이산수학