본문 바로가기

분류 전체보기

 (336)
백준 3015번 - 오아시스 재결합(C++) https://www.acmicpc.net/problem/3015 Greedy 문제처럼 생겨서 그리디로 접근하려 했지만 N의 개수를 확인했을 때 반복문 안에서 다시 반복문이 실행되는 순간 시간 초과가 발생할 것임을 직감했다. 그래서 결국 문제 분류를 보니 stack 을 확인했다.들어오는 숫자에 따라 스택을 사용해 f(x)를 구성하면 N번의 Stack Push로 O(N) 에 문제를 해결할 수 있다. 문제는 3가지 경우로 나눌 수 있다.  이번에 들어온 사람의 키가 직전 사람보다 ~1. 작은 경우2. 같은 경우3. 큰 경우 1번 직전 사람보다 작은 경우를 생각해보자.  543 2  현재 stack.top() = 3 이며 3은 자기 직전 4, 이후 2와 마주볼 수 있다. 2번 같은 경우를 생각해보자. 543 ..
Servlet - HttpServlet 사용법 (Request , Response) Servlet : 동적 웹 페이지를 만들 때 사용되는 Java 프로그래밍 기술. 서블릿은 웹 요청과 응답의 흐름을 간단한 메소드 호출로 가능하게 해준다. 만약 서블릿이 없다면 개발자들은 HTTP 스펙을 모두 알고있어야하고 순수 HTTP 상태나 response, request를 파싱하고 해석해야할 것이다. 서블릿이 이것을 대신해준다. 1. Request 클라이언트가 서버에 요청을 보낼 때가 있다. 가장 일반적으론 GET요청 등이 있을 것이다.1. 이 때 쿼리파라미터를 통해 유저아이디나 이름을 보낼수가 있고2. HTML 폼을 통해 POST로 요청한다. 웹 브라우저가 만들어서 보내는데 쿼리 파라미터로 넘어가는 것과 같다.3. POST를 통해 바디에 담아서 간다. 보통 json으로 날아온다. 2. Respons..
백준 1010번 - 다리놓기 (C++) https://www.acmicpc.net/problem/1010 지능과 센스가 있으면 쉽게 풀 수 있는 문제. 그러나 난 둘다 없다 ㅎ.  다이나믹 프로그래밍 태그에서 들어간 문제이기 때문에 DP임은 알고 있었다. 이 문제에서 DP를 사용하는 방식은 두가지 가 있는데, 하나는 순수 DP, 하나는 조합론을 사용하는 방법이다. 1. 조합론 이 문제는 2 -> 4 문제로 보이지만, 우측에서 좌측으로 보낸다고 생각하면 언제나 꼬이지 않고 선을 연결할 수 있는 방법이 있다. 그러므로 문제는 갑자기 M combination N 을 구하는 문제로 바뀌어버린다. 그대로 주어진 조합을 구해도 괜찮지만 알다시피 조합은 엄청난 시간복잡도를 자랑하기 때문에 사용하기 어렵다. 이 문제에선 가능하지만 말이다. 그렇다면 조합의 ..
백준 1700번 - 멀티탭 스케줄링 https://www.acmicpc.net/problem/1700 골드1 치곤 조금 쉽다고 느낀 문제이다.처음엔 DP를 생각했다. 하지만 알고리즘 분류를 보니 그리디였다. DP로 점화식이나 규칙을 찾아볼 때 이전의 값을 사용하는 낌세가 보이지 않고, 상태를 계속 변경하면서 체크해야하면 그것은 DP가 아님을 인지하고 빠져나와야하는데 실력이 너무너무너무 부족하다. 하,, 그리디로 넘어와서 멀티탭에 꽂아져있거나, 자리가 있으면 괜찮지만 자리가 없으면 무엇을 뽑아야할지 정해야한다. 여기서 난 처음에 2, 4, 5 가 꽂혀있다고 할 때 남은 스케줄 중 2의 개수, 4의 개수, 5의 개수 중 가장 개수가 적은 것을 뽑는 알고리즘을 작성했다. 합리적으로 보이나 반례가 있었다.  만약  3 2 3 4 4 4 5 5 5..
백준 17472번 - 다리 만들기 2 (C++) https://www.acmicpc.net/problem/17472 삼성 A형 기출 문제로 좋은 문제다. 이전에 삼성 대학생 역량 어쩌구를 할 때도 이런 종류의 문제가 많았다. bfs, dfs 후 경로를 사용해 다익스트라를 사용한다는 문제가 있었다. 하지만 이 문제는 mst를 하는 문제이다. 1. bfs or dfs를 통해 각 섬의 번호를 매긴다. (그래프 탐색)2. 그리고 다시한 번 bfs를 통해 각 섬끼리의 최소 거리를 구해 그래프를 구성한다. (bfs, 구현 능력)3. 구성한 그래프를 통해 MST를 진행한다. (MST 프림 or 크루스칼) 그래프의 크기가 크지 않아서 시간을 생각하는 것 보다 코드를 어떻게 해야 간단하고 완벽하게 구성할 수 있을까 고민하는 것이 관건이이며, BFS, MST 같은 기본..
Dynamic Programming - Top Down, Bottom Up 다이나믹 프로그래밍은 메모이제이션을 사용해 이전에 사용한 값을 그대로 읽어 사용함으로서 극적으로 줄일 수 있다. 여기서 메모이제이션의 개념을 보면 마치 캐시 와 비슷해보인다. 그래서 혹자는 캐시질이라고도 한다. Top - Down큰 숫자에서 작은 숫자까지 내려가면서 솔루션을 구하는 방법이다.  rec(N){ dp[N] = min(rec(N - 1), rec(N - 2))}Bottom - Up작은 숫자부터 시작하며 다음 숫자에서 이전의 값을 사용하는 정석적인 dp 방식이다. 주로 점화식을 찾아서 적용시킬 때 사용된다.for(int i = 2; i
백준 17143번 - 낚시왕(C++) https://www.acmicpc.net/problem/17143 구현문제로 엄청난 사고력을 요하는 문제는 아니지만 시간 복잡도 때문에 수학적인 테크닉이 필요한 문제이다. 아무래도 구현문제이기 때문에 사람마다 풀이가 매우 다를 것이다. 하지만 기본적인 아이디어는 비슷할 것이다. 1. 낚시왕이 물고기를 낚는다.2. 상어가 이동한다.  그러므로 난 우선 처음 상어를 입력받을 때 사냥가능한 상어를 먼저 사냥하고 인덱스 1부터 솔루션을 시작했다. 그리고 상어의 정보를 담고 있는 벡터를 선언했는데, 상어가 사냥되거나 다른 상어에 의해 먹혔다고 해서 벡터에서 없애버리는 것은 구현이 어렵고 시간도 더 걸린다. 그래서 life 변수로 살았는지 죽었는지 체크해주었다. 또한 상어들을 이동하고서 같은 곳에 모두 쌓아놓고 ..
프로그래머스 - 오픈 채팅방(C++) https://school.programmers.co.kr/learn/courses/30/lessons/42888 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 카카오 2019년 기출문제로 코딩테스트에서 자주 출제되는 맵을 적절히 사용해야하는 문제이다. Insert가 들어오면 맵에 만약 유저 아이디가 존재하면 갱신하고 없으면 추가한다.체인지가 들어오면 맵 유저 아이디 key에서 닉네임을 교체한다. 그리고 insert와 leave가 들어오면 순서 벡터에 유저 아이디와 나가고 들어감을 표시해둔다.그리고 이후 순서 벡터대로 결과를 출력하면 된다. 그렇게 어렵진 않..

티스토리툴바