본문 바로가기

알고리즘46

[백준+프로그래머스] 1978번 소수 찾기 + 프로그래머스 소수 찾기 소수 찾기는 간단한 것 같으면서도 헷갈리는 그러한 문제다. 원리는 간단하다.주어진 수의 개수를 입력받고, 주어진 수를 1~주어진 수 까지 나누어서소수의 성질인 1과 자기자신만 나눠지는 2가지만 체크해서 결과에 ++해준다. 요즘 들어 프로그래머스의 level1 문제를 다시 풀어보고 있다.한번 푼다고 해서 정확하게 아는것이 아니기 때문이다.일반적인 소수찾기 문제는 어렵지 않게 풀 수 있다. 그런데 제출했더니 시간초과가 발생했다.그래서 에라토스테네스의 체를 써야 하나보다 하고 적용하려했더니 잘 기억이 나지 않았다.다시 풀어보길 잘한 것 같다. 에라토스테네스의 체쉽게 말해서 2를 예로 들면 2는 소수 이지만 2의 배수인 4, 6, 8, 10 ~ 은 소수가 아니다.3은 소수이지만 6, 9, 12, 15는 소수가 .. 2018. 12. 10.
[Kakao_Blind_Recruitment 1차] 비밀지도 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다.전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다.암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을.. 2018. 9. 11.
[Kakao_Blind_Recruitment 1차] 다트게임 다트게임카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다. 다트 게임은 총 3번의 기회로 구성된다.각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 (점수1 , 점수2 , 점수3 )으로 계산된다.옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를.. 2018. 9. 10.
[백준] 7576번 토마토 - 기억할 것1. 익은 토마토가 있는 곳 = 행렬의 값이 1인 지점을 시작점으로 해야한다. >> 처음에 행렬 값이 1인 x,y 좌표를 먼저 저장한다.2. 애초에 다 익은 경우 0을 출력, 다 익지 못하는 경우 -1을 출력3. 익은 토마트 = 안익은 토마토 + 14. 현재 있는 위치가 (x,y) 라면 그 다음 갈 수 있는 좌표는 인접해 있는 상,하,좌,우 칸입니다. 즉, 상 : (x-1,y) , 하 : (x+1,y), 좌 : (x,y-1), 우 : (x, y+1) 이므로 이를 4개의 순서쌍으로 생각해서 배열로 만들 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 2018. 8. 21.
[백준] 1260 DFS와 BFS DFS와 BFS를 공부하고 좋은 예제를 찾아보다가 백준 알고리즘을 찾게되었다.DFS는 스택을 이용한 방식으로 현 경로상의 노드만을 기억하면 되기때문에 저장공간의 수요가 적다.목표노드가 깊은 곳에 있는 경우 빨리 구할 수 있다. BFS는 큐를 이용한 방식이다. 현 노드에서 인접한 노드를 모두 들리면서 탐색하는 방식이다. 문제. 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.입력. 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 .. 2018. 8. 20.
백준 10866번 덱(Deque) 1. Deque(덱) 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐 어떻게 사용하느냐에 따라 큐와 스택이 모두 될 수 있음 2. Deque관련 메소드 1. 추가 add, addFirst, addLast, put, putFirst, putLast, offer, offerFirst, offerLast // Deque 마지막에 element삽입, first와 last자리삽입 push : Deque 앞 부분에 element 삽입 2. 삭제 poll : Deque의 제일 앞 element를 return받은 후 element 제거, 큐에서 element받아오기 pop : Deque의 제일 앞 element를 return받은 후 element 제거, 스택에서 element받기 * 큐의 경우 FIFO 이기 .. 2018. 7. 30.

티스토리툴바