본문 바로가기

Algorithm123

Swift) 백준 1085번 (직사각형에서 탈출) 요구능력 : 덧셈, 뺄셈 코드설명 : 문제에서 말하는 경계선은 (x, y)에서 직사각형의 변에 최소한으로 닿을수 있는 거리를 물어본것이다. 그림을 보면 빨간화살표를 말하는 것이다. (0, 0)에서 (x, y) 와 (x, y)에서 (w, h)의 x값과 y값 각각의 거리를 구해주면 된다. 그렇다면, 구해야 할 값은 x, y, (w - x), (h - y) 가 된다. 나는 여기서 arr[2]와 arr[3]에 구해야되는 (w - x), (h - y)를 미리 계산하여 집어넣었다. 그리고 for문을 실행하여 각각 비교하고 가장 작은값을 temp에 저장해줬다. 후기 : 쉬웠다. var arr = readLine()!.split(separator: " ").map{Int($0)!} arr[2] = arr[2] - ar.. 2021. 8. 15.
Swift) 백준 9020번 (골드바흐의 추측) 요구능력 : 에라토스테네스의 체를 응용할수 있느냐 코드설명 : 문제에서 10000보다 작거나 같은 모든 짝수 n이라고 했으므로, 에라토스테네스의 체를 이용해서 10000까지의 소수를 구해준다. 이후에 for문을 이용하여 테스트케이스만큼 골드바흐파티션을 구해줄것이다. 절반의수를 두 번 더하면 하나의 수가 나온다. ex) 4 = 2 + 2, 8 = 4 + 4 이 원리를 이용하면 쉽게 풀리는 문제이다. 8 = 4 + 4니까, 소수끼리 더한게 아니다. 그럼, 여기서 p1에서 1을 빼고 p2에서 1을 더해보면 결국 결과값은 8이 나온다. (혹시나 설명해주면 에라토스테네스의 체를 만들어놨기 때문에 arr[p1]의 값은 p1이다.) if문을 이용해서 arr[p1] + arr[p2]가 구하고자하는 값(scan)과 같으.. 2021. 8. 14.
Swift) 백준 4948번 (베르트랑 공준) 요구능력 : 에라토스테네스의 체를 이해하고 있냐 코드설명 : 문제에서는 0이 입력되면 종료한다고 했으므로 while문을 통해 n이 0일경우 break를 걸었다. 그리고 1의 경우 에라토스테네스의 체로 신경쓸 수 있는 부분이 아닌것 같으므로 따로 처리해줬다. 아래는 에라토스테네스의 체를 이용해서 구해줬다. 배열을 2부터 생성해줘야 2의 배수를 다 없앨 수 있기 때문에 2부터 생성해줬고 마찬가지로 2의배수부터 배수를 쭉 없애줘야 하기 때문에 2의 배수부터 배열을 0을 만들어 줬다고 보면된다. 그리고 범위가 n < ☺️ 2021. 8. 9.
Swift) 백준 1929번 (소수구하기) 요구능력 : 에라토스테네스의 체 알고리즘을 사용할 수 있느냐 코드설명 : 에라토스테네스의 체를 사용했다. M부터 N까지 이지만, 배열은 2부터 생성해주고 배수 지워줄 때도 2부터 지워줬는데 그 이유는 한번 M부터 N으로 실행해서 출력해보면 알 수 있을 것이다. 후기 : 갓빈나님의 동영상을 보고 학습했는데 바로 이해가 되버렸다.( https://www.youtube.com/watch?v=5ypkoEgFdH8&t=498s) 문제풀어 볼 생각도 안하고 바로 에라토스테네스의 체라는 알고리즘을 찾아봤는데, 그 이유는 솔직히 천재가 아닌이상 "무슨알고리즘을 써라" 라는 식의 문제를 혼자서 풀수없다. 수학에서 근의공식을 쓰는거처럼.. 오기가 있으신분들도 억지부리지말고 학습하고 이해한다음 풀어보시길 let getMN .. 2021. 8. 8.