오늘 할일
- 스프링 개발 실습
- 알고리즘 문제풀이
- 저녁 프로젝트 모임
오늘 한 것 & 배운 내용
알고리즘 문제 풀이
큐
-
문제 해석
- 큐를 구현하고 push, pop, size, empty, front, back 명령어를 수행할 수 있도록 한다
-
풀이 계획
- 지난번 큐와 비슷하게 따로 메소드를 만들어 switch case로 명령어에 따라 동작을 수행하도록 한다
- 배열의 크기는 최대값으로 고정한다
- 지난번 큐와 비슷하게 따로 메소드를 만들어 switch case로 명령어에 따라 동작을 수행하도록 한다
-
- arr와 front , back을 static 배열과 변수로 선언하여 queue 메소드르 따로만들어 명령을 처리해주었다
- front == back일 때 queue가 비어있다는 성질을 이용해 명령들을 처리할 수 있었다
- 지난번에 문제의 요구조건들을 꼼꼼히 확인하지 않아 여러번 틀린것을 반성해서 문제를 꼼꼼히 여러번읽으며 요구조건들을 만족시켜나갔따
- 그럼에도 불구하고 -1을 출력하는 곳에 1을 출력해서 한번 틀려서 아쉽다
- 테스트의 숫자가 정해져있기 때문에 배열의 크기를 정해서 풀었지만 없었다면 pop을 할 때 새로운 배열을 선언해서 옮기는게 좋을지 아니면 배열을 계속 크기를 키워나가야될지 고민이 됬다
- 잠깐 검색해보니 이게 선형구조의 큐가가진 단점이고 그래서 이런 단점을 보완한 원형큐를 구현한다는 것을 알 수 있었다
- 참고 : https://plainote.tistory.com/52?category=888980
-
다른사람풀이
- ArrayList를 이용하면 pop할때 항상 remove(0)만 해주면 쉽게 구현할 수 도 있는 것 같다
수 찾기
-
문제 해석
- 기준이 되는 숫자의 그룹이 N개 제시하고 다시 M개의 정수를 제시하여 각각의 정수가 N개의 정수에 포함되어있는지 확인한다
- 포함되어있다면 1을 출력하고 포함되어있지 않다면 0을 출력한다
- 기준이 되는 숫자의 그룹이 N개 제시하고 다시 M개의 정수를 제시하여 각각의 정수가 N개의 정수에 포함되어있는지 확인한다
-
풀이 계획
- N개의 정수를 카운터 정렬을 이용하여 정렬한뒤 M개의 정수를 입력받아 해당 index가 true라면 1을 출력하고 아니라면 0을 출력하도록 풀면 될 것 같다
- 다시보니 정수의 범위가 int의 범위와 같은데 그러면 카운터 정렬에 사용할 배열에 범위가 너무 커져서 사용하기가 어려울 것 같다
- n의 값과 m의 값을 비교하는 방법을 사용하되 몇가지 장치를 넣어 최대한 연산을 줄여주는 방식으로 풀어봐야될 것 같다
- 먼저 n을 입력받은 배열을 정렬하여 최소값과 최대값을 뽑아서 m의 정수가 그범위 안에 있는지 없는지 확인하여 연산 줄여준다
- n의 중간 index를 기준으로 값이 더 큰지 아니면 작은지 비교하여 비교하는 index에 연산을 줄여준다
- N개의 정수를 카운터 정렬을 이용하여 정렬한뒤 M개의 정수를 입력받아 해당 index가 true라면 1을 출력하고 아니라면 0을 출력하도록 풀면 될 것 같다
-
- n을 입력받아 배열을 만들어 정렬하고 m을 하나씩 입력받아 배열에 있는지 비교하는 방식으로 풀었다
- m이 n의 최소값과 최대값의 범위에 m이 있는지 확인하여 범위밖이라면 0을 출력하도록 하였다
- m의 값보다 n의 값이 크다면 더이상 검색을 하지 않고 0을 출력하도록 하였다
- 통과하긴 했는데 다른풀이에 비해 수행시간이 너무오래걸려서 개선할 방법을 찾아봐야될 것 같다
- n을 입력받아 배열을 만들어 정렬하고 m을 하나씩 입력받아 배열에 있는지 비교하는 방식으로 풀었다
-
다른 사람 풀이
- 이분 탐색법을 활용하여 탐색의 범위를 줄여가는 방식으로 풀 수 있엇다
- 참고 : https://code0xff.tistory.com/32
- 오름차순으로 배열을 정렬하고 배열의 중앙 index mid를 기준으로 값을 탐색해나가는 방법이다
- 배열에 첫 인덱스를 fist, 마지막 인덱스를 last로 둔다
- fitst <= last 를 조건으로 반복문을 만들고 (first+last) /2 로 가운데 인덱스 mid를 찾는다
- 찾는값과 mid인덱스의 값을 비교한다
- 같으면 true를 리턴하고 반복문을 종료한
- n < arr[mid] 이면 last = mid -1을 해서 범위를 mid의 왼쪽으로 줄여준다
- 반대로 n > arr[mid] 이면 범위를 first = mid +1을 해서 범위를 mid로 줄여준다
- 반복문에 조건안에서 탐색을 반복하다 찾는 값이 없으면 false를 리턴한다
- 이분 탐색법을 활용하여 탐색의 범위를 줄여가는 방식으로 풀 수 있엇다
-
나의풀이2 - 이분탐색 적용
- 한번만 반으로 나눈게 아닌 계속 미드 index를 활용해 반으로 줄인걸 반으로 줄여가면서 탐색하는 방식으로 넓은 범위의 수를 탐색할때 유리할 것 같다
터렛
-
문제 해석
- 좌표 x1, x2과 x2,y2가 입력되고 점 1과 점3까지의 기리인 r1과 점2와 점3의 거리임 r2가 주어질때 점3이 될수 있는 좌표의 위치의 개수를 구하라
- 위치의 개수가 무한대이면 -1을 출력한다
- 좌표 x1, x2과 x2,y2가 입력되고 점 1과 점3까지의 기리인 r1과 점2와 점3의 거리임 r2가 주어질때 점3이 될수 있는 좌표의 위치의 개수를 구하라
-
풀이 계획
-
두점사이의 거리의 공식을 이용하여 2개의 식을 만들고 해당 식을 모두 만족하는 x, y의 값을 찾아내기로 하였다
- x와 y의 범위는 다른 좌표의 범위와 마찬가지로 -10,000보다 크거나 같고 10,000보다 작거나 같은 정수로 본다
-
-
풀이실패
-
위와같이 구하니 연산하는데 너무 오래걸려서 접근방법이 잘못된 것임을 알게되었다..
-
1시간이상 풀이법을 고민해보았는데 풀지 못해서 다른사람풀이를 통해서 배우고 다음에 다시 풀기로 하였다
-
-
다른사람풀이
- 참고 : https://st-lab.tistory.com/90
- 주어진 두점을 A와 B라고 했을 때 점 A를 중심으로하고 r1을 반지름으로하는 원1과 점B를 중심으로하고 r2를 반지름으로 하는 원2의 접점의 갯수를 구하는 문제로 해석하였다
- 위와 같이 봤을때 2원이 가질 수 있는 접점은 3가지 종류이다
- 접접이 개수가 무할할때(= 두원의 중심이 같고, 반지름도 같을 때)
- x1= x2, y1=y2, y1=r2를 모두 만족할때 접접의 갯수는 무한대가 된다
- 접접이 없을 때(두 원이 서로 만나지 못할때)
- 두점 사이의 거리가 각 원의 반지름의 합보다 클때 (두 원이 서로 떨어져있을때)
- 한 원안에 다른원이 있으면서 접접이 없을 때
- 점 A와 점 B의 거리보다 반지름의 길이가 더 작다면 두원은 만날 수 없다
- 접점이 한개일 때
- 내접할 때
- 점 A와 점B의 거리와 반지름사이의 거리가 같으면 내접하게된다
- 외접할 때
- 두점사이의 거리가 두 반지름의 합과 같으면 외접한다
- 내접할 때
- 이외에 상황은 접접이 2개인 상황이된다
- 접접이 개수가 무할할때(= 두원의 중심이 같고, 반지름도 같을 때)
- 풀이시 double을 사용하면 연산에 오류가 있을 수 있으니 모두 int형을 이용해 제곱된 형태로 구하는게 바람직하다
내일 할일
- 스프링 개발 실습
- 알고리즘 문제풀이
- 프로젝트 준비
배우는 개발 일기