본문 바로가기

분류 전체보기

 (386)
프로그래머스 - 소수 찾기 (Java) https://school.programmers.co.kr/learn/courses/30/lessons/42839 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 완전탐색 + 소수  판별 문제이다. 이 문제는 17 -> 1, 17, 7, 71 을 알아내면되는 문제이다. 즉 순열을 찾아내는 것이 관건이다. 순열 조합 문제는 완전탐색으로 조금만 N이 커도 쓸 수 없다. 하지만 이 문제는 최대 길이가 9이기 때문에 충분히 순열을 찾아낼 수 있다.  9! / (9 - k)! 아주 작다.  순열은 dfs 백트래킹으로 구현할 수 있다. 1. 방문체크 배열에서 방문하지 않..
백준 2458번 키 순서 (Java) https://www.acmicpc.net/problem/2458 한 노드에서 다른 노드의 대한 정보를 알 수 있는가를 묻는 문제이다. 방법은 두개가 있다. 1. 각 지점에서 모두 dfs해보며 갈 수 있는지 검사한다. 2. 플로이드 워셜을 사용한다.  이 문제의 의도는 2번이기 때문에 2번의 의미를 알아보도록 하자 플로이드 워셜은 다익스트라와 달리 각 모든 노드들의 최단거리를 알아볼 수 있는 알고리즘이다. 예를들어 A 노드에서 B노드로 가는 방법에는 두가지가 있을 것이다.  1. A -> B로 바로 가는 경우2. A -> C - > B 어떤 노드를 경유할 경우 그리고 이 둘 중 작은 값이 최단거리가 된다. dist[i][j] = min (dist[i][j], dist[i][k] + dist[k][j]) ..
백준 13023번 ABCDE (C++) https://www.acmicpc.net/problem/13023  백트래킹을 연습하기에 좋은 문제이다. 백트래킹은 모든 경로를 검색하며 1번 노드를 방문하고 여기가 아니면 돌아가는 식으로 이뤄지는 알고리즘이다. 코딩테스트에도 빈출이니 철저히 연습해놔야한다. 백트래킹은 완전탐색에 자주 사용되고 유연하게 사용할 수 있어야한다.  이 문제는 결국은 어떤 정점에서 시작할 때 시작하여 최대 노드의 개수가 자신을 포함해 5개라면 정답이된다. 가지를 쳐내면 된다. 그런데 사실 이렇게 생각을 처음에는 했지만 이러면 결국 모든 정점에서 백트래킹을 해야하는데... 시간초과가 안날수가 없는데 안나더라...? 대체 왜 안나는 걸까 #include #include using namespace std;vector graph[..
백준 7682번 - 틱택토 (C++) https://www.acmicpc.net/problem/7682 7682번: 틱택토 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 www.acmicpc.net 두가지 풀이법이 있다. 틱택토의 모든 조건을 따져 지금 들어온 틱택토가 유효한지 확인하는 방법과 모든 시뮬레이션을 해보고 들어온 틱택토가 있는지 확인하는 방법이다. 이전의 방법은 많은 블로그에서 소개하고 있기 때문에 난 두번째 방법으로 해보았다. 시간 복잡도는 9^9 로 충분히 가능하다. 그리고 문자열을 방문표시해야하는 짜증이 있었는데 이것을 셋으로 표현했다. 맵으로 표현했을 때 안되는 이유가 ..
알고리즘 - 에라토스테네스의 체(C++) 최근 코딩테스트에서 소수를 판별해야하는 문제가 나왔다. 그래서 에라토스테네스의 체를 사용해야함을 바로 알았지만 아쉽게 떠올리지 못하여 정리해두려고 한다. 원래 소수를 판별하는 방법은 대학교 1학년 C언어 시간에 배울 정도로 쉽다. N까지 모두 나눠보며 나눠 떨어지는 수가 2이면 소수이다. 그러나 이것은 매우 시간이 오래걸린다.  에라토스테네스의 체는 이 수가 소수인지 아닌지 판별하는 것이 아니라 1~100만 등 어떠한 범위내에서 소수인지 아닌지 판별할 때 유용하다. 즉 1~100만 중 소수가 몇개인가? 이러한 것을 해결하는 방법이다. 알고리즘은 다음과 같다. 1.  2 ~ N까지 2의 배수를 false 처리한다. 2. 3 ~ N까지 3의 배수를 false 처리한다.4. 5 ~ N까지 5의 배수를 fals..
Spring 기초 1) WAS란 무엇인가? 동적 페이지는 사용자와 상호작용하며 어떤 버튼을 누르면 이벤트가 작동하는 등으로 작동해야한다. 동적 웹 페이지에서 상호작용을 위해 필요한 것이 WAS이다. WAS 사용자 컴퓨터나 장치에 어플리케이션을 수행해주는 미들웨어이다. 주로 동적 서버 컨텐츠를 수행하는 것으로 웹 서버와 다르며 데이터 베이스 서버와 같이 작동하게 된다. WAS는 Web Server의 기능도 가지고있지만 Web Container와 구분되기 때문에 구조적으로 분리되었다. 위 사진을 보면 WAS는 웹서버와 컨테이너를 모두 포함한다. 덕분에 사용자의 다양한 요구에 맞춰 웹 서비스를 제공할 수 있으며, WAS는 JSP, Servlet 등 구동 환경을 제공해주기 때문에 웹 컨테이너 혹은 서블릿 컨테이너라고도 불린다. Web Service Ar..
백준 - 3687번 성냥개비 (C++) https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 개인적으로 이런 문제를 굉장히 싫어한다. 못풀면 그냥 내 능지문제가 되는 것 같은 문제들.. 하지만 문제를 편식해선 좋은 개발자가 될 수 없다! 무튼, 이 문제는 특이하다. 최대 개수는 그리디로 최소개수는 dp로 구해야한다. 이러한 유형의 문제는 먼저 문제의 조건에 맞도록 수를 나열해보면서 규칙을 찾거나 풀이법을 고민하는 것이 올바른 방법이다. 1개로는 아무것도 만들 수 없으니 스킵한다. 성냥개수 가장 ..
백준 - 4179번 불! (C++) https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문자 www.acmicpc.net 이 문제를 읽고 생각났던 것은 3차원 배열을 선언하여 그 상태 자체를 확인해야한다고 생각했다. 그러나 그러지 않아도 되었다. https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는..

티스토리툴바