gustn3964의 등록된 링크

키자드에 등록된 총 137개의 포스트를 확인하실 수 있습니다.

Naver Blog

개근상 - 백준 1563 - swift

https://www.acmicpc.net/problem/1563메모이제이션을 사용한다. 이전정보로만 판단하여 현재날짜에 가능한 경우의수를 구해낸다.이것이가능하려면, 마지막날짜에 출석인지,지각이몇번인지,결석인지, 결석이라면 결석이 몇번연속인지,를 알아야한다. dp [ i ] = i날짜에 개근상이 가능한 쌍. 으로정의한다.개근상이가능한 쌍은 다음과같이 추려볼 수 있다.0. 출석1. 지각0번 & 결석 1번2. 지각0번 & 결석 2번 3. 지각1번 & 결석 0번 4. 지각1번 & 결석 1번5. 지각1번 & 결석 2번 만약 다음날에 출석을한다면, 출석에는 0,1,2가 담기게된다.결석은 연속으로 하는것이 중요하기때문에 연속하지않는다면 항상.......

원문보기 내부링크
Naver Blog

수 정렬하기 3 - 백준 10989 - swift

https://www.acmicpc.net/problem/10989O(NlogN) 보다 빠른 정렬을 사용해야한다 풀고나서 찾아보니 이러한 정렬을 계수정렬이라고 한다고 한다. 처음에 정렬들을 공부할때 계수정렬! 이름도 어려워보여서 안보고 넘겼었는데, 개념은 쉬운 정렬이였다. 나조차도 풀었으므로, 계수정렬을 모르더라도 풀 수 있다고 생각한다.또한 문제티어자체도 낮다. 개수가 천만이나 되고, 수는 10000보다 작다고했다. 내가 아는 정렬에서 빠른 정렬은 기수정렬(radix sort)이고, 최대값이 작을때 아주 유용한 정렬로 알고있으므로,기수정렬로 작성하고, 제출하려고 메모리제한을 봤는데 왠걸 8메가라니!Int64는 8바이트이고, 천만개면 8만KB, 80MB가.......

원문보기 내부링크
Naver Blog

RGB거리 2 - 백준 17404 - swift

https://www.acmicpc.net/problem/17404메모이제이션을 이용한다. 이번 RGB거리의 조건은 첫번째집이 마지막 N번 집과 색이 달라야한다는 조건이 더 붙었다. 여러번의 삽질 결과, 다음과같이 간단히 할 수 있었다. 첫번째집의 색을 빨강색으로 색칠하고, 바텀업방식으로 메모이제이션으로 N번째를 구하는데,이때는 N번째의 답은 빨강색을 제외한 색이되야한다.이어서 첫번째집의 색을 초록색으로 질하고, 위와마찬가지로 진행하고,이때 N번째의 답은 초록색을 제외한 색이 되야한다. 마찬가지로 파랑색으로만 칠하고 시행한다.

원문보기 내부링크
Naver Blog

기상청 인턴 신현수 - 백준 2435 - swift

https://www.acmicpc.net/problem/2435K구간씩 누적합으로 구해낸다. 0부터 N-1까지 배열을 한번에 훑으면서,인덱스가 K보다 크거나 같은경우 누적합을 최대값과 비교하여 최대값을 갱신해준다. 또한 누적합에서 i-k의 인덱스에위치한 값을 빼준다. 계속해서 누적합을 더해나간다.

원문보기 내부링크
Naver Blog

행성탐사 - 백준 5549 - swift

https://www.acmicpc.net/problem/55492차원 누적합을 이용한다! 1차원누적합으로만 사용하면 시간초과가 난다. 당연히.. 조사영역 K가 10만이니, 날수밖에없다. 요로케 저러케 직사각형들을 그려보아도 2차원누적합을 생각하지 못했다..그렇게 다른블로그를 참고하다가, 아래블로그에서 큰 깨달음을 얻었다!https://peanut2016.tistory.com/218sum [ i ] [ j ] = 1,1좌표부터 i,j 좌표까지의 누적합을 만들어낸다!크으,, 생각한 사람들 대단하다! 나는 한번에 표시된영역을 두번만에 계산하려고 하니까 절대 나올수없었다. 정말 간단하다! 예를 들어 아래와 같이 영역이표시되어있다하자. 위의 누적합을 적용해보면 , 4번만.......

원문보기 내부링크
Naver Blog

어두운건 무서워 - 백준 16507 - swift

https://www.acmicpc.net/problem/165072차원 누적합을 이용한다. sum [ i ] [ j ] = 1,1 좌표부터 i,j 좌표까지 사각형안에 있는 원소들의 합 으로 정의하여, 2차원누적합을 만들고, 쿼리에 따라, 누적합들을 계산하여 사각형안에있는 원소들의합을 구하여 개수로 나눠준다. 2차원 누적합 구하는 방법은 아래글에 설명해놨다https://blog.naver.com/gustn3964/222258402195

원문보기 내부링크
Naver Blog

라이노님의 빠른 입력 readLine 분석하기!

도입.. 제가 존경하고 도움을 주신 라이노님의 빠른 readLine을 분석해보려고 합니다.코드는 아래의 깃헙에 올라와있습니다. swift의 알고리즘 부분에서는 한획을 그은 분이지 않을까 ㅎㅎ 생각합니다 https://gist.github.com/JCSooHwanCho/30be4b669321e7a135b84a1e9b075f88백준에는 입력값이 10만개를 넘어가면 swift에서는 입력받는 시간이 아슬아슬해집니다. 심하면 시간초과로 풀지도 못하죠. 다행히 라이노님의 오픈소스 덕분에! 여러 많은 문제를 해결할 수 있었습니다. 그럴때마다 느끼는 생각은 " 어떻게 기본 readLine() 메서드보다 더 빠를 수 있을까? "였습니다. 매번 사용하면서 언젠가 라이노님의 코드를 깨.......

원문보기 내부링크
Naver Blog

그대,그머가 되어 - 백준 14496 - swift

https://www.acmicpc.net/problem/14496최단경로를 구한다.최단경로는 주로 노드들, 간선, 위치, 와같은 단어들이 주로 문제에서 나오는데, 이문제는 그렇지않다.하지만 그런단어들을 안썼을뿐이지 의미하는 바는 같다. 특정 알고리즘이 특정 문제에만 익숙하면 이런문제에서 놓치기 쉽다. 간선의비용이 모두 1로 동일하다.다익스트라로 풀어도 되겠지만, 도착지점에 종료하지않고 모두 탐색하도록 하면서, bfs로 거리들을 갱신하면서 탐색해도 된다.

원문보기 내부링크
Naver Blog

소형기관차 - 백준 2616 - swift

https://www.acmicpc.net/problem/2616dp를 이용한다. 소형기관차가 끌수있는 객차 수를 D라고한다면,주어진 기차배열안에서 D만큼 3그룹으로 적절히 나누어 최대값을 찾는 문제다.이를 N이 5만이므로 완전탐색은 시간초과가 난다.dp [ i ] [ j ] = 0<=j<=2 , i번째객차까지 , 0~j번소형기관차가 최대로 끌수있는 합. 이라고 정의한다.1번째객차부터 N번 객차까지 탐색하는데,해당객차에서 0~2번 소형기관차가 끌수있는 최대합을 갱신한다.0번소형기관차는 n번객차까지 D만큼안에서 자신이끌수있는 최대를 찾아낸다.1번소형기관차는 , 우선 1번소형기관차가 끌수있는 경우는, 0번소형기관차가 끌고 난뒤다.즉 n번.......

원문보기 내부링크
Naver Blog

새끼치기 - 백준 17291 - swift

https://www.acmicpc.net/problem/17291N이 충분히 작으니 완전탐색한다. 배열을 하나만들고, 배열안에는 벌레의 년수와, 언제태어났는지를 담도록 저장한다. N년도까지 배열의 안에있는 벌레의 년도를 1씩증가시켜주고, 벌레의 길이만큼 0년도로 붙여준다.문제의 지문대로 홀수년도에 태어났으면서 3년이 된다면 삭제해주고, 짝수년도에 태어났으면서 4년이된다면 삭제해준다.

원문보기 내부링크
Naver Blog

백도어 - 백준 17396 - swift

https://www.acmicpc.net/problem/17396단순 다익스트라문제이다 다익스트라를 돌릴때, 다음 노드가 지나갈 수 있는 위치인지 아닌지만 판별해주면된다.지나갈 수 없는 경우는 시야에 보이는 곳이다. 또한, 마지막위치는 항상 시야에보이므로, 지나갈수없는 경우이지만, 마지막 위치라면 큐에넣어주도록 한다.

원문보기 내부링크
Naver Blog

정렬 알고리즘 - (선택,삽입,버블,퀵,기수,계수) - swift

대표적인 정렬알고리즘을 알아보자. 이 글은 선택정렬, 삽입정렬, 버블정렬, 퀵정렬, 기수정렬,계수정렬 을 다뤄볼려고 한다.특히나 각 정렬을 어떻게 구현하냐에따라 의미는 같더라도 수행시간이 많이 달라진다는 점을 깨닫고 쓰는 글이다. # 또한 이글은 항상 오름차순정렬을 기반으로 한다. 선택정렬 여러 블로그를 돌아다녀보면 참 잘만들어준 .gif 파일이 많다. 아래 gif파일을 보면 직관적으로 이해하기가 쉽다. 정렬하고자하는 위치를 "선택" 하여 정렬한다. 0번 인덱스부터 마지막 인덱스까지 탐색하는데, 해당 인덱스가 "선택"된 위치이며, 해당인덱스부터 마지막인덱스사이까지 , 가장 작은 원소를 해당 인.......

원문보기 내부링크
Naver Blog

개업 - 백준 13910 - swift

https://www.acmicpc.net/problem/13910조합과 dp 를 이용한다 어제 이문제를 두세시간동안 못풀었다 ㅠ고수분들께 조언을 구해서 겨우 풀 수 있었다. 푼거는 어제풀었지만, 오늘 정신이 맑은 상태에서 다시 풀어보고 글을 쓰려고 했다. 어제는 긴가민가하면서 풀었지만, 이제는 확실히 이해했다! dp [ i ] = 짜장면의수가 i일때 최소 요리횟수 로 정의한다.웍은 한번에 2개씩 이용할 수 있다.즉 모든 가능한 웍의 2가지조합을 선택하여 dp를 갱신해내면된다. 물론 2가지가 나오지않는다면 1가지웍으로 선택한다. 웍은 최대100개이므로, (N²-N)/ 2 개가 나온다. 짜장면의수는 최대 1만이므로, 약 5천만은 1초안에 계산이 가능.......

원문보기 내부링크
Naver Blog

리조트 - 백준 13302 - swift

https://www.acmicpc.net/problem/133022차원 dp를 사용한다. dp를 1차원배열로 N일마다 최소금액을 적용할 수는 없다.각 날짜마다 쿠폰이 몇개인지에따라, 현재는 최소금액아닐수는 있어도, 나중에는 쿠폰을 사용함으로써 최소금액이 될 수 있기 때문이다.그러므로 쿠폰의 변수도 고려하여, dp [ i ] [ c ] = i날짜에 쿠폰의개수c 에 따른 최소금액 으로 정의한다.i날짜에는 4가지행동을 할 수 있다.i날짜에서 1,3,5일전의 값들안에서 최소금액들을 갱신해주고,i날짜에서 1일전의 값들안에서 쿠폰이3개이상인경우에 쿠폰을 사용하는 것과, i날짜에서 1일전의 값들안에서 1,3,5연속 입장권을 사는 것.i날짜에 만약 갈수없는날이면.......

원문보기 내부링크
Naver Blog

소가 길을 건너간 이유5 - 백준 14465 - swift

https://www.acmicpc.net/problem/14465누적합을 이용한다. 해당i번째에 신호등이 고장났는지 아닌지를 구별하기위해 bool 타입의 damage 1차원배열을 만들어둔다. 1번부터 N번까지 탐색하는데, 누적합을 사용하여, 해당 i번째 신호등이 고장났으면 1씩 더해준다.만약 i번째가 K보다 크다면, i-K번째 신호등이 고장났다면 누적합에서 빼준다.

원문보기 내부링크
Naver Blog

동전바꿔주기 - 백준 2624 - swift

https://www.acmicpc.net/problem/2624냅색문제처럼 접근한다. dp [ k ] [ i ] = i번째동전까지 사용하면서k원을 만드는 경우. 로 정의하고, 냅색문제처럼 접근한다. i번째동전을 1...nj개수까지 사용하면서 만들수 있는 경우를 탐색한다. 이와같이 접근하면, 시간복잡도는 이론상 O(K*T*N) , 약 10억이되는데, 문제에서 방법의수는 2의31승을 넘지않는다고 하므로, 시간초과가 나지 않는 듯 하다.

원문보기 내부링크
Naver Blog

1,2,3 더하기 2 - 백준 12101 - swift

https://www.acmicpc.net/problem/12101N이 10이하다. 1,2,3으로 10을 만들수있는 경우의수는 276개로 굉장히 작다. 그러므로, 모든 가능한 경우의수를 하나씩 만들어보며 추가해나가도 1초안에는 충분히 가능할 숫자이다. dp [ i ] = 숫자 i를 만들기위한 가능한 경로들 로 정의하여, 1부터 N까지 만들수있는 경로들을 만들고, N에 해당하는 경로들을 sort하여 출력해낸다.

원문보기 내부링크
Naver Blog

본대 산책 - 백준 12849 - swift

https://www.acmicpc.net/problem/12849각 건물에 i시간에 도착가능한경우를 구한다. 우선 각 건물들이 인접한 건물들을 지정해준다. 예를들어, 정보과학관은 전산관,미래관과 연결되어있다.신양관은 전산관과 미래관,전리관,한경직기념관 과 연결되어있다. 간단하게 각 건물들을 번호로 부여하여, 각 번호에 연결된 번호들을 배열로 만들어준다.dp [ i ] [ k ] = i 시간에 k건물에 도착가능한 경우라고 정의하고, 1부터 D시간까지 dp테이블을 갱신해둔다. 우선 정보과학관에 시간 1에 도착가능한경우는 없다.전산관이 시간1에 도착가능한경우는 언제일까? 전산관과 인접한 건물들이 시간0에 도착가능한 경우일때, 전산관에 시간.......

원문보기 내부링크
Naver Blog

모두의 마블 - 백준 12845 - swift

https://www.acmicpc.net/problem/12845최대값을 찾고, 인접한 값을 없앤다. 우선, 카드의 개수가 1000개이하이므로, 매번 최대값을 찾는데는 큰 비용이 들지 않는다.또한, 특정요소를 삭제하는데도 큰 비용이 들지 않는다.항상 최대값을 찾아, 인접한 값을 더해주는것이 최적이므로, 최대값을 찾아내고,인접한 갑중 하나를 더하며 없애나간다.

원문보기 내부링크
Naver Blog

가희와 3단 고음 - 백준 16162 - swift

https://www.acmicpc.net/problem/16162차례대로 다음 고음을 찾는다. 문제는 순서대로 있는 참가자들의 음들중에 음A를 시작으로 D음씩 올라가는 X단 고음을 형성하는 것을 찾으면된다.그중에서도 가장 높은 X단 고음을 찾으면된다.A가 1 이고, D가 2이고,참가자들의 음이 [ 1, 3, 4, 2, 1, 5, 6, 9, 8, 7 ] 이면 다음과 같이 찾으면된다.[ 1, 3, 4, 2, 1, 5, 6, 9, 8, 7 ]

원문보기 내부링크
Naver Blog

전광판의숫자 - 백준 16159 - swift

https://www.acmicpc.net/problem/16159모두 구현한다. 우선 처음에 주어지는 전광판의 숫자들은 다행히도 각 불빛의 합이 유일하다.0은 10개, 1은 6개, 2는 14개, 3은 9개...로 각각 유일하게 불빛이 켜져있다. 각 불빛의 합을 통해 현재 전광판의 숫자들을 알아낼 수 있다.그다음에 각 전광판의 순열의 배열은 10자리인경우, 총 3백만정도 경우이므로, 다 만들어서 해도 시간초과는 나지않을거다. 하지만 규칙만 찾는다면 모든 순열을 만들지 않고도 알 수 있다. 만들어낸 숫자배열을, 뒤에서부터 2개씩 탐색하여 값이 작아지는 경우가 발생하면,뒤에서부터 값이작아지는 경우까지만 배열을 다시만들어내면된다.3,4,5,2,1 의 전.......

원문보기 내부링크
Naver Blog

기타 레슨 - 백준 2343 - swift

https://www.acmicpc.net/problem/2343최대길이로 이분탐색한다. 레슨의 가장 작은값을 Left로, 레슨의 모든 합을 right로 하여,이분탐색한다. 결정된 mid를 통해, 레슨을 순차적으로 탐색하는데, 이전의합들이 mid보다 작거나 같을때까지만 더해나가며,mid보다 클경우는 group으로 카운팅하고, sum을 현재값으로 초기화하는데,만약 현재값이 mid보다 클경우는, 해당 mid로는 만들 수 없다.그렇게 나온 group이 M보다 크거나, 마지막 sum값이 mid보다 크다면 해당 mid로는 만들 수 없으므로, mid를 늘리고, 그외의경우는 더 줄이면서 탐색해본다.

원문보기 내부링크
Naver Blog

병사 배치하기 - 백준 18353 - swift

https://www.acmicpc.net/problem/18353가장 긴 감소하는 부분수열을 구한다. 문제는 가장 적은인원을 열외함으로써 가장 긴내림차순의 길이를 구하는 것이다.그러므로, 가장 긴 감소하는 부분수열을 구하는 간단한 dp로 , O(N²)으로 구할 수 있다.

원문보기 내부링크
Naver Blog

호텔 - 백준 1106 - swift

https://www.acmicpc.net/problem/1106dp를이용한다. dp [ i ] = i비용으로 얻을 수 있는 최대 고객수 라고 정의하여 풀어낸다. 여기서 문제는 i의 범위가 어디까지인지다.처음에는 100보다 작다고했으므로, 최소비용인 1으로 1000을 나누었는데, 틀렸다.다시생각해보니 비용이 100일때, 고객의수가 1증가할 수 있으므로, 이때 C가 1000이라면, 비용의 범위는 10만까지 증가한다.

원문보기 내부링크
Naver Blog

우유도시 - 백준 14722 - swift

https://www.acmicpc.net/problem/14722dp로 해결하면서, 예외경우도 고려한다. 동쪽,남쪽으로만 움직이고, 다시 돌아가지 않는다. 그러므로 특정위치에서는 어느쪽으로 오든 경로는 유일하다 .이중에서 가장 큰값들만 남기도록 하면된다. 주의할점은, 첫번째위치가 딸기우유라는 보장이없다.두번째는, 해당위치에서 우유를 먹지않아도된다.dp [ i ] [ j ] [ k ] = i,j위치까지 마지막으로 k우유를 먹으면서, 최대 마신 우유개수 라고 정의한다.한위치에서 동,남 탐색하면서,그안에서 딸기,바나나,초코를 모두 탐색한다.

원문보기 내부링크
Naver Blog

달빛여우 - 백준 16118 - swift

https://www.acmicpc.net/problem/16118다익스트라를 2번돌린다. 늑대가 움직일때와,여우가 움직일때 다익스트라 각각 돌려준다.우선 주의할점은, 늑대는 속도가 반으로줄었다가, 두배로늘어났다가 하는데, 반으로줄어들때, Int타입으로 나누면 소수점이 사라진다. 그렇다고 double 타입으로쓰면, 아주 미세하게 나눠지는 값에서 오차가 발생하므로 정확한 값 비교가 어려워진다.그러므로, 간단하게 속도를 처음부터 10을 곱한상태에서 시작한다.그렇게 하면 Int로 2로나누어도 값의 손실이 없다. 여우가움직일때는 단순 다익스트라이고, 늑대가 움직일때는 2가지경우를고려한다.현재 움직임이 빠른속도인지,느린속도인지. 그러므로, dp를.......

원문보기 내부링크
Naver Blog

사수빈탕 - 백준 14585 - swift

https://www.acmicpc.net/problem/14585dp를 이용한다. 수빈이는 위쪽 또는 오른쪽으로만 이동할 수 있다고한다.그러므로 해당위치에 도착하는 시간은 항상 똑같게 된다. 2차원배열로 아래로 훑는걸 적용하기 위해 입력값을 반대로 받았다.그러므로 위쪽이 아닌, 아래와 오른쪽으로만 이동하게끔 했다. 0,0 부터 300,300 까지 모든 지점을 탐색하면서 최대값으로 갱신해준다.

원문보기 내부링크
Naver Blog

Game Map - 백준 14953 - swift

https://www.acmicpc.net/problem/14953dfs + dp를 이용한다 간단하게 해석하면, 연결된 도시들은 이웃이라고부르고, 해당도시에 연결된 도시개수가 이웃수가된다.문제는 가장 긴 이웃리스트의 길이를 찾는다.가장 긴 이웃리스트는, 다음과 같이 조건을 만족해야한다.예로 a1,a2,a3,a4 리스트가 있다면, 각 도시들은 달라야하며,a1,a2 a2,a3 a3,a4 는 이웃이여야하고,a2는 a1보다 이웃수가 많아야하고,a3는 a2보다 이웃수가 많아야하고,a4는 a3보다 이웃수가 많아야한다.우선 입력값들을 통해 각 도시마다 이웃의 수를 알 수 있다. dp [ i ] = i번도시부터 가장긴이웃리스트의 길이 라고 정의하고, 각 도시마다 dfs를 돌리면서, dp의.......

원문보기 내부링크
Naver Blog

한조서열정리하고옴ㅋㅋ- 백준 14659 - swift

https://www.acmicpc.net/problem/14659앞에서부터 탐색해나간다. 봉우리를 정하면서 탐색해나간다.만약 봉우리가 다음봉우리보다 높다면 처치수를 +1 카운팅시키고, 그렇지않다면, 봉우리를 갱신하면서, 처치수를 0으로 만든다.처치수가 가장높은 값을 출력한다.

원문보기 내부링크
Naver Blog

비밀번호 - 백준 2780 - swift

https://www.acmicpc.net/problem/2780dp를 이용한다. 각 자리마다 가능한경우를 죽 나열하면 너무나 많은 경우가 나온다.길이가 N이라면, 길이를 1부터 N까지 각 숫자가 마지막으로 끝나는 경우를 생각해본다.1일때는 모든 숫자들은 경우가 1개이다.2일때는, 숫자 1를예로들면, 숫자1이 마지막으로 끝날때를 생각해본다. 어떤경우일까? 즉, 1이 마지막으로 눌릴 수 있는 경우인데, 이때는 1의 인접한 값들일때다. 즉 2,4가 그전에 눌렸을때, 1을 누를수있다.그러므로, 길이가 1일때, 2와 4가 마지막에 눌린경우의 합이 길이가2일때 숫자1을 눌렀을때 경우의수다.마찬가지로, 숫자2일때는, 숫자2가 마지막에 눌렸을때이고, 이는 숫자2와.......

원문보기 내부링크
Naver Blog

크리보드 - 백준 11058 - swift

https://www.acmicpc.net/problem/11058모두 탐색해본다. 처음에는 bfs로 접근했다가, 메모리 초과났고, 뭔가 빈틈이 많아서 다시 고민했다.앞에서 접근한방법으로 깨달은 것은, 붙여넣기하기 위해서는 3단계가 필요하다.즉, N번째 버튼을 누를때는, N-3번째때 나온값을 그대로 추가한값을 출력할 수 있다.예를들어, N이 6일때는, 3번째때 나온값을 그대로추가한값과, 2번째때나온값을그대로 2번 추가한값, 1번째때 나온값을 그대로 3번추가한값, 그리고, 6번그대로 A를 붙인값, 총 4가지 경우가 있다.그중에서 제일 큰값을 갱신해준다. 이 큰값이 9번째때 복사할값이기때문이다. 그럼 복사및붙여넣기에 대한 정보를 담는 배열을 만들어.......

원문보기 내부링크
Naver Blog

안녕 - 백준 1535 - swift

https://www.acmicpc.net/problem/1535배낭문제로 해결할 수 있다. 연속해서 사용하거나, 그런 조건들없이, 최대기쁨을 얻기위해 특정사람에게 인사하거나 안하거나 하므로,배낭문제로 해결할 수 있다.모든사람들을 체력0부터 99까지 탐색하는데,체력i일때 인사할 수 있는 최대 기쁨을 계산한다. 각 사람이 인사하고, 안하고, 둘중하나이므로, 최대기쁨을 계산할때는, 체력 i일때, 해당사람전에 체력i일때의 기쁨과, 해당사람이 인사하고서의 기쁨중에 최대값으로 가진다. dp [ i ] [ k ] = 체력이 i일때, k번사람까지의 최대기쁨 (1번사람부터 k번사람까지의 인사한사람)

원문보기 내부링크
Naver Blog

BOJ 거리 - 백준 12026 - swift

https://www.acmicpc.net/problem/12026현재위치에서 갈 수 있는 거리들을 모두 탐색한다.앞에서부터 탐색하는데,예를들어, 현재위치가 B라면 남은 위치들중 O인 위치들만 선택하여 에너지를 최소로 갱신한다.처음은 무조건 B이므로 탐색이가능하지만,두번째부터 마지막위치까지는 현재 위치가 에너지가 갱신되있는경우만 탐색한다. 갱신되지않은곳은 갈 수 없는 위치이기때문이다.

원문보기 내부링크
Naver Blog

BABBA - 백준 9625 - swift

https://www.acmicpc.net/problem/9625이전의 B와 A의 개수로 다음을 알 수 있다.A는 B 로 바꿔주고,B는 BA로 바꿔준다.즉, A가 2개, B가 3개 있다면, 여기서 버튼을 한번더 누르면,A는 이전B만큼 개수가 되고, B는 이전B의개수 + 이전A의 개수가 된다.

원문보기 내부링크
Naver Blog

악수 - 백준 8394 - swift

https://www.acmicpc.net/problem/8394N번째 사람이 악수를 하는경우와 안하는 경우. 악수를 할수 있는 경우의수 를 A라고 하고,악수를 할수 없는 경우의수 를 B라고 하겠다.우선 1명일때 당연히 A는 0이고, B는 1이다.그다음 2명일때, 즉 2번째사람이 A는 1번째사람이 B일때이다. 동시에 악수를 할 수 없기때문이다.2번째 사람이 B는, 1번째사람의 A+B인 경우다. 2번째사람이 악수를 하지않는 경우는 그전사람이 행했던 모든 경우의수이여야한다.그럼 2번째사람의 A는 1이고, B는 1이된다.그다음 3명일때, 즉 3번째사람이 A는 2번째사람이 B일때다.3번째사람이 B는 2번째사람의 A+B인 경우다.그러므로, 3번째사람은 A = 1 , B .......

원문보기 내부링크
Naver Blog

피보나치 수 4 - 백준 10826 - swift

https://www.acmicpc.net/problem/10826배열을 통한 숫자계산하기. N번째피보나치수를 구하는 문제인데, N이 3자리수만 되도 2의64승이 훌쩍넘어버린다. N이 4자리수만되도 Double타입을 넘어버려 print가 inp로 찍힌다.그러므로, 기존 정수타입,실수타입으로는 계산이 어려우므로, 다른방법으로 접근해야한다.우선 Double타입으로 1000번째 숫자길이를 찍어보니, 209 길이가된다. 10000번째는 부디 4,5천? 길이가 안넘길 바랬다. 4,5천길이가 되지않는다면, 숫자들을 배열로 담아서 계산할 수 있는 양이 되기때문이다. 123 + 123 을 배열로 계산할건데,[1,2,3] + [1,2,3] 으로 계산한다.즉, 두개의 배열을 앞에서부터 더하면된다.두 원.......

원문보기 내부링크
Naver Blog

동방프로젝트(Large) - 백준 14595 - swift

https://www.acmicpc.net/problem/14595누적합을 이용한다.배열을 N크기만큼 0으로 만들고,입력값 x는 [x] += 1입력값 y는 [y] -= 1하여 배열들을 갱신한다.모두 갱신되었다면, 1부터 N까지 누적합을 해나간다. 만약 0이라면, 방이 있다는 것으로, 카운팅시킨다.

원문보기 내부링크
Naver Blog

달나라 토끼를 위한 구매대금 지불도우미 - 백준 17212 -swift

https://www.acmicpc.net/problem/17212dp를 이용한다. 1원부터 N원까지, 만들수 있는 최소한의 동전개수로 dp를 갱신한다.dp [ i ] = i 원으로 만들수 있는 최소한의 동전개수 1원부터 7원까지 dp를 갱신했다면,8원을 만들기위해서는, 1원,2원,5원,7원이 있을때,1원은 7원으로 만들수있는 최소동전개수 + 1 개가되고,2원은 6원으로 만들수 있는 최소동전개수 + 1 개가되고,5원은 3원으로만들 수 있는 최소동전개수 + 1 개가된다.7원은 1원으로 만들수있는 최소동전개수 + 1개가된다. 그중에서 가장 작은동전개수가 8원을 만드는 최소동전개수가된다.

원문보기 내부링크
Naver Blog

과일서리 - 백준 17213 - swift

https://www.acmicpc.net/problem/17213dp + 재귀함수로 풀어낸다 N가지 종류 과일을 하나씩 가져가도록 한다. dp [ i ] [ left ] = i번째 종류과일을 선택할때, left개 남아있을때, 총 경우의 수 예제와같이,1번째과일에서는 1개를 선택하고,2번쨰과일에서는 나머지9개안에서 선택해야한다. 1개를선택했다면, 3번째과일은 8개를 선택해야한다.만약 2개를 선택했다면 3번째과일은 7개를 선택해야한다...... 만약 8개를 선택했다면 3번째과일은 1개를 선택해야한다.이것으로 알 수 있는 경우의수가, dp [ 2 ] [ 9 ] = 8개의경우의수가 있다는 걸 알 수 있다.

원문보기 내부링크
Naver Blog

프린터 큐 - 백준 1966 - swift

https://www.acmicpc.net/problem/1966주어진 조건대로 구현한다. N이 크지않기때문에, removeFirst를 사용했다. while문으로 큐가 빌때까지 실행한다.첫번째원소와 나머지원소를 모두비교하면서, 맨뒤로보내거나, 첫번째원소를 없앤다.

원문보기 내부링크
Naver Blog

1로 만들기2 - 백준 12852 - swift

https://www.acmicpc.net/problem/12852dp를 이용한다. N을 1로 만들기보다는, 1에서 N으로 만드는 경우를 구해본다. dp [ i ] = ( i를 만들기위한 가장 최소경우의수, i를만들기위한 이전의 값 ) 으로 정의한다. i를 만들기위한 이전의값이 필요한 이유는, N까지 가장 빠른 경우의수를 구한다음에, N을 1로 가는 경로들을 dp를 통해 찾아내기 위해서다. dp [ i ] 는 1에서부터 시작하므로, 반대의연산, +1, *2 , *3 3가지경우로 갱신해나간다.각 연산마다 가능한 경우의수가 최소의경우로만 dp[i]를 갱신한다. 예를들어, 6을만들기위해서는, dp[5] + 1, dp[3] * 2 , dp[2] * 3 인경우가있다.dp[5] + 1,인경우는, dp[5]를 만들.......

원문보기 내부링크
Naver Blog

캡틴 이다솜 - 백준 1660 - swift

https://www.acmicpc.net/problem/1660DP로 해결한다 N개가있다면, N개를 최소의 사면체의 개수를 구하기 위해서는, 그전단계, 1~N-1까지 만들수있는 사면체의 수를 최소로 구해놓으면 구할 수 있겠다라고 생각했다.그래서, 각 i개마다 만들 수 있는 최소의 사면체를 구하기위해서는 모든 사면체가 필요했다.이 모든사면체가 약 100개정도면 시간안에 풀 수 있겠다라고 생각했다.100*300000 은 3천만으로 시간안에 구할 수 있기 때문이다.다행히도, 모든사면체를 구해보니 120개정도 나왔다. 그러므로, DP로 모든사면체를 i개에대해 탐색하며, 최소사면체개수로 만들어준다.

원문보기 내부링크
Naver Blog

1,2,3 더하기 4 - 백준 15989 - swift

https://www.acmicpc.net/problem/15989dp를 이용한다. 1부터 N까지 , 1,2,3으로 만들수있는 경우의수를 구해야한다. 순서만 다른경우는 1개로 치기때문에, 1,2,3 각 숫자마다 모두 1부터 N까지 갱신시켜놓는다.

원문보기 내부링크
Naver Blog

Moo 게임 - 백준 5904 - swift

https://www.acmicpc.net/problem/5904분할정복으로 해결한다. 문제의 조건대로 S(i)를 구해보면 다음과같다. S(3)을 분해해보면 다음과같다.즉, S(i)를 만들어보면서, N보다 커졌을때, 더이상 만들지않고, 분할해본다. 조건은 1. S(i)의 가운데 문자열 moooo... 에 속하는지,2. 그외인지, 에따라 나눌 수 있다.1에 속한다면, 기저사례가되면서, 맨앞인경우는 m이되고, 그외는 o가된다.2에 속할경우는, S(i-1)로 다시 위의조건을확인한다. 다만, S(i-1)+가운데moo.. 길이보다 큰경우는, N을 그만큼 빼주도록하고,작을경우는 왼쪽에서 탐색하는것이므로, 그대로 N을 사용한다.

원문보기 내부링크
Naver Blog

자원캐기 - 백준 14430- swift

https://www.acmicpc.net/problem/14430dp를 이용한다. 로봇은 오른쪽이나 아래로만 내려간다.그러므로, 위에서부터 아래로 내려가되, 행을 훑으면서 dp테이블을 최대값으로 갱신해주면 된다.왜냐하면, 로봇은 오른쪽이나 아래로만 내려가는데, 이와같이 dp테이블을 갱신해주면, 항상 그위치에는 최대의값만 저장되기 때문이다.

원문보기 내부링크
Naver Blog

숫자카드 - 백준 2591 - swift

https://www.acmicpc.net/problem/2591메모이제이션을 사용한다. 숫자를 일렬로 앞에서부터 탐색한다.각 하나의 숫자가 가능한경우를 탐색하는데, 가능한경우는 2개로 나눌 수 있다.각 하나의 숫자가 혼자가능한경우와 이전숫자와 연관된 경우, 2가지를 탐색한다.즉, 2712 이라면,2에서는 혼자가능한경우와 이전숫자와연관된경우를 구하는데, 혼자가능한경우는 당연히 1개이고,이전숫자와연관된경우는 이전숫자가 없기때문에 0개다.그러므로, 2에서는 총 1개경우가 가능하고,7에서도 마찬가지로 탐색하는데, 혼자가능한경우도 마찬가지로 1개이다.즉 7이전까지 가능한 모든경우들을 가져올 수 있다.7이전에 2는 모든경우가 1개였으므로, 1개.......

원문보기 내부링크
Naver Blog

스테판쿼리 - 백준 14654 - swift

https://www.acmicpc.net/problem/14654구현문제다. 가위바위보의 결과를 어떻게 코드로 구현할지가 관건이다.이것은 다양하게 구현할 수 있다고생각한다.나는 A가 가위,바위를 낼경우는 이기고 지는것은 동일하게 적용된다는점과 A가 보일때만 지는경우만 예외적으로 다루었다. 또, 비길경우는 이전의 승리자가 지게된다는 점도 고려한다.

원문보기 내부링크
Naver Blog

하늘에서 별똥별이 빗발친다. - 백준 14658 - swift

https://www.acmicpc.net/problem/14658완전탐색해준다. 내가 혼자서 풀긴했지만, 너무 복잡하게, 어렵게 풀어냈다.내가접근한 방법은, 처음에는 좌표를 다 그려보았다. 각 좌표마다 모두 탐색해주면 되겠다 생각이 들었다. K가 100이므로 충분히작기때문에 100*100은 너무나 가능하다고 생각했다.하지만 내가 생각한건 각좌표가 모서리일때만, +L 넓이안에서 계산하는거라, 답이될 순 없겠다라고 생각했다. 그렇게 다른방법을 생각하다가, 좌표들을 x축으로 정렬하여 일렬로 내려, 1차원으로보면, 투포인터로, 구간이 L안에들어오는지로 판단하며 훑어내려갈 수 있겠다라고 생각했다.먼저 x축으로 가능한 구간들을 찾아내어, y축으로 정.......

원문보기 내부링크
Naver Blog

준오는 최종인재야!! - 백준 14657 - swift

https://www.acmicpc.net/problem/14657가장긴지름의 응용버젼 꽤 어려웠다. 단순히 가장긴지름을 찾으려고한다면, 시간초과가난다.이 문제에서 가장긴지름이라는 것은 과제의 개수가 된다.하지만 과제의 개수가 모두동일한 지름들이 여러개라면?물론 노드의개수보다는 많이적겠지만, 그래도 시간초과다.그러므로, 가장긴지름을 찾을때, 조건을 붙여준다. 가장긴지름이면서, 시간이 적게걸리는. 노드를 찾는다.문제의 데이터들은 트리형식이므로, 어떤 노드를 하나잡고, dfs돌려서 시간이 적게걸리면서 가장긴지름, 노드를 찾고,그 노드로 다시 dfs를 돌린다.

원문보기 내부링크
Naver Blog

욱제가 풀어야 하는 문제 - 백준 18249 - swift

https://www.acmicpc.net/problem/18249DP를 이용한다. 1부터 N까지일때 계산해나간다. 문제의 조건을 그릴 수 있는 선분으로 나타내보면,2가지가 있다. 1개일때 그릴수있는 선분과2개일때 크로스되게 그릴 수 있는 선분으로 나뉜다.그러므로, 두가지 경우로 1부터 N까지 가능한 경우의수를 갱신해나간다. 또한 특정 규칙이 있기때문에, 다음과같이 dp[i]는 점화식으로 표현할 수 있다.dp [ i ] = dp [ i - 1 ] + dp [ i - 2 ]

원문보기 내부링크
Naver Blog

야곰님의 오토레이아웃 정복하기

본 글은 돈을받고 광고하는 것이 아님을 알려드립니다 ㅎ강 력 추 천 2주동안 열심히 들었다. 정말 돈이 아깝지 않은 정말 정말 좋은 강의다. 자신이 오토레이아웃이 부족하다? 그렇다면 무조건 이 강의다.구성은 앞부분개념과 뒷부분 실습및 프로젝트다. 앞부분개념을 설명할때 애플의 공식문서를 참조하시는게 너무 좋았다. 그리고 뿐만 아니라 중요한 내용들이 포함된 WWDC를 알려주시면서 시간날때 보라고 하신다. 나는 이미 오토레이아웃의 기본지식은 있었고, 정확하게 딱 안다고 생각못했는데, 이 강의를 통해 자신감이 생겼다. 이미 기본지식이 조금있었던 터라, 너무 유익하고 재밌었다. 덕분에 priorty, intrins.......

원문보기 내부링크
Naver Blog

적록색약 - 백준 10026 - swift

https://www.acmicpc.net/problem/10026간단한 bfs or dfs 탐색문제이다. 같은색상으로 인접한 색들을 그룹으로 구현하면 된다. 색이담긴 2차원배열을 하나씩 탐색하는데, 탐색할 색이, 이미 그룹으로 처리되었는지 아닌지를 판별하기 위해 그룹처리목적으로 2차원배열을 만들어서 사용했다. 탐색할때 bfs 또는 dfs로 좌우위아래 탐색하며 같은색이면 그룹처리2차원배열을 갱신해준다.그렇게되면 2차원배열안에서 다음 색은 이미 그룹처리되어있거나 아니거나 둘중하나인데, 그룹처리되었다면 이 값은 더이상탐색하지않고 다음색으로 넘어간다. 마찬가지로 빨강,초록을 구분하지 못하는 사람의 경우에도, 빨강을 탐색할때는 좌우위아래가.......

원문보기 내부링크
Naver Blog

계단 오르기 - 백준 2579 - swift

https://www.acmicpc.net/problem/2579현재 계단을 밟으려고할때, 그전의 계단을 밟았니, 안밟았니? 이제 이런 유형의 문제를 보면 DP문제임을 파악할 수 있었다. 그리고, DP로 풀수있게끔 현재의 계산과정이, 마지막 계산과정도 동일하게 결과를 출력할 수 있는지 이해하려고 한다.내가 세운 식이 마지막 결과에도 답을 줄 수 있는지 여러번 시도하고, 코드로 작성했다.내가 이문제를 DP로 풀수있었던 이해한 방법은 다음과 같다.현재 계단을 밟을 수 있는 방법은, 1. 전의 계단을 밟거나, 2. 전전의 계단을 밟는 것 둘 중하나여야한다.여기서 전의계단을 밟기위해서는 전의계단은 그전의 계단을 밟지 않아야한다. 즉, 현재 3번째계.......

원문보기 내부링크
Naver Blog

우선순위 큐,힙 구현하기 - swift

우선순위 큐를 구현하기전에 힙(Heap)을 알아야한다. https://www.youtube.com/watch?v=jfwjyJvbbBI힙을 모른다면 위의 강의를 추천한다. 3분도 걸리지 않는 강의지만 정말 이해가 쏙쏙된다.이영상을 이해하게되면 힌트만 주면 우선순위큐를 구현할 수 있을 수 있다! 정말 어렵지 않은 자료구조입니다! ( 알고자 하는 마음으로 배운다면 금방이해할 수 있다. 하지만 또 자료구조야.. 어려워.. 라고 처음부터 겁먹고 배울려면 이해가 쉽게 안된다. ) ( 아래의 설명하는 내용들을 이해하기 위해서는 꼭 위의 동영상을 이해해야한다 ) 힙(Heap)힙이란, 최소값 또는 최대값을 빠르게 얻기위한 자료구조이며, 완전이진트리면.......

원문보기 내부링크
Naver Blog

구간합구하기4 - 백준 11659 - swift

https://www.acmicpc.net/problem/11659합들을 한번만 계산해놓는다. i번째부터 j번째수까지의 합들을 쿼리라고 지칭하면,쿼리들의 개수가 최대 10만개이다. i번째와 j번째의 간격의 차가 0이거나 1이면 계속해서 합을 계산해도 괜찮겠지만,간격의 차가 너무 크면 매번 쿼리에 대해 합을 계산하는것은 너무 오래걸린다.다행이 이 문제는 배열들의 숫자가 변하지 않는 점에서 쉽게 구할 수 있다.배열들을 순회하며 계속해서 합을 쌓아나가는 배열을 만든다. 위의 예제처럼 합의배열은 [0] 에서시작한다.위의 예제배열을 순회하며 합을 쌓아나가면된다. [0,5][0,5,9][0,5,12][0,5,12,14][0,5,12,14,15] 합의 배열안의 각 요소들은 다음과같.......

원문보기 내부링크
Naver Blog

스티커 - 백준 9465 - swift

https://www.acmicpc.net/problem/9465패턴만 잘 알면 된다! 2차원배열로 생각해보면, 첫번째 칼럼에서 첫번째 줄에서 시작한다고하면 (초록색)큰 값일 가능성은 셋중 하나에 이렇게 나온다.첫번째 칼럼에서 두번째 줄에서 시작한다고 하면 (초록색)큰 값일 가능성은 셋중 하나에 나온다. 이렇게보면 패턴이 보인다 첫번째 줄에서 시작하면 그다음 칼럼의 두번째 줄,또는 그다음다음칼럼의 두번째줄.두번째 줄에서 시작하면 그다음 칼럼의 첫번째줄,또는 그다음다음 칼럼의 첫번째줄이된다. 그러므로, 초록색이 3번째칼럼 첫번째 줄이라면, 이 값이 최대일 가능성은, 첫번째칼럼의 첫번째줄과 두번째칼럼의 두번째줄과의 합.......

원문보기 내부링크
Naver Blog

이친수 - 백준 2193 - swift

https://www.acmicpc.net/problem/2193패턴만 파악하면 쉽다! 재귀함수로 생각하면 참 쉽다. 재귀함수로 구현하면 직관적으로 구현할 수 있기 때문이다. 여기서 직관적이다 라는 말은 생각하는 것처럼 간결하게 코드가 작성이 가능하다라고 볼 수 있다. 현재 0일때는 다음이 0또는 1로 재귀함수를 돌리고,현재 1일때는 다음이 0으로 재귀함수를 돌리면된다.이렇게 짜니 시간초과났다 그말은 더 빠른 방법이 있다는 뜻이다. 생각보다 간단한 문제다.1부터 시작해서 어떤 경우의수가 나오는지 손으로그려보면 금방 파악이 된다. 마찬가지로 0일때는 0또는 1의 경우수가 나온다. 1일때는 0만 나온다. ( 빨간색은 경우의수를 뜻한다 ).......

원문보기 내부링크
Naver Blog

부등호 - 백준 2529 - swift

https://www.acmicpc.net/problem/2529모든 수를 앞에서부터 넣어보면 된다. 구해야하는 값이 가장 큰값과 가장 작은 값을 찾는거다.가장 직관적으로 생각할 수 있는것이 가장 큰값은 당연히 앞에서부터 큰값을 넣어주면 될 것 같다.반대로 가장 작은 값또한 가장 작은 값부터 넣어주면 될 것 같다. 가장 큰 값을 구하는 걸로 예시를 들면,가장 큰 값부터 넣어준다. 그다음 등호를 비교하여 성립하지 않으면 다시 뒤로돌아가 그보다 낮은 값을 넣어준다.예제를 설명해보면, 처음엔 9가들어간다.그다음 9보다낮은 8을 넣는다.첫번째 등호를 비교한다.9 < 8 는 틀리므로,8을 빼고 7을 넣어본다.다시 등호를 비교한다.9 < 7 또한.......

원문보기 내부링크
Naver Blog

랜선 자르기 - 백준 1654 - swift

https://www.acmicpc.net/problem/1654이분탐색으로 풀면 효과적이다. K개의 랜선은 길이가 제각각이다. 이런 문제를 처음접하면 떠올릴 수 있는 방법이 랜선에 각각 어떤값을 넣어 최대값을 찾으면되는데, 이 어떤값을 어떻게 결정할지 참 난감하다. 뭔가, 가장 길이가 긴랜선과 가장 길이가 짧은 랜선, 또는 중간랜선.. 등등 어떤값을 정하고 싶은데, 다 마땅치않다. 또한 K개의 랜선은 최대 10,000개이며, 각랜선의 길이는 최대 2의 31승 -1 이다 . 이는 2,147,483,648 즉 21억이다. 참 난감하다!이럴때 이분탐색을 이용하면 매우 효과적이다.이분탐색은 logN 만으로 원한는 값을 찾을 수 있는 매우 빠른 탐색 알고리즘이다. 탐색은.......

원문보기 내부링크
Naver Blog

수 찾기 - 백준 1920 - swift

https://www.acmicpc.net/problem/1920빠르게 찾을 수 있는 방법을 요구한다. 아래와 같이 N개의 정수배열이 있다면, 이 정수배열안에 특정 숫자들이 있는지를 빠르게 찾을 수 있는지 요구한다. 배열안에서는 index로 값을 바로 탐색할 수 있다.하지만 특정 index에 값을 정확히 모를경우 이 index는 0부터 배열.count 만큼 다 탐색해야할 것이다. 즉, 한개의 값을 찾는데 걸리는 시간은 O(N)이걸린다. 제한시간이 2초이지만, 배열은 10만개이고, 탐색하고자하는 배열도 10만개이므로, 10만*10만 이걸리므로 너무오래걸린다.즉 O(N²) 보다 빠르게 찾을 수 있는 방법을 모색해야한다.방법은 많다.나는 가장 먼저떠오른게 swift의 Dict.......

원문보기 내부링크
Naver Blog

색상환 - 백준 2482 - swift

https://www.acmicpc.net/problem/2482패턴을 파악하여 이를 점화식으로 세워야한다. 라고 간단히 말하지만, 이과정까지 3시간이 걸렸다ㅎㅎ.. 어제 3시간동안 풀다가 계속 틀리길래 포기했지만, 오늘 한번더 확인해보고, 나머지를 제대로 해주지 않은걸 발견하고 맞췄다. 너무 뿌듯하다. 처음에는 예제의 문제처럼 2개만 선택하는 경우만 구하는건 줄 알고 골드인데 왜이렇게 쉽지 하면서 풀다가 K개를 선택하라는 걸 보고 급 생각에 빠졌다. 그럼 그렇지. 쉬울리가 없지.지금은 코드도 다시 개선하여 점화식으로 간단히 표현했지만, 그 과정까지는 너무 돌아서 접근한거같다.원으로 표현하여, 규칙을 발견하고, 점화식을 찾고... 너.......

원문보기 내부링크
Naver Blog

교수님 저는 취업할래요 - 백준 18221 - swift

https://www.acmicpc.net/problem/18221재밌는 간단한 구현문제이다. 문제의 설명중 도입부분이 웃겼다.대부분 대학생 3,4학년이라면 공감할만한 내용이였다 ㅎ 문제접근은 간단하다.선생님과 성규의 거리가 5이상이면서, ( 좌표평면위의 두개의좌표사이의 거리인데, 문제에 구하는 방법이나와있다) 선생님과 성규가 직사각형을 이루면서 그 직사각형안에 학생들이 3명이상이면된다.여기서 구현해야할것은좌표평면위의 두개의좌표사이의 거리를 얻는방법과,선생님과 성규의 좌표를 통해 직사각형을 만드는 방법이다. 직사각형만 만들면, 그 직사각형안에서 순회하며 학생들인지만 탐색하면 된다. 직사각형만드는 방법은 간단하다.선.......

원문보기 내부링크
Naver Blog

숫자판 점프 - 백준 2210 - swift

https://www.acmicpc.net/problem/2210간단히 완전탐색하면 된다. 완전탐색은 제일 시간이 오래걸리는 방법중 하나기 때문에 다른 좋은 방법이 있을지부터 떠올리는게 좋은 것 같다.하지만 완전탐색아니고서 수많은 경우의수를 뽑을 수 있는 방법이 떠오르지 않았다.배열도 5X5로 정해져있고, 25배열은 충분히 작고, 한칸마다 모든방향을 탐색하는건 충분할 것 같아서 DFS로 풀었다.또한 무수히 많이 생성된 숫자들을 유니크하게 판별하기위해 Set을 사용했다. 코드

원문보기 내부링크
Naver Blog

회전하는 큐 - 백준 1021 - swift

https://www.acmicpc.net/problem/1021주어진 순환큐를 이용하여 최솟값을 찾는다. 이렇게 왔다갔다하면서 가장최소비용을 출력하는건 탐욕적으로 해결하는 문제가 많은데, 이문제도 나름 탐욕적으로 풀었다.뽑아야하는 원소들은 순서가 정해져있기 때문에, 첫번째부터 최소한의연산으로 뽑을 수 있을지 선택하면 된다.문제가 원하는 것은 2,3번의 연산값이기 때문에, 뽑는 1번의연산은 0이다. 그러므로 뽑아야하는 원소가 왼쪽에서 적은지 오른쪽에서 적은지를 판별하면된다. 예를들어 3개의 원소중 2번째원소를 뽑으려고한다면, 왼쪽에서는 1번의연산,오른쪽에서는 2번의연산이 필요하다.이둘중에서 연산이 작은걸 선택하여, 그에 맞는 큐.......

원문보기 내부링크
Naver Blog

가장 큰 증가 부분 수열 - 백준 11055 - swift

https://www.acmicpc.net/problem/11055증가부분수열의 길이가 아닌 합이다. 가장 긴 증가부분수열의 길이만 구했었는데, 이 문제는 증가부분수열중 가장 합이 큰 놈을 찾는거다.그래서 증가부분수열의 길이를 구하는 빠른 알고리즘은 통하지 않는다.처음에는 재귀함수로 구현했는데 시간초과나서 다시 생각했다.처음부터 하나씩 증가부분수열을 손으로 만들면서 보니까 각 위치마다 증가부분수열을 만들면 되겠다고 생각들었다.즉 위의 예제를 보면 앞에서부터 증가부분수열을 다 저장해둔다.11 1001 2 1 2 501 2 50 60 1 2 3 1 2 3 51 2 3 5 61 2 3 5 6 71 2 3 5 6 7 8추가하는 방법은 지금까지 저장해둔 증가부분수열들을 모두 탐.......

원문보기 내부링크
Naver Blog

촌수계산 - 백준 2644 - swift

https://www.acmicpc.net/problem/2644간단한 그래프 탐색문제이다. 촌수라는 것은 그래프의 노드와 노드의 간선의 개수를 의미하게된다. 또한 다행이 부모는 최대 한명이여서 큰 복잡함을 고민할 필요없다. 위의 예제를 그래프로 그려보면 아래와 같은 그래프가 나온다.즉 7번노드에서 3번노드까지 간선의 개수를 새면된다. 즉 7번노드를 시작으로하여 방문처리를 하면서 3번노드를 발견하면 종료하고 지나온 간선의 개수를 출력하면 된다.4,6,5노드처럼 동떨어져있는 그래프도 있을 수 있으므로 7번노드에서 5번노드의 촌수를 구하라고 하면 연결간선이 없으므로 -1을 출력한다. 코드 - BFS bfs안에서 removeFirst와 removeLast를 쓸.......

원문보기 내부링크
Naver Blog

비전공자를 위한 이해할 수 있는 IT지식

2020.11.02 ~ 2020.11.05 느낀점 흐릿하게 대충 알고 있던 지식들을 좀 더 자세히 알게되어 좋았다.이책은 특정 개발 직군에 대해 설명하지 않고, 대표적인 서버,클라이언트 개발자 직군들에 대해 설명하고, 더 나누면, 서버, 웹, 앱 개발자로 나누어서 전체적인 관점(기획자)에서 설명해준다. 이렇게 전체적인 관점에서 볼 수 있어서 자세하진 않더라도 크게크게 어떻게 돌아가는지 알 수 있어서 좋았다. 특히나 앱디자인 하는분들께 추천드리고 싶다.어떤 디자인을 바꾸고 싶은데, 서버한테 말해야할지, 클라이언트 개발자에게 말해야할지 매번 모르는 상황에서 이 책은 도움이 될거라고 생각한다.다만 어느정도 개발을 하신 분.......

원문보기 내부링크
Naver Blog

기지국 설치 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/12979언뜻보면 이진탐색같다 N이 최대 2억이라는 점과 이런 비슷한 문제들은 이진탐색으로 풀었었다. 물론 시간만 많이 주어진다면 이진탐색으로도 풀리겠지만, 이 문제는 효율성도 있기때문에 틀린다.하지만 이진탐색으로 만들고 풀다보면은 이진탐색이 필요없겠다라는 생각이 든다. 기지국의 개수를 이진탐색으로 정해줄 필요가 전혀없다. 한번의 계산으로 기지국 개수를 알 수 있다. 간단히 원리는 기지국의 범위는 (2*w) + 1 이된다. 즉 기지국의 범위를 최대한 붙여서 설치하면 이게 답이 된다. 1부터 N까지안에서 기지국들을 최대한으로 설치하면된다. 그 안에서 적절히 기.......

원문보기 내부링크
Naver Blog

스티커 모으기(2) - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/12971풀기전에는 이 문제의 난이도를 몰랐다. 하지만 풀면서 이 난이도는 Level 4란걸 직감했다. 2시간동안 겨우 풀었다. 이 문제도 충분히 풀 수 있는 문제라고 생각한다. Level4 라고해서 겁내지말자! 완전탐색해야한다. 처음에는 재귀함수를 사용하여 DP로 풀다가 효율성측면에서는 다 틀려서 더 빠르게 풀 수 있는 방법을 생각했다. 그렇게 고민하다가 이론적으로는 말로 설명을 잘 못하겠는데, 머릿속으로는 for문을 한번만 돌면은 가능할 거 같다고 생각이 들었다. 그전에 1개부터 7개까지 연결된 스티커를 생각해보면, ( 다각형으로 생각하면 이해가 된다 ) 스티커가5개,6개.......

원문보기 내부링크
Naver Blog

단어 변환 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/43163모든 경우의 수를 돌아보자 완전탐색한 이유는 완전탐색보다 더 좋은 알고리즘이 생각나지 않았기 때문이다. 이런문제는 완전탐색보다 더 빠르게 끝낼 수 있는 그리디또는 DP가 생각났지만 그렇게해서는 어떻게 구현할지 감이안온다. 그리디는 어떤 특정한 순서나, 특정한 조건이 있어야하고, 완전탐색하지 않아야하는데, 일단 어떤 특정한 조건은 보인다."words안에 있는 단어안에서 현재알파벳과 다른 부분이 1개인 경우에만 변경이 가능하다." 하지만 이 조건으로만 탐색한다고해서 "이 경우가 무조건 짧은 단계이니?" 라는 물음에는 동의할 수 없었다.......

원문보기 내부링크
Naver Blog

디스크컨트롤러 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/42627" 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리합니다. " 위문장이 엄청 중요합니다. 그전에 분류가 되야하는데 우선순위는 처리시간이 가장 짧은애들로 sort하되, 처리시간이 같다면 요청시간이 작은 애들로 sort해야합니다. 이것만 생각해내셨다면 그다음 관건이 위의 문장입니다. 예를 들어보면 어떤 작업을 처리했습니다. 그래서 현재 시간은 3입니다. 나머지 작업들은 [2,6], [4,3] 남았습니다. 이 작업들을 앞서말씀드린 sort를 한다면, [4,3] [2,6] 이 됩니다. 하지만 [4,3]을 처리하게된다면 위의 문장을 위배됩니다. .......

원문보기 내부링크
Naver Blog

톱니바퀴 - 백준 14891 - swift

https://www.acmicpc.net/problem/14891착실한 구현문제다어떤 지시를 줄테니 마지막 결과를 출력하라는 문제로, 문제의 동작을 이해하는 것이 가장 중요하고, 이해한 바탕으로 잘 구현해야한다. 이러한 문제는 꼼꼼하게 문제를 잘 보고, 동작원리를 잘 이해하고 이를 코드로 잘 구현해야한다.이문제의 키포인트는 특정톱니바퀴를 기준으로 좌우톱니바퀴의 결과를 구현할 수 있냐인 것 같다.또한 특정톱니바퀴와 좌우 톱니바퀴를 비교할때 비교하는 톱니의 번호가달라진다는 점도 중요하다. 예를들어 3번톱니바퀴와 4번톱니바퀴는 3번톱니바퀴의 2번톱니와 4번톱니바퀴의 6번톱니와 비교해야하고,3번톱니바퀴와 2번톱니바퀴는 3번톱니바.......

원문보기 내부링크
Naver Blog

단어수학 - 백준 1339 - swift

https://www.acmicpc.net/problem/1339역시 그리디는 어렵다 그리디는 정말 많이 접하면서 감을 길러야하는 것 같아요.저는 그리디로 접근했지만 계속 틀려서 다른사람의 해설을 보고 풀었습니다.저의 그리디 접근은 가장 큰값에 있는 알파벳부터 큰값을 지정해줬는데, 이 경우는 예제들은 다 맞지만, 반례가 있습니다.ABC , D , D 이런경우는 D에 C보다 높은 값을 줘야하는데 이부분을 해결하지 못하구요.BC, AA 인 경우도 A에 높은 값을 줘야하는데 순서가 없으므로 해결하지 못해요. 여기서 조금만 더 고민했으면 됐는데 저는 모르겠더라구요.다른사람의 해설은 이렇습니다.해당 위치의 알파벳을 수로 변환하면 10ᴺ 이됩니다. .......

원문보기 내부링크
Naver Blog

순위 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/49191모두 탐색하면서 이기고 지는걸 갱신해주자. 이 문제를 쉽게 푸는 방법은 플로이드워셜 이라는 알고리즘을 사용하면 간단하게 풀립니다.하지만 저는 잘 이해를 못했습니다. ㅠㅠ 플로이드워셜은 모든노드에서 모든노드로 가는 최단거리정보를 구하는 방법인데요,간단히 말하면 다익스트라 알고리즘을 N(모든노드)번 한다고 생각하시면 되요. 그렇다면 이문제는 다익스트라를 N번돌려서 풀수도 있다는 말이겠죠.다만 이 문제는 가중치가 모두 1이기때문에 다익스트라로 구현안하고 단순 bfs로도 풀 수 있죠. 플로이드워셜은 뭔가 과정을 함축하고 결과만 띡! 나오는 듯해서 제.......

원문보기 내부링크
Naver Blog

RGB거리 - 백준 1149 - swift

https://www.acmicpc.net/problem/1149오 어떻게 풀어야하지? 문제를 이해하고 바로 어떤식으로 접근하겠다고 떠오르지 않는 문제들은 처음에 당황스럽다. 이 문제도 그랬지만, 몇개 손으로 적어보니 쉬운 문제였다. 값이 작은 애들부터 골라내면 되겠다. 26부터 가능한 경우들을 다 돌아본다. ( 26-60-13, 26-60-99, 26-57-13, 26-57-89 ) 그다음 40에서부터 가능한 경우들을 돌아본다. 이때, 40-49, 40-57 가 가능하다. 뭔가 겹치는게 보인다. 처음에 26으로 시작했을때도, 26-60, 26-57 이였다. 분홍색이 겹친다. 즉 26,40 에서 57과의 합이 작은애들부터 더해나가면 된다. 즉 이문제는 전형적인 DP문제다. 나는 처음에 재.......

원문보기 내부링크
Naver Blog

음식물피하기 - 백준 1743 - swift

https://www.acmicpc.net/problem/1743간단한 전형적인 bfs 문제이다. 지문의 핵심은 인접한 가장큰 음식물 쓰레기를 구하는 것입니다. 이런 문제들을 접하다보면, 인접하면서 붙어있는 음식물쓰레기들이 여러개의 그룹으로 있다는걸 미리 알 수 있어요. ( 문제의 예시도 그렇습니다. )(음식물쓰레기는 1, 아닌것은 0 으로 2차원배열을 만듭니다 ) 그래서 2차원배열을 순회하면서, 음식물쓰레기가 나오면 bfs를 돌려줍니다.그래서 인접한 음식물쓰레기들을 0으로 바꿔주고, count를 샙니다. bfs가 끝난다면, 아직 2차원배열의 순회가 끝나지 않았다면 이제 다음 음식물쓰레기들을 찾아나겠죠, 이전에 탐색한 음식물쓰레기들은 0으로 바.......

원문보기 내부링크
Naver Blog

수열과 쿼리 38 - 백준 18917 - swift

https://www.acmicpc.net/problem/18917손으로 몇개 해보면 된다. 지문에서는 배열을 사용하면서 쿼리 예시를 설명한다.추가하는건 O(1)이므로 쉽지만 특정 번호를 삭제하는건 O(n)이 걸리므로 시간이 많이 잡아먹는다는걸 느껴야한다. ( 한번만 삭제하는거는 감수할 수 있지만 삭제횟수가 많다면 큰 부담이 됩니다 ) 합이야 금방 배열이 필요없다는걸 알게된다. XOR은 손으로 몇개 해보면 마찬가지로 XOR도 배열이 필요없다는걸 알게된다. 저도 이문제에서 XOR이 뭔지몰라서 찾아보고 풀었습니다.숫자를 2진수로 나타내면 0또는 1로 바꿀 수 있고, 두 수를 XOR한다는 것은 2진수로 바꾼 두 수의 값들이 다른경우 1로 나타냅니다.2는.......

원문보기 내부링크
Naver Blog

멀리 뛰기 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/12914DP를 이용하여 푼다. DP는 바텀업 방식과 탑다운 방법이 있는데, 아직은 탑다운 방식으로 푸는게 더 편하다.탑다운은 위에서 아래로 , 즉 재귀함수로 이미 끝을 확인한후 아래로 내려가는 방식이고,바텀업방식은 처음부터 끝가지 가는 방식이다. 탑다운 방식의 단점은 재귀함수의 깊이가 너무 깊어지면 에러가 난다. 바텀업 방식이 더 빠르다. DP를 이용할 수 있는 이유는 손으로 몇개 해보면 반복되는걸 알 수 있다.탑다운방식으로 생각해보면, 현재의 몇칸인지에 따라 성공할 수 있는지 없는지를 알 수 있다. 1또는 2를 추가하며 재귀함수를 진행하는데, 마지막이 n과 일.......

원문보기 내부링크
Naver Blog

올바른괄호의 개수 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/12929다른분의 추천으로 난이도를 확인하지 않고 풀었는데, 난이도가 4였네요. 프로그래머스 난이도가 4라고 해서 겁먹고 안푸는적이 많은데, 정말 어려운 문제도 있지만, 생각보다 풀리는 문제도 많다라는걸 다시금 깨달았습니다. 우선 올바른 괄호인지 판단해야한다. 이 문자열이 올바른 괄호인지를 확인하는 문제는 많아서 한번 이런 문제의 유형을 겪고, 접근법을 안다면, 이 문제도 쉽게 풀리는 문제입니다. 일단 올바른 괄호인지를 판단하는 방법은 쉽습니다. (, ) 에 따라 sum 에 +,- 하는것입니다. ( 이 나온다면 + 1 , ) 이나온다면 - 1 만약 sum이 음수면 이 경우는 절대.......

원문보기 내부링크
Naver Blog

N-Queen - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/12952완전탐색이지만 거를건 거르자! 예전에 덜컥 이문제를 접했다가 멘탈이 와르르르 부서졌었다. 너무 어려웠고, 해답을 이해하고서도 어려웠다. 초반에는 이제 쫌 풀어봤으니 자만심에 차서 시간복잡도를 생각하며 "아니 이걸 언제다 완전탐색하고있어?? 너무 오래걸리잖아!! " 하며 짜증냈었다. 시간이 좀 흘러 복습할 겸 다시 풀어봤다. 물론 전보다는 덜 어렵다. 이해한대로 풀 수 있었다. 이 문제는 기존과는 다른 유형의 문제라고 생각한다. 이런걸 백트래킹? 가지치기? 라고 부르는 것 같은데, 간단히 말하면 완전탐색을 하면서 이길은 아니다 싶으면 진행.......

원문보기 내부링크
Naver Blog

미친로봇 - 백준 1405 - swift

https://www.acmicpc.net/problem/1405완전히 탐색해야한다. 주어진 예시는 동서남북이 모두 동일한 확률이지만, 다른 예시에서는 동서남북이 모두 동일할 확률이 없을거다.그러면 각각 동서남북에 따른 길들은 모두 다른확률일것이다. 그러므로 첫지점에서 시작하여 모든 길의 경우의 확률을 구해야한다. 기존에 방문한곳을 방문하면 안되면서 빠른시간안에 구해야한다. 나는 그래프탐색문제들은 거의 너비우선탐색을 사용하곤 했다. 이 문제도 너비우선탐색으로 푸는데 시간초과가 난다.왜냐하면 방문한곳을 방문하면안되기에, visit배열을 큐에 담았기 때문이다.각각 흩어지는 길들은 각 고유의 방문배열이 필요했기 때문이다. 이.......

원문보기 내부링크
Naver Blog

다음웹툰앱 상단 구현해보기 - iOS

어떤 부분을 구현할껀가요? 다음웹툰에 TableView또는 CollectionView 위에 이미지가 멋지게 줄어들고 사라지는 걸 볼 수 있다. 줄어드는 이미지를 구현해보도록 할거다. 다들 개발자라면 다음웹툰을 볼때마다 어떻게 구현했을까 한번쯤 생각하지 않았을까? 마음같아선 페이지를 넘길때마다 왼쪽상단 무늬가 변경되는것도 구현하고싶다.ㅎㅎ.. 결과물 나름 비슷하게 만들어보았다. 나는 나름 만족한다.구현해보자 ( 구현하기까지 여러 시행착오가 있었으며, 나름 고민했습니다.. )( 그리고 오로지 코드로만 구현하겠습니다. ) 구현하는 방법은 여러가지가 있겠지만, 나는 다음과 같이 구현했다. 하단은 UICollectionView이며, .......

원문보기 내부링크
Naver Blog

네이버웹툰앱 상단 구현하기 - iOS

구현하고자 하는 화면 다음웹툰처럼 비슷하다.하지만 네이버웹툰은 상단의 NavigationBar가 위아래로 움직인다! 멋있다.. 이 navigationBar가 움직이도록 구현해보겠다. 결과 완벽하다고 할순 없지만 나름 만족한다. 구현해보자 일단, navigationBar를 제외한 CollectionView 와 상단헤더뷰의 구현방법은 아래에 설명해놓았다. 이번 게시글에는 navigationBar의 움직임을 구현하도록 하겠다. https://blog.naver.com/gustn3964/222127992060마찬가지로 비슷하다! 하단은 UICollectionView를 사용했고, 상단은 customUIView를 사용했다.didScroll할때 navigationBar를 조절하면된다! 하지만... navigationBar 변경하지말래.......

원문보기 내부링크
Naver Blog

네이버 블로그앱 상단 구현하기 - iOS

구현할 화면 네이버웹툰,다음웹툰을 구현하고 네이버블로그 앱도 유심히 봤다.비슷하긴한데, 다른점이 상단 헤더뷰에 여러 정보관련된 뷰가 많다. - 제목, 아이디, 홈편집..등등 하지만 스크롤을하면 아래서부터 안보이게된다. 신기하다 그래서 이걸 최대한 닮게 구현해볼 것이다. 결과 나름 열심히 구현해봤다..구현하기 하단은 이전 게시글처럼 하단에 CollectionView로 구현하였고, 상단은 cusomUIView로 구현하였다.상단과 하단이 매끄럽게 스크롤하는 구현은 아래글에 설명해놓았다. https://blog.naver.com/gustn3964/222127992060나는 생각끝에 customUIView - ImageView 에 정보관련된 View들을 감싸는 StackView를.......

원문보기 내부링크
Naver Blog

멀티탭 스케쥴링 - 백준 1700 - swift

https://www.acmicpc.net/problem/1700그리디하게 풀어야 한다는 생각이 떠올라야한다. N과 K가 100이하여서 생각보다 작아보이지만 완전탐색으로는 시간초과다.N이 90 이고, K가 100이면, 90^10으로 어후.. 문제의 답은 최소를 원하니, 그리디하게 풀수밖에 없을 것 같다.가장 나중에 사용될 용품을 빼라니? 하지만 내가 생각한 답은 예제는 맞지만 27%에서 계속 틀렸다. 잘 모르겠어서 다른분들껄 참고했는데 이해가 안가더라.접근방법 1. 콘센트에 자리가 남아있으면 꽂는다.2. 콘센트에 이미 똑같은 용품이 있다면 pass한다.3. 콘센트에 자리가 남아있지 않다면 나중에 사용되지 않을 용품 또는 가장 나중에 사용될 용.......

원문보기 내부링크
Naver Blog

간단하게 xib 파일 사용해보자 - iOS

스토리보드에서만 뷰를 만들고 그안에서 꾸미고 했었는데,따로 xib파일로 만들어서 사용하는 분들을 봤다. 분리해서 사용할 수 있기에 장점이 많은건 느꼈지만, 매번 사용할때마다 뭐가 안되고 어쩌고,, 해서 잘 안돼서 두려운 친구였다. 이번에 맘 잡고 다시 공부해봤다. 하나하나 다른점을 파악하고 어떤 부분에서 어떤게 쓰이는지만 잘 눈여겨보면 구조를 이해할 수 있다. xib , nib 이란? xibs와 nib은 엄연히 다르다. xib은 XML파일이고, nibs은 배치가능한 파일이다. xib을 앱에 사용하기 위해서는 반드시 nib에 컴파일되어야한다. 여러사람들과 협업을 할때, 하나의 스토리보드로 사용하면 merge 충돌이 너무나 힘든작업이기 때문에, .......

원문보기 내부링크
Naver Blog

공항 - 백준 10775 - swift

https://www.acmicpc.net/problem/10775문제가 잘 이해가 안됐다. 문제이해만 몇십분 해먹었다. " 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다 " 예제1을 보면 3번째줄 4는 1~4 번 게이트중 하나에 도킹하면된다.4번째,5번째줄 1은 1~1번 게이트중 하나에 도킹하면된다.그냥 큰 값부터 도킹해주면 되는거아니야? 라고 쉽게 생각하고, 골드1인데 이렇게 쉬울리가 있나, 싶어서 코드를 작성하는 순간 바로 막혔다 역시 이렇게 쉬울리가 없지큰 값부터 도킹해주고, 도킹이 되어있다면, -1값하며 찾아나간다. 큰 값부터 찾는건 이문제의 핵심이 맞다. 하지.......

원문보기 내부링크
Naver Blog

가장 먼 노드 - 프로그래머스 - swift

https://programmers.co.kr/learn/courses/30/lessons/491891로부터 가장 먼 노드들의 개수를 찾으면 된다. 여기서 가장 먼노드들은 이리저리 왔다갔다해서 가장 거리가 먼게 아니라, 최단경로중에서 가장 먼노드여야 한다.최단경로를 이용하면 된다.단 비용은 동일하게 1이므로, bfs로 풀어도 된다. swift는 큐 자료구조가 없기 때문에, removeFirst()는 백준같은 문제에서는 시간초과가 날 가능성이 많다. ( removeFirst는 시간복잡도가 n이기 때문이다. ) 프로그래머스는 swift를 이해해주는지, removeFirst()를 사용해도 시간초과가 거의 안난다.백준같은 문제에서 시간초과가 난다면 따로 큐를 구현하거나, 그와 비슷한 성능을내는 함.......

원문보기 내부링크
Naver Blog

내리막길 - 백준 1520 - swift

https://www.acmicpc.net/problem/1520간단한 bfs 문제아닌가? 조건은 현재위치보다 낮은 곳으로만 이동할 수 있으니 완전탐색하면 되는거아닌가? 했지만~ 시간초과났다. 이로인해 완전탐색보다 더 빠른 방법이 필요하다.다시보니 DP이군! 여러개의 경로를 구하는 것이기 때문에, 분명 겹치는 경로가 발생할 것으로 생각되었다. 그러므로 겹치는 경로는 이미 한번 판단했으므로, DP를 이용하여 다시는 계산하지 않도록 하면 답이 될거라고 생각했다. 그렇게 DP로 구하는 bfs로 변경했다. 하지만 틀렸다! 만약 낮은곳으로 갔는데 , 이 경우가 답이 아닌경우는? 이거에 대한 조건을 걸지 않아서 틀렸다.기존코드는 0또는 + 값만으로 취급했.......

원문보기 내부링크
Naver Blog

알아봐요동물의숲 처럼 만들어보기 - iOS

어떤 부분을 만들어볼건가요? 제가만든 앱은 아니지만, iOS앱에서 유명하신 분들이 만든 - 알아봐요동물의숲 어플이있습니다. 간단한 아이디를 만들고서 가장 첫화면이 이런 컬렉션뷰화면인데, 저렇게 캐릭터들이 레이아웃에서 삐져나온게 그렇게 이쁘더라구요. 그래서 저렇게 비슷하게 만들어보고 싶었습니다. 결과물 나름 비슷하게 만들어봤습니다 ㅎㅎ저 어플이 나온지 좀 됐는데, 그때 당시에도 이 어플을 다운받아서 볼때 어떻게 만들었을까???라는 생각만하고 끝이였는데 이번엔 만들어봤습니다. 완전 똑같지 않지만, 일단 삐져나오게 할 수 있도록 구현한게 마음에 듭니다. 준비물 UICollectionView를 사용했구요, 각 item을 나.......

원문보기 내부링크
Naver Blog

보물섬 - 백준 2589 - swift

https://www.acmicpc.net/problem/2589이거이거 쉽구만 가장 긴 지름 구하면 되는거아니야? 예제1처럼 육지가 두개의덩어리로 이루어진경우도 있기 때문에, 육지덩어리 별로 가장 긴 지름을 구한다. 긴지름을 구하는 방법은 어디서든 시작하여, 가장 먼노드를 찾고, 그 노드로 시작하여 가장 먼노드를 찾는다.라고 단단히 착각하여 풀었지만 틀렸다 ㅎ완전탐색이 필요하다 가장긴지름을 구하는거라면 나의 코드에서는 틀림이 없다고 생각했고, 뭐가 틀린건지 모르겠어서 질문글들을 보았다. 거기서 이런 반례를 주었다. 나의코드는 9를 나타냈고, 답은 10이었다.아래의 두곳을 찾아야 답이된다. 하지만 가장긴지름으로는 찾을 수 없.......

원문보기 내부링크
Naver Blog

3진법 뒤집기 - 월간코드챌린지시즌1 - swift

https://programmers.co.kr/learn/courses/30/lessons/68935N진법으로 나타내는 방법만 알면된다. swift에서는 숫자를 N진법으로 나타내는 String 타입의 이니셜라이저가 있습니다. String(_, radix:)_(value) 은 BinaryInteger 프로토콜을 따르는 타입이여야합니다.또한, N진법으로 나타낸 값을 숫자로 변경하는 Int 타입의 이니셜라이저가 있습니다.Int(_, radix:) _(value) 은 StringProtocol 프로토콜을 따르는 타입이여야합니다.코드 3진법으로 바꾼후, reversed한다음 String타입으로 변경후, 다시 원래값으로 돌려주면 됩니다.

원문보기 내부링크
Naver Blog

지형이동 - Summer/Winter Coding2019 - swift

https://programmers.co.kr/learn/courses/30/lessons/62050문제 어렵습니다. 못풀고 다른분의 해설을 참고하여 풀었습니다.2시간 걸렸네요 ㅠㅠ 큰 숲(MST)을 볼 수 있어야합니다. 물론 저도 큰 숲을 보지 못했습니다.ㅎ이 문구를 통해 최소스패닝트리(MST)가 떠올라야합니다.저도 MST까지는 떠올랐지만, 어떻게 MST를 활용할 수 있는지.. 몰랐습니다.* MST는 모든 경로를 연결하면서 최소의 비용을 구하는 문제에서 아주 유용합니다.모든 경로를 사다리가 필요없는 그룹으로 압축할 수 있다. 저희는 마지막에 MST를 활용할건데, 그러기 위해서는 준비단계가 필요합니다.우선 모든 경로를 그룹으로 압축할 수 있습니다.그룹의.......

원문보기 내부링크
Naver Blog

쿼드트리 - 백준 1992 - swift

https://www.acmicpc.net/problem/1992재귀함수로 구현하면 된다. 이와 비슷한 문제 풀면 쉽게 풀린다. 기저사례는 배열을 순회하며 다른 값이 없는 경우이고,다른 값이 있는 경우 4방면으로 분할하여 재귀함수 반복한다. 코드

원문보기 내부링크
Naver Blog

치즈 - 백준 2636 - swift

https://www.acmicpc.net/problem/2636바깥치즈와 구멍을 어떻게 찾는담? 바깥치즈를 찾는 방법은 알겠는데, 그안의 구멍은 어떻게 구현할까 계속 생각하다가 약간 시간이 걸리지만서도 간단한 구현으로 답을 찾는 방법이 떠올랐다. 구멍을 찾을 필요가 없다. 구멍을 찾지말고, 치즈를 발견하면 bfs를통해 판의 가장자리에 닿기만 하면, 이 치즈는 1시간뒤에 사라질 치즈다. 이 치즈들의 위치를 배열에 추가하고, 배열에 담긴 치즈들의 위치를 0 으로 바꿔준다. 그리고 남은 치즈들의 개수를 샌다. 위의 과정을 치즈가 0이될때까지 반복한다. 나름 재밌었던 문제다 35분 걸렸다. 코드

원문보기 내부링크
Naver Blog

넷플릭스 - 규칙없음

2020.10.09 ~ 2020.10.25개발관련 책을 제외하고 오랜만에 책을 읽었다. 다 읽고 나서.. 이 책은 겉으로는 넷플릭스의 문화를 설명하지만, 사람이 어떻게 되어야하는지를 이해할 수 있었다. 아무리 뛰어난 사람이여도 완벽하지 않으며, 계속해서 개선해나간다. 무결점인 완벽한사람이 대단한사람이 아니라 개선하고 발전해나가는 사람이야말로 대단한사람인 것 같다.자신에게 불리한, 쓴 소리를 흘려듣지 않고 받아들이고 개선해나갈 수 있어야한다.개발자라는 분야는 끊임없이 공부를 해야하는 분야인데, 비단 개발자뿐만 아니라 사람은 끊임없이 자기계발해 나가야만 자신이 상상하던 사람이 될 수 있다. 규칙과 절차가 중요한 곳이 있고.......

원문보기 내부링크
Naver Blog

압축 - 백준 1662 - swift

https://www.acmicpc.net/problem/16622시간동안 못풀고 재귀함수또는 스택으로 구현해서 풀라는데 감은 오는데 못풀다가 다음날 멀쩡한 머리로 풀었다 ( 확실히 고민하는 일정시간을 넘어가면 잘 안풀리는데, 다시 시작하는 마음으로 다음날 풀면 풀린다. ) (, ) 의 위치가 중요합니다. ( , ) 위치를 통해 어떻게 한묶음으로 나타내며 어떤 애들이 감싸는 애들인지 판단할 수 있습니다. 단순히 주어진 예제로 보면 맨앞- ( 맨뒤 - ) 로 한덩어리씩 판단하면 될 것 같지만, 이런 경우는 통하지가 않습니다.그러므로 앞에서부터 판단해야합니다. 두번째 예제는 답이 24 입니다. 앞에서부터 순회하는데, ) 이 나온다면, 무조건 그.......

원문보기 내부링크
Naver Blog

용액 - 백준 2467 - swift

https://www.acmicpc.net/problem/2467양끝을 줄여나가면 될 것 같은데.. 처음드는 생각은 양끝이 가장 작지 않을까, 했지만, -99 , 99, 1000, 1002 인경우는 어림도없다 그럼 양수인경우만 생각해봤다. 오름차순으로 주어지기 때문에 당연히 왼쪽 2개가 답이겠다.그럼 음수인경우만 생각해봤다. 역시나 당연히 오른쪽 2개가 답이겠다.그럼 음수,양수 다 들어있는경우는? 문제들을 경험해보면 ,앞서 말한 조건들을 부합되도록 문제를 내지 않는다. 즉 답을 도출하기위해 각각의 조건들에 맞춰 귀찮게 코드를 작성하도록 문제를 내지 않는다는 말이다.( 물론, 문제의 지문그대로 잘 살펴보며 구현하는 문제는 예외다. ) 간단한 원리로 구.......

원문보기 내부링크
Naver Blog

동전 0 - 백준 11047 - swift

https://www.acmicpc.net/problem/11047그리디의 기본 문제 다음동전들이 이전동전의 각 배수이므로, 탐욕적으로 풀 수 있다. 각 배수가 아닌경우는 DP나 다른방법으로 풀어야한다. 코드

원문보기 내부링크
Naver Blog

간단하게 ContainerView 추가하기 - storyboard , 코드

스토리보드로 추가하기 스토리보드로 추가하는 건 너무나 간단합니다. Label을 추가하는것 만큼 쉽다랄까요. + 버튼이나, Command + Shift + L 을 눌러서 Container View 를 넣어줍니다.그러면 자연스럽게 밑에처럼 viewcontroller옆에 작은 네모난친구(ViewController)가 새로 나타납니다.그 사이로 segue로 연결되어있습니다.즉, ContainerView안에서는 새로나타난 ViewController가 보이게 됩니다. 같은 stroyboard 안에 있는 다른 ViewController로 변경해도 가능합니다. 기존에 새로생긴 ViewController를 삭제하고, ContainerView에서 control + 드래그 하여 다른 뷰컨트롤러에 갖다댑니다. Embed를 클릭합니다. 그.......

원문보기 내부링크
1 2