전체 글
BOJ 1012 - 유기농 배추
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 � www.acmicpc.net DFS 를 이용해서 구분된 구역의 총 갯수를 구하는 문제였다. 이 문제를 풀면서 깨달았던 것은 1. 테스트 케이스가 여러개 주어지면 memset 으로 배열 초기화 작업을 해줘야 다음 테스트 케이스에서도 사용이 가능하다. 2. 인접 행렬에 대한 구분 구역의 갯수는 메인 함수에서 구하며, 구역 내에서의 찾고자하는 원소의 총합은 dfs 함수 내에서 구해야한다. 2번에 대한 부분은 BOJ 2667 문제를 풀면 이..
BOJ 1764 - 듣보잡
https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. �� www.acmicpc.net 이 문제를 풀면서 배웠던 두가지가 있는데 첫째는, c++ STL vector 를 사용할때, 초기에 size 를 설정하지 않고 push_back 을 하면 2^n 만큼의 메모리 크기를 잡는다는것. 그래서 resize 를 통해서 미리 크기를 잡아주면 연산 속도도 줄이고, 메모리 크기도 줄일수 있다는 점을 알게 되었다. 둘째는, 코드 작성의 편리성 측면에 근거하여, algorithm header ..
BOJ 3085 - 사탕 게임
https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고 www.acmicpc.net 이 문제는 주의할것이 한가지 있는데, DFS 같은 방식으로 푸는 문제가 아니다. 브루트포스 방식으로 풀어야 하는데, 1. 양옆으로 자리를 바꿨을 때, 2. 위아래로 자리를 바꿨을 때 이 두가지 경우를 고려하면서 코드를 작성해야 한다. 또한 사탕의 갯수를 고려할때, 가로로 계산했을때 최대 몇개인지 세로로 계산했을때 최대 몇개인지를 따져야한다 다만 주의 할 것은 행,열을 빙고처럼 완성하는..
BOJ 1157 - 단어 공부
https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 처음 이 문제를 풀었을 때는, algorithm 헤더의 count 함수를 이용해서 문자열에 포함된 각 문자들의 갯수를 카운팅하려 했다. 그러나 한가지 간과한것이 있었는데, algorithm 헤더의 count() 함수에 대한 시간 복잡도가 O(N) 이기 때문에 입력 받은 문자열 기준 한바퀴를 도는 포문 O(N) 과 겹쳐서, O(N^2) 의 시간 복잡도를 갖는 코드가 되었고, 계속 시간초과가 발생하였다 그래서 다음과 같이 수정해서 코..
BOJ 2231 - 분해합
https://www.acmicpc.net/problem/2231 2231번: 분해합 문제 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+ www.acmicpc.net 브루트포스 를 이용해서 푸는 문제로, 조건만 잘 맞추면 어렵지 않게 풀 수 있는 문제다 나 같은 경우엔 1 부터 백만까지의 수(i) 를 돌려서 그 수(i) + 그 수의 각 자리수의 합 (i 의 자리수 합) 을 구한다음 그 값이 입력받은값 N 과 동일하면 값을 출력하고, 전체 다 돌았음에도 값을 찾지 못하는 경우 0 이 출력되도록 해주면 풀렸다. - c++ #include ..
Load Balancing 이란
* 정의 Load Balancing 이란 다수의 서버가 있을 때, 요청 서비스별 트래픽을 어떻게 분산할지에 대한 아키텍쳐다. Load Balancing 을 사용하지 않은 web infrastructure 구조는 아래와 같이 나타낼 수 있다. 위와 같은 구조는 단일 서버만 운영하기 때문에, 서버에 오류가 생길경우, 유저는 해당 도메인에 접속하지 못하게 된다. 웹 서비스의 경우 위 처럼 한명 들어오고 단일 서버랑 연결하고 이런 단순한 1:1 구조가 아닌 경우가 대부분이다. 예를들면, 수강신청 같은 것 처럼 한번에 많은 인원이 동시에 접속하는 경우, 서버가 트래픽을 감당하지 못할 수가 있고, 사용자 입장에서도 체감상 로딩 시간이 상당히 오래 걸림을 느끼게 된다. * 해결책 이런 문제를 해결하기 위해서는 1. ..
Cookie, Session, Token 이란?
매번 헷갈리던 이 세개의 개념을 정리하려고 포스팅을 작성했다. * 쿠키 (Cookie) HTTP 는 본래 정보를 유지하지 않는다. (stateless) 클라이언트와 서버 사이에 뭔가 통신이 필요하면 필요한 그 순간 마다 매번 요청을 하고 그에 대한 응답을 하는 구조로 되어 있다. 한번 클라이언트와 서버가 서로 연결이 이뤄지고 요청 응답이 완료되었으면 연결이 끊기는데 (connectionless) HTTP 자체가 인터넷 상에서 불특정 다수와 연결되는 통신 환경을 만들기위해 설계되었기 때문이다. 서버가 다수의 클라이언트와 연결이 끊기지 않고 계속 연결되어 있으면, 연결 유지를 위한 Resource 가 너무 많이 필요하게 되어, 서버 관리 측면에 있어서는 단점으로 작용하기 때문이다. 그러나, 웹 기술이 발달하..
BOJ 2042 - 구간 합 구하기
https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄�� www.acmicpc.net 세그먼트 트리를 이용한 문제. 세그먼트 트리는 배열 같이 연속적인 데이터가 주어졌을 때, 일부 구간 마다의 합을 구해서 트리로 표현하는 자료구조다. http://arkainoh.blogspot.com/2018/06/segment.tree.html [Algorithm] 세그먼트 트리 (Segment Tree) 세그먼트 트리(Segment..