본문 바로가기

전체 글

BaekJoon 1076 저항 2019. 1. 21. Link https://www.acmicpc.net/problem/1076 소스결과 2004 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 저항에 있는 색 3개를 가지고 현재 저항의 값이 몇인지 출력 하는 문제 현실의 저항에서 오차 범위를 제외한 문제 역시 수학보다는 문자열 처리가 조금 더 알맞지 않을까 하는 문제이다. 색의 첫번째 두번째는 두자리 수의 각각 10의 자리 1의 자리를 의미하고 세번째 자리는 10의 거듭제곱 값을 의미한다. 문자열 처리는 각각 전부 비교해주는 함수를 사용해도 되지만 이번에는 각각 자리를 기준으로 겹치지 않는 경우로 만든 nested-if문을 사용했다. 출력을 int 값을 사용하면 21억이 넘는 경우가 존재 하기 때문에 overflow가 발생한다. ..
BaekJoon 1652 누울 자리를 찾아라 2019. 1. 21. Link https://www.acmicpc.net/problem/1652 소스결과 1992 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학 설명 영식이가 누울 수 있는 자리의 갯수를 가로와 세로로 구분해서 출력해주자. 입력은 문자열로 주어진다. 문자 사이에 공백이 없다. 한번에 받아야 한다. 수학탭에 있지만 왜 수학문제인지 조금 궁금하다. 문자열 처리에 좀 더 가깝지 않을까 하는 의문이 들기도 한다. 가로와 세로로 구분해서 문자 X가 나오기 전까지 . 의 개수를 세서 개수가 2 이상이면 가로/세로의 수를 1 늘려주면 된다. x가 나오기 전에 끝나는 경우가 존재 하기 때문에 다음 줄로 넘어가기전에 개수를 한번 더 처리해 주어야 한다. 알고리즘 1. 방의 정보를 받아온다. 2. 가로 /..
BaekJoon 5567 결혼식 2019. 1. 21. Link https://www.acmicpc.net/problem/5567 소스결과 2112 KB / 4 ms 출처 baekjoon, JOI 2010 언어 C++ 17 분류 그래프 이론 설명 상근이가 결혼식에 학교 동기 중 자신의 친구와, 친구의 친구를 초대할 때 상근이가 초대할 친구의 수를 구하는 문제이다. 동기의 수가 최대 500명이기 때문에 인접리스트를 써도 무방하다. 또한 a - b가 친구이면 b - a도 친구라는 점에서 양방향 그래프로 추가 하면 된다. 상근이를 기준으로 깊이가 2 이하인 친구들의 수를 출력하면 된다. 동기의 수만큼 배열을 만들어 깊이를 저장하는 방법도 있고 깊이가 2까지 진행 하게 DFS를 진행하는 방법도 있다. 아래 소스코드는 두 방법이 아닌 큐를 이용해서 친구를 구한 후 친..
BackJoon 1978 소수 찾기 2019. 1. 21. Link https://www.acmicpc.net/problem/1978 소스결과 1984 KB / 0 ms 출처 Baekjoon 언어 C++ 17 분류 수학, 에라토스테네스의 체 설명 100개 이하의 주어진 수 중 소수인 수의 개수를 구하는 문제 분류에 적혀있는 에라토스테네스의 체를 연습하기 위한 문제이다. 2 이상의 수 에 대하여 소수인 수의 곱 값은 소수가 아니다 라는 정의를 이용한다. 대표적인 소수 2를 기준으로 4, 6, 8, 은 2의 곱이므로 소수가 될 수 없다. 현재 탐색하는 수가 과거의 수들을 기준으로 곱으로 판정이 되지 않았다면 해당 수는 소수로 판별 할 수있다. 위키 백과 - 에라토스테네스의 체 : https://ko.wikipedia.org/wiki/에라토스테네스의_체 알고리즘 1...
Baekjoon 1405 미친 로봇 2019. 1. 21. Link https://www.acmicpc.net/problem/1405 소스 결과 1988 KB / 40 ms 출처 Baekjoon 언어 C++ 17 분류 DFS, 브루트 포스, 탐색 설명 통제할 수 없는 미친 로봇이 n번의 행동 중 로봇의 이동 경로가 단순한 경우의 확률을 구해 내는 문제 앞선 문제의 경우와 다른 점은 확률을 구해야 한다는 점이 가장 눈에 띈다. 이동 경로를 구해야 되는 문제이기 때문에 BFS/DFS를 사용 해야 한다. 하지만 이번 문제는 최단 경로를 구하는 문제가 아니기에 BFS를 사용하는것은 적절하지 않아보인다. 또한 로봇이 이동 할 수 있는 모든 경로에 대해서 탐색 해야한다. DFS를 진행 하면서 브루트 포스가 자동으로 진행 되기 때문에 크게 유의하지는 않아도 된다. 맵의 크기..
BaekJoon 2661 좋은수열 2019. 1. 21. Link https://www.acmicpc.net/problem/2661 소스결과 1988 KB / 0 ms 출처 Baekjoon, KOI 1997 언어 C++ 17 분류 수학, 백트래킹 설명 1, 2, 3으로 이루어진 수열 중 인접한 두개의 부분 수열이 동일한 하지 않은 최솟값 수열을 출력하는 문제이다. 첫 자리를 제외하고 나머지 자리는 2번씩 검색해야하는 느낌이 드는 문제이다. 시간 제한이 1초인 점이 의심스럽다. 하지만 위 문제는 간단히 생각하면 앞자리가 1인 경우가 항상 최소가 되는 수열이다. 수열을 검사하는 부분을 최대한 간략화 시키기만 한다면 쉽게 문제가 풀린다. 알고리즘 1. 수를 입력받는다. 2. 현재 위치의 문자 값을 1 ~ 3 사이로 설정한다. 2 - 1. 0번 인덱스를 제외한 나머지..
BaekJoon 1600 말이 되고픈 원숭이 2019. 1. 19. Link https://www.acmicpc.net/problem/1600 소스결과 4328 KB / 112 ms 출처 Baekjoon 언어 C++17 분류 BFS 설명 말이 되기위한 원숭이가 자신의 능력과 말을 흉내내는 능력을 섞어 쓰면서 시작지점에서 목표 지점까지 최대한 빠르게 가는 방법을 알아내는 문제다. 움직일 수 있는 경우의수는 총 12가지로 현재 위치에서 인접한 위치로 움직이는 경우와 체스의 나이트처럼 움직이는 방법이다. 이 문제의 특징은 나이트처럼 움직일 수 있는 횟수가 정해져 있다는 것과 조건부에 한해서 같은 위치를 중복해서 방문할 수 있다. 말의 움직임을 흉내내서 가는 경우와 걸어서 가는 경우를 구분 해야 하기 때문에 말의 흉내를 내는 경우의 최대 값인 30번인 경우를 포함해 최대 크기인..
BaekJoon 9019 DSLR 2019. 1. 19. Link https://www.acmicpc.net/problem/9019 소스결과 2128 KB 4712 ms 출처 Baekjoon, ACM-ICPC 언어 C++ 17 분류 BFS 설명 네 개의 명령어가 있는 계산기를 사용해 시작값이 목표값 까지 가는 최단 과정을 요구하는 문제 4가지의 연산 경로 (D S L R)가 존재하고, 현재 결과를 저장 해야하며 최소한의 명령어를 생성 해야 한다. Brute Force로 얼핏 가능해 보이지만 질문 게시판을 찾아보니 결론은 힘들다는 내용으로 보인다. 처음 이 문제를 풀었을 때 중복으로 추가하는 부분을 처리 안해줬더니 시간초과가 바로 나왔다. 중복으로 추가하는 부분을 처리해 주니 문제 요구 시간내로 들어왔다. BFS를 매번 구현하다보니 BFS를 구현하는 내용은 크게..

티스토리툴바