본문 바로가기

분류 전체보기

 (336)
백준 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'로 표시되어 있는..
백준 17835번 - 면접보는 승범이네 (C++) https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 처음보는 유형의 다익스트라였다. 파티 문제처럼 역방향을 받아 다른 노드까지의 거리를 구하는 문제는 접한적이 있었기 때문에 핵심 아이디어는 캐치할 수 있었으나, K의 범위가 결국 N까지 올라올 수 있기 때문에 K번 다익스트라 처리를 하면 시간초과를 받을 수 밖에 없다. 여기서 처음 본 테크닉은 처음 다익스트라를 시작할 때 하나의 지점만 넣고 시..
Java 기초 체력 기르기 자바 문자열 모두 대/소문자 만들기 = Str = Str.toUpperCase() Str = Str.toLowerCase() 문자열 -> 정수 String str = "120"; int tmp = Integer.parseInt(str); 정수 -> 문자열 int tmp = 120; String str = Integer.toString(tmp) ArrayList 삽입 : add ArrayList 삽입 add(3, 'a') 3번째에 a삽입 Collections.reverse -> 반전 Collections.sort(Array) -> 오름차순 Collections.sort(Array, Collections.reverse()) -> 내림차순 Collections.sort(Array, comp) -> 사용자 설정

티스토리툴바