티스토리

Vapor

검색하기

블로그 홈

Vapor

vapor3965.tistory.com/m

공유가 생명입니다. 같이 발전합시다!💪🏻

구독자: 9

방명록 방문하기

주요 글 목록

프로그래머스 - 위클리 챌린지 7주차 - 입실 퇴실 - swift https://programmers.co.kr/learn/courses/30/lessons/86048 코딩테스트 연습 - 7주차 사회적 거리두기를 위해 회의실에 출입할 때 명부에 이름을 적어야 합니다. 입실과 퇴실이 동시에 이뤄지는 경우는 없으며, 입실 시각과 퇴실 시각은 따로 기록하지 않습니다. 오늘 회의실에는 programmers.co.kr 문제 유형은 구현문제 일수도 있고, 나는 스택으로 풀어냈다. 구현문제로 접근하려고 논리를 세워봤지만 코드로 작성할 수 있는 깔끔한 논리가 떠오르지 않았다. 예를들어, 확실하게 만난 사람은, 다음과 같을 수 있겠다 1. 자신이 들어온다음에 들어온 사람들 중에서, 자신이 나가기전에 있는 사람들에 속한다면 반드시 만났겠다. 2. 자신이 들어오기 전에 사람들 중에서, 자.. 공감수 0 댓글수 0 2021. 9. 15.
백준 - 하노이 탑 이동 순서 - 11729 - swift https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제는 재귀 유형이다. 우선 풀이에 앞서 정말 감격스럽다. 코딩테스트 공부한지 1년만에 도움없이 혼자서 이해하고 풀었다. 그전까지 매번 하노이탑 볼 때 마다 이걸 어떻게 푸는건지 감도 오지 않았다. 심지어 예전에 풀이를 봤을때도 이해가 안갔었다. 하지만,... 1시간동안 고민 끝에 풀었다!ㅠㅠ 처음에는 완전탐색으로 접근했다가, 계속 이동하는 걸 그려보면서 다음과 같은 패턴을 찾을 수 .. 공감수 1 댓글수 0 2021. 9. 3.
백준 - 도도의 음식 준비 - 22953 - swift https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net 문제는 완전탐색과 이분탐색으로 볼 수 있다. 완전탐색에는 순열과 조합을 이용했다. 크게 문제는 최적의 시간을 찾는 것으로, 각 요리사들에는 요리 시간이 정해져있고, K개의 음식을 모두 준비하는데 걸리는 가장 빠른 시간을 찾는 문제다. 이러한 유형은 미리 최적의 시간이 X라고 정하고서 탐색하는 방법, 즉 이.. 공감수 0 댓글수 0 2021. 9. 1.
백준 - 빌런 호석 - 22251 - swift https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 문제 유형은 구현, 완전탐색 또는 비트마스킹이 될 수 있다. 하나의 문제에서 다양한 접근법이 가능하므로 정말 좋은 문제인 것 같다. 어떻게 이런 문제를 만드는지 정말 대단하다. 내 기준에서는 조금 난이도가 있었다 내 접근법 우선 처음 접근법( 구현 + 완전탐색 ) 은 다음과 같았다. 하나의 디스플레이에 0부터 9까지 숫자를 표현할 수 있고, 각 숫자마다 필요한 LED가 다르다. 또, 각 디스플레이마다 LED는 최대 7개이다. 호석이는 1부터 최대 P개까지 LED를 반전시킬 수 있다... 공감수 0 댓글수 0 2021. 8. 27.
백준 - 정보 상인 호석 - 22252 - swift https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 유형은 우선순위 큐 이용 문제다. swift에서는 우선순위 큐가 없기 때문에, 이진 힙으로 이용하여 따로 구현해야 한다. 몇 번 작성하다 보면은 저절로 외워진다. 우선순위 큐가 필요한 이유는, 쿼리가 다 주어진 다음에 계산을 시작하는 것이 아닌, 각 쿼리마다 그때그때 계산을 해야 한다. 한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라도 그 정보를 파기한다. 어느 시점.. 공감수 0 댓글수 0 2021. 8. 26.
백준 - 숨바꼭질 4 - 13913 - swift https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제는 너비 우선 탐색 - bfs 유형이다. X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 총 3가지의 움직임이 있는데, 3가지 모두 다 1초 후에 발생한다. 문제는 가장 빠르게 동생을 찾을 수 있는 시간을 묻고 있다. 모두 1초이므로, 간단하게 bfs를 통해서 풀 수 있다. .. 공감수 1 댓글수 0 2021. 8. 26.
백준 - 늑대와 양 - 16956 - swift https://www.acmicpc.net/problem/16956 16956번: 늑대와 양 크기가 R×C인 목장이 있고, 목장은 1×1 크기의 칸으로 나누어져 있다. 각각의 칸에는 비어있거나, 양 또는 늑대가 있다. 양은 이동하지 않고 위치를 지키고 있고, 늑대는 인접한 칸을 자유롭게 www.acmicpc.net 실버 4의 낮은 난이도지만, 재밌는 문제였다. 문제 유형은 구현에 가깝다. 또는 bfs로도 풀 수 있긴 하다. 즉 bfs를 몰라도 풀 수 있는 문제다. 사실 나도 문제를 보자마자 bfs가 딱 떠올랐다. 대체로 bfs나 dfs가 들어가면 최소 실버1~2의 난이도를 갖는데, 의아했다. 왜 실버 4일까? 처음에는 늑대를 기준으로 bfs를 돌리면서 양을 만나는...이런 생각을 하다가, 양을 기준으로 .. 공감수 0 댓글수 0 2021. 8. 25.
백준 - 두 로봇 - 15971 - swift https://www.acmicpc.net/problem/15971 15971번: 두 로봇 입력에서 두 번째 줄에 주어지는 방번호는 1과 2, 세 번째 줄에 주어지는 방 번호는 2와 3, …, i번째 줄에 주어지는 방 번호는 i-1과 i, …, N번째 줄에 주어지는 방 번호는 N-1과 N이다 (아래 입력과 www.acmicpc.net bfs 또는 dfs , 그래프탐색 유형이다. 굉장히 좋은 문제라고 생각한다. 그래프탐색의 골드5의 난이도는 그렇게 어렵지 않지만, 핵심을 파악하는게 꽤 걸렸다. ( 사실 그마저도 다른 분의 코드를 참고해서 깨달았다. ) 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방.. 공감수 0 댓글수 0 2021. 8. 25.
백준 - 회의준비 - 2610 - swift https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 유형은 bfs탐색 또는 플로이드 워셜로 볼 수 있다. 문제를 푸는 데 있어서 핵심 로직은 다음과 같다. 1. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 한다. 2. 효율적인 회의 진행을 위해 위원회의 수는 최대가 되어야 한다. 사실 1번을 만족한다면 2번은 자동적으로 만족할 수밖에 없다. 즉 2번은 그다지 고려하지 않아도 되는 부분이다. 그러므로, 위원회를 만들어주기 위한 그룹핑이 필요.. 공감수 0 댓글수 0 2021. 8. 24.
백준 - 쇠막대기 - 10799 - swift https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제는 스택 유형이다. 나름 재밌는 문제 였다. 특정 문제들은 특정 알고리즘을 쓰면 풀 수 있는 그런 뻔한 문제들이 있는데, 그런 문제 말고 이렇게 직접 문제 해결 과정을 오롯이 찾아가는 문제가 재밌다. 처음 봤을때는 이걸 어떻게 접근해야하는지, 감이 안왔다. 레이저기준으로 양옆을 확인해야하는지... 등등 시도 해봤지만 다 영 아니였다. 그러다가, 스택으로, 앞에서부터 순차적으로 확인하는걸로 생각해봤다. 만.. 공감수 0 댓글수 0 2021. 8. 24.
백준 - 구슬 탈출 1, 2, 4, 13459, 13460, 15653 - swift https://www.acmicpc.net/problem/13459 13459번: 구슬 탈출 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 조금 난이도 있는 구현, bfs 문제라고 생각한다. 구현에 있어서 고려할 요소가 몇 개 있다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지이다. 즉, 좌, 우, 위, 아래 움직일 때 한 칸만 움직이는 것이 아닌 끝까지 움직이도록 해야 한다. 그리고 더 이상 움직이지 않을 때는, 벽에 부딪히거나, 또는 다른 구슬에 부딪힌 경우다... 공감수 0 댓글수 0 2021. 8. 23.
프로그래머스 - 위클리 챌린지 4주차 - 직업군 추천하기 - swift https://programmers.co.kr/learn/courses/30/lessons/84325 코딩테스트 연습 - 4주차 개발자가 사용하는 언어와 언어 선호도를 입력하면 그에 맞는 직업군을 추천해주는 알고리즘을 개발하려고 합니다. 아래 표는 5개 직업군 별로 많이 사용하는 5개 언어에 직업군 언어 점수를 부 programmers.co.kr 난이도가 낮은 구현 문제라고 할 수 있다. 주어진 조건대로 구현하면 문제 없다. 개발자가 사용하는 언어의 언어 선호도 x 직업군 언어 점수 의 총합이 가장 높은 직업군을 return 하도록 solution 함수를 완성해주세요. 총합이 같은 직업군이 여러 개일 경우, 이름이 사전 순으로 가장 빠른 직업군을 return 해주세요. 문제는 총 5개의 직업군이 존재하므.. 공감수 0 댓글수 0 2021. 8. 23.
백준 - 주간 달력 - 22936 - swift https://www.acmicpc.net/problem/22936 22936번: 주간 달력 주간 달력(주력)은 일요일부터 토요일까지 총 7일간의 일정이 들어있는 달력이다. 작년 수현이는 일 년 짜리 달력에 코팅 용지를 붙여 사용했는데, 올해는 조금 더 똑똑해져서 주력에 테이프를 www.acmicpc.net 완전 탐색 및 누적합 문제 유형 같다. ( 알고리즘 유형에는 구간합이 없었지만, 내가 난이도 기여해서 누적합을 추가했다 ) 나름 재밌었던 문제다! 문제의 지문이 조금 애매한 것 같은데.. ( 그래도 풀 수 있었으니 ) 우선 핵심 지문들이 있다. 주력 하나에 들어갈 수 있는 일정의 개수는 제한이 없고, N개의 주력은 서로 연속되어야 한다. 주력의 맨 처음 날짜는 1 이상이어야 하고, 요일은 신경 쓰지 .. 공감수 0 댓글수 0 2021. 8. 22.
백준 - 쿠키크루 - 22939 - swift https://www.acmicpc.net/problem/22939 22939번: 쿠키크루 밀가루반죽으로 잘 구워진 킴쿠키는 광활하고 평평한 들판 위에 세워진 쿠키나라의 시민이다. 킴쿠키는 케이크나라의 침략으로 어려워진 쿠키나라를 지키기 위해 할 수 있는 일이 없을까 늘 고 www.acmicpc.net 완전탐색 및 구현 문제라고 볼 수 있다. 처음에 가장 가까운 토핑들만 탐색하는 bfs로 접근했는데 틀렸다. 사실 그 방법으로도 의문점이 있었다. 반례가 존재할 것 같았다. 집 - [토핑 1, 2, 3] - 도착지점 이렇게 bfs로 탐색한다고 해서 최소거리가 보장 된다는 점이 없다는 것이다. 그래서 이 점을 해결하기 위해 순열로 각 토핑들의 방문위치를 정해주는 것이다. 총 3개의 토핑들이 있으므로, 총 6개.. 공감수 0 댓글수 0 2021. 8. 22.
LeetCode - 98. Validate Binary Search Tree - swift https://leetcode.com/problems/validate-binary-search-tree/ Validate Binary Search Tree - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 노드를 이진 탐색 트리인지 판별하는 문제다. 이진 탐색 트리는 왼쪽 자식 노드는 부모 노드보다 작아야 하며, 오른쪽 자식 노드는 부모 노드보다 커야 한다. 뿐만 아니라, 자식의 자식들도 부모 노드보다 크거나 작아야 한다. 즉 아래의 경우는 이진 탐색 트.. 공감수 0 댓글수 0 2021. 8. 20.
LeetCode - 207. Course Schedule - swift https://leetcode.com/problems/course-schedule/ Course Schedule - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com numCourse 라는 숫자변수가 총 들어야하는 수강과목 수 이다. prerequisits [Int] 배열이 들어오는데, 각각 [ a, b ] 를 갖는데, 이는 a를 수강하기 위해서는 b를 필수적으로 수강해야 한다는 뜻이다. a, b 는 numCourse보다 무조건 작은 숫자이다. prerequisit.. 공감수 0 댓글수 0 2021. 8. 20.
LeetCode - 36. Valid Sudoku - swift https://leetcode.com/problems/valid-sudoku/ Valid Sudoku - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 간단한 스도쿠 판별문제다. 행, 열, 그리고 3*3 행렬안에 중복된 숫자가 있는지 판별하는 문제다. 조건대로 행, 열을 모두 판별하면서, 3*3 행렬안에 중복된 숫자가 있는지 판별하는 것을 구현하면 된다. 3*3행렬은, i / 3, j / 3 으로 나눈값으로 판별했다. class Solution { func is.. 공감수 0 댓글수 0 2021. 8. 20.
LeetCode - 31. Next Permutation - swift https://leetcode.com/problems/next-permutation/ Next Permutation - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 주어진 숫자 배열을 통해, 그다음의 순열을 찾는 문제다. 만약 다음 순열이 존재하지 않는다면, 오름차순으로 정렬된 배열로 만들고, 존재한다면 그 다음의 순열로 배열을 만든다. 조금만 고민하면, 특징을 찾을 수 있다. 다음의 순열이 되기 위해서는, 배열의 끝부분부터 탐색하면서, 현재 위치보다 -1 한.. 공감수 0 댓글수 0 2021. 8. 20.
LeetCode - 15. 3Sum - swift https://leetcode.com/problems/3sum/ 3Sum - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 숫자가 들어있는 배열( arr ) 이 주어지는데, 이 배열에서, arr[ i ] + arr[ j ] + arr[ k ] == 0 이면서, i != j 이면서 j != k 이면서 i != k 인 경우의 [ arr[i] , arr[j], arr[k] ] 들을 찾는 문제다. 2개 이상의 경우에는 나름의 최적화가 필요하다. arr의 개수는 최대 3.. 공감수 0 댓글수 0 2021. 8. 18.
LeetCode - 12. Integer to Roman - swift https://leetcode.com/problems/integer-to-roman/ Integer to Roman - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 구현 문제다. 말 그대로 숫자를 로마 표기법으로 변환하는 방법이다. 1,5,10,50,100,500,1000 이렇게 각 값마다 표기하는 로마 표기법이 있고, 8은 VIII 이렇게, 큰숫자부터 앞에서 쓴다. 하지만.. 4는 IIII가 아닌, IV 이다 ! ( ??? ) 9는 VIIII가 아닌, IX .. 공감수 0 댓글수 0 2021. 8. 18.
LeetCode - 22. Generate Parentheses - swift https://leetcode.com/problems/generate-parentheses/ Generate Parentheses - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 숫자 n이 주어지는데, 올바른 괄호의 짝의 개수를 뜻한다. n이 1이면 () 이 올바른 괄호이고, n이 2이면 ()(), or (()) 이 올바른 괄호다. n이 3이면 ()()() or (())() or ()(()) or (()()) or ((())) 이 올바른 괄호다. 이렇게 n이 .. 공감수 0 댓글수 0 2021. 8. 18.
LeetCode - Count Good Nodes in Binary Tree - swift https://leetcode.com/explore/challenge/card/august-leetcoding-challenge-2021/615/week-3-august-15th-august-21st/3899/ 문제는 Good 이라는 노드의 개수를 찾는 것인데, Good 노드인 경우는, root노드로부터 x노드까지 가는 경로에 x노드보다 큰 값이 없는 경우에 Good 노드라고 한다. 노드의 개수는 최대 10만개이다. 간단한 이진트리를 탐색하는 문제다. 자식노드들이 Good노드이냐 아니냐만 판별하여 카운팅하면 된다. 모든 노드들을 방문하므로, O(N)이 걸린다. 그러므로, 매번 자식노드들을 탐색할때, 지금까지 방문한 노드들의 값의 최대값을 저장하면서 현재 노드와 값을 비교하면 된다. class Soluti.. 공감수 0 댓글수 0 2021. 8. 17.
프로그래머스 - 위클리 챌린지 3주차 - 퍼즐 조각 채우기 - swift https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 구현문제에 완전탐색과도 같다. 여기서 핵심을 빠르게 짚어야하는데, 조각을 보드판에 채우기위해서는 꼭 맞아떨어져야 한다는 점이다. 즉, 하나의 .. 공감수 0 댓글수 0 2021. 8. 17.
백준 1561 - 놀이공원 - swift https://www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 꽤나 정답비율이 낮은 편에 속하는 문제다. 이렇게 낮은문제는 한번에 떠오르는 생각만으로 접근하다보면은 틀리기 십상이다. 그러므로 예외처리나, 더 세세하게 경우들을 생각하거나, 구현을 잘해야한다. 일단 N이 20억으로, 한명한명 모두 태워보며 마지막을 찾기란 시간초과다. 그러므로 시간안에 풀수있는 효율적인 방법이 필요하다. "시간"을 기준으로 문제를 접근해본다... 공감수 0 댓글수 0 2021. 8. 5.
프로그래머스 - 표 편집 - 2021 카카오 인턴 - swift https://programmers.co.kr/learn/courses/30/lessons/81303 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 문제해설은 이미 카카오테크에 나와있다. 본글은 연결리스트로 푸는 방법과, 세그먼트트리 + 이분탐색 으로 푸는 방법을 작성할것이다. 굉장히 좋은 문제라고 생각한다. 당시 시험볼때 효율성을 맞추지못한 문제였다. 다시 풀어보니, 연결리스트를 이용하니 쉽게 풀리는 문제였다. 우선 문제의 조건에도 핵심이있다. 마지막에 ".. 공감수 0 댓글수 0 2021. 7. 12.
LeetCode - 898 - bitwise Ors of Subarrays - swift https://leetcode.com/problems/bitwise-ors-of-subarrays Bitwise ORs of Subarrays - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 꽤 어려웠다. 이해하기까지 시간이 걸렸던 문제다. 간단하게 생각하면, 모든 부분연속수열들를 구하여 OR연산하면 되겠지만, 우선 숫자들의 갯수가 최대 5만개이므로, 시간초과가 난다. 조금만 고민해보면, 다음과 같이 알수있다. 주어진 숫자배열을 arr [ i ] 이라고하고, .. 공감수 0 댓글수 0 2021. 7. 1.
백준 10473 - 인간 대포 - swift https://www.acmicpc.net/problem/10473 10473번: 인간 대포 입력은 한 개의 길찾기 문제를 표현한다. 첫 줄에는 두 개의 실수가 입력되며 각각은 당신이 현재 위치한 X, Y좌표이다. 두 번째 줄에는 목적지의 X, Y좌표가 실수로 입력된다. 이어지는 줄에는 대 www.acmicpc.net 두 점사이의 거리공식만 안다면 풀수있다. 물론 조금의 고민이 필요하다. 우선 대포는 어떤 방향이든 50m로 날라갈수있다고 했다. 즉 대포는 50m주변 원으로 날라갈 수 있는데 조금만 고민해보면 어느지점으로 날라가야할지 알 수 있다. 답은 대포지점과 다른점 사이의 직선으로 날라가면 된다. 즉 두 점 사이의 직선의 방정식안에서 50m로 날라가면된다. 하지만 이렇게 50m가 되는 지점을 찾을수없.. 공감수 0 댓글수 0 2021. 6. 29.
백준 1699 - 제곱수의 합 - swift https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp문제이다. dp [ i ] = i값을 만들기위한 최소한의 항의개수라고 정의한다. 그래서 1부터 N까지 하나씩 탐색하면서, 1부터 N까지중에서 제곱수로 dp를 갱신해나간다. 처음에는 각각 10만*10만 시간복잡도인줄 알아서 고민했는데, 알고보니, 제곱수까지만 확인하면된다. 즉 N이 10000까지라면, 제곱수는 1부터 100까지만 확인하면 된다. 10만이라면.. 공감수 0 댓글수 0 2021. 6. 27.
백준 1039 - 교환 - swift https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net 완전탐색이 필요한 문제다. 완전탐색을 하면 중복되는 경우의수가 존재할수있는데, 이는 check [ 숫자 ] [ k ] = k번 교환했을때 숫자가 이미 나왔는지 로 체크하여 중복횟수를 줄일 수 있다. 길이가 1인경우와 길이가 2면서 0이포함된 숫자는 교환할수없다는 부분도 고려해야한다. let inp = readLine()!.split(separator: " ").map{Int(String($0))!} var check = Array(repeating: Array(rep.. 공감수 0 댓글수 0 2021. 6. 26.
백준 15732 - 도토리 숨기기 - swift https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 조금 고민이 필요한 문제였다. 하나씩 규칙들을 탐색하면서 각 상자에 카운팅해도되겠지만, 1개씩 찾다보면 도토리가 총 10억개이므로 시간초과다. 좀 더 효율적으로 찾는 방법이 필요하다. 고민을해보니, 100~150개에서, 10간격이라면, 총 6개 도토리를 넣을수있다. 110~150, 15간격이라면 총 3개 도토리를.. 공감수 0 댓글수 0 2021. 6. 26.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.