1. 문제 [1차]셔틀버스 2. 핵심 아이디어 구현 3. 코드 4. 풀이 과정 뭔가 특별한 알고리즘을 써야하나 싶어서 문제를 시간을 들여 좀 자세히 봤는데, 딱히 떠오르지 않았다. 또한 주어진 데이터의 크기가 작았기 때문에 구현으로 문제를 풀어도 충분하다고 생각이 들었다. 중요한 포인트는 다음과 같다. 마지막 버스에 사람들이 다 차있는지 확인하기 위해 시뮬레이션 형태로 버스마다 탑승하는 사람들을 빼주었다. 그리고 마지막으로 탑승한 사람의 idx는 대기열에 있는 사람의 수가 된다. 이를 이용하여 경우에 따라 다르게 답을 산출했다. 5. 다른 사람의 코드 프로그래머스에 있는 다른사람의 풀이인데, 사용이 신기해서 가져와봤다. prefix는 접두사 suffix는 접미사 라는 의미인데, paramater에 숫자n을 넣으면 prefix는 앞에서부터 n 만큼, suffix는 뒤에서부터 n만큼 원소를 가져온다. 비단 String 뿐만 아니라 Array에서도 사용가능하다. 이거는 C나 C…

언제 2023년 1월 9일 ~ 3월 18일 어디서 온라인 (코테 2회) 오프라인 aT 센터 1차 코테 문제는 총 5개 였다. 알고리즘 4 SQL 1 1번: 그리디. 프로그래머스 LV2 2번: 완전 탐색. 프로그래머스 LV3 3번: 그리디. 프로그래머스 LV2 4번: 완전 탐색. 프로그래머스 LV3 5번: SQL. 분기처리 특수한 명령어? 나는 알고리즘 문제를 확실하게는 1번을 풀었다. 2번 3번은 테스트 케이스는 맞췄는데, 복기해보니 틀렸던 것 같다. SQL은 잘모르겠다. 분기처리와 특수한 명령어를 써서 풀었어야 했던 것 같다. 코테를 본 후 나는 아직 코테 실력이 부족하다고 느꼈다.유사한 문제를 풀어봐서 어떻게 풀어야할지 대충 알고 있었는데, 실제 구현에서 시간이 너무 많이 걸렸다. 그래서 2번 3번 문제를 제대로 풀지 못했다. 그래서 탈락하지 않을까 생각했는데, 시험 도중 서버오류가 있어서 1차는 모두가 코테에 합격했다…!! (천운이였던듯) 2차 코테 문제는 1차 코테와 같이 …

1. 문제 고득점 Kit 겹치는 선분의 길이 2. 핵심 아이디어 3. 코드 4. 풀이 과정 처음에는 이렇게 생각했다. 선분의 총 길이를 구해서 0으로 배열을 초기화 한 후, 해당 배열에 주어진 선분들의 길이에 해당하는 위치에 += 1 씩 해줘서 2 이상인 위치의 개수를 구하면 되지 않을까? 대략 이런식이다. 그런데 이렇게 하면 resultLine 배열의 길이도 다시 맞춰주거나, 동적으로 맞춰주지 않고 제한사항에 맞게 resultLine을 200 (선분의 길이는 -100 ~ 100)을 맞춰줘야하는데, 전자는 번거롭고 후자는 낭비라고 생각해서 다른 방법을 택했다. 간단하게 ~= 연산자를 사용하여 바꿨는데, 훨씬 간결하고 빠르게 answer을 찾을 수 있다. 그런데 현재 이 코드로는 답이 2배가 되었다. 왜인가 하니 라인이 [[0, 2], [-3, -1], [-2, 1]] 으로 주어질 때 해당 위치에서 한번 더 체킹이 되기 때문이였다. 사실은 선분이 끝나는 점의 한칸 전에서 이미 …

1. 문제 고득점 Kit 방의 개수 2. 핵심 아이디어 3. 코드 4. 풀이 과정 우선 문제를 보고 다음과 같이 생각했다. 대각선의 움직임을 나타내기 위해서 좌표계를 2배로 그리는 것은 아이템 줍기 문제에서 아이디어를 떠올렸다. 대각선을 표시하는 이유는 다음과 같다. | 그림에서처럼 네모안에 하나의 대각선이 가로질러 2개의 방이 있는 상태를 가정해보자. | 그 다음 대각선을 다른 대각선이 가로지르는 경우, 좌표계에서 따로 표시할 수 없으므로 해당 대각선에서 교차한다는 사실을 알기 어렵다. 하지만 좌표계를 2배로 만든다면, 대각선의 중간에 노드가 생겨서 쉽게 대각선의 교차를 확인할 수 있다. 그 다음 방이 만들어지는 조건은 이다. 때문에 현재 노드와 방문할 다음 노드 두개 모두 필요하고, 이 둘의 경로를 추적하는 것이 필요하다. (중복되는 경로로 방의 개수가 중복 카운팅 되는 것을 막기 위함) 그리고 이러한 아이디어를 종합해서 코드를 짜면 된다. (이틀 걸림ㅋㅋ) 코드에서 P…

개요 알고리즘 문제를 풀던 도중.. Array와 Set을 사용했을때 많은 시간차이가 발생하는 것을 발견했다. 그 이유는 무엇일까. 간단한 실험을 통해서 얼마나 속도가 차이나는지 알아보고 이유 또한 알아보자. 실험 우선 실험에 사용할 유용한 조수를 소개한다. 코드를 클로저로 받아서 사용할 수 있는 아주 좋은 녀석이다. 코드는 이곳에서 가져왔다. 그 다음 Array와 Set에 원소 추가, 순회, 삭제를 테스트했다. 1만번 기준 속도의 차이는 다음과 같다. 순회가 속도 차이는 가장 크지만, 기준 속도의 차이 떄문에 추가가 값의 차이가 가장 많이난다. 실로 어마어마한 차이이다.. 왜 이런 차이가 나는 것일까? 이유 우선 Array와 Set의 가장 큰 차이는 이다. 코드를 보자. 보다시피 Array와 Set에 똑같은 순서로 삽입을 했지만, Array는 순차적으로 제거된 반면 Set은 랜덤하게 삭제되었다. 이러한 차이의 이유를 Array와 Set의 원소 추가, 순회, 삭제 메소드에서 살펴보자…

1. 문제 고득점 Kit 가장 먼 노드 2. 핵심 아이디어 3. 코드 4. 풀이 과정 가장 멀리있는 노드가 몇개인지 구하는 문제인데, 처음에는 쉽다고 생각했다. 우선 처음에 문제를 풀떄 연결된 점을 그래프로 만들어 BFS로 탐색하려고 했다. 하지만 이렇게 풀면 graph 자체가 매우 클때 graph 하나의 라인을 n 만큼 계속 반복해줘야하기 떄문에 시간 복잡도가 커져서 문제에 통과할 수 없다. 해답은 그래프를 연결된 간선으로만 만들어서 탐색하는 것이였다. 해당 풀이는 이곳을 참고하였다. 그런데 이 풀이에서는 중복값을 제거하기위해 Node를 담는 배열에 Set을 사용하였다 했는데, 사실은 isVisited 배열이 중복을 체킹해주고 있어서 중복값이 들어갈일은 없다. Set Array 다만 시간초에서 유의미한 차이가 발생해서 Set 과 Array의 iteration 속도를 한번 실험으로 측정해봤다. Array와 Set의 속도 차이 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀…

1. 문제 고득점 Kit 징검다리 2. 핵심 아이디어 3. 코드 4. 풀이 과정 입국심사 문제와 동일하게 이분탐색 문제이다. 다만 조금 더 응용해서 이분탐색을 사용해야했다. 이분탐색을 할 때 탐색할 값과 조건을 정하는게 가장 중요한데, 징검다리에서는 와 를 사용해야했다. 두개의 돌 사이의 거리를 탐색값으로 정해서 해당 값보다 작다면 바위를 제거한다고 생각을 하고 시뮬레이션을 하는 아이디어였다. 이러한 아이디어를 떠올리는게 가장 키포인트 였는데, 나는 떠올리지 못해서 검색을 통해 알게되었다. 이곳에서 자세하고 쉽게 풀이를 해주셨다. 두개의 이분탐색 문제를 보니 이제 중요한 부분이 뭔지알것 같다. 중요한것은 과 을 하는 것이다. 그런데 그런 아이디어를 떠올리고 곧바로 코드로 풀어내려면 좀 문제를 많이 접하는게 중요할듯하다. 연습을 통한 경험의 필요성을 다시금 느낀다..! 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

ScreenTime API WWDC21 에서 ScreenTime API 가 처음으로 등장했다. Meet the Screen Time API ScreenTime API 는 요약하자면 사용자의 Device (아이들) 내부의 앱 실행을 제어하는데 사용할 수 있는 API 이다. 그 후 WWDC22 에서 조금 기능이 추가되고 확장되었다. 원래 아이들의 Device를 제어하는 것에 한정된 Family Controls가 개인의 Device를 제어할 수 있도록 기능이 확장되었고, Device Activity로 사용자가 사용한 앱들의 정보를 불러올 수 있게 되었다. 이번 포스팅에서는 Device Activity를 이용하여 사용자가 사용한 앱들의 정보를 불러오는 방법에 대해서 소개하겠다. 기본 셋팅 Device Activity에 사용되는 view는 SwiftUI로 구성되어있다. SwiftUI로 프로젝트를 만들어주자. 프로젝트를 만든 후 family controls에 대한 권한을 추가해야한다. Ta…

1. 문제 고득점 Kit 입국심사 2. 핵심 아이디어 3. 코드 4. 풀이 과정 우선 이분탐색을 어떻게 해야할지 감이 안잡혀서 검색을 통해 풀이를 봤다. 이곳에서 잘 정리해주셨는데, 핵심은 전체 소요시간을 하여 탐색하는 것이였다. 코드에 있듯이 최소, 최대로 심사 시간을 정해놓고 그 중간의 시간부터 탐색을 시작한다. 그리고 현재 탐색하는 총 심사시간(mid)을 각각의 심사시간(t)로 나눠서 심사할 수 있는 인원의 수(total)를 판단한다. 심사할 수 있는 인원의 수가 n 을 넘으면 탐색하는 총 심사시간을 줄인다. 반대로 n을 넘지 못한다면 총 심사시간을 늘인다. 이분탐색을 어렴풋이 알고있어서 문제를 못풀기도 했고, 하는 아이디어가 떠오르지 않았다. 이렇게 쓰는거구나 대충 알았으니 이제 비슷한 문제는 잘풀 수 있지않을까 생각한다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 퍼즐 조각 채우기 2. 핵심 아이디어 3. 코드 4. 풀이 과정 정말 어려웠고 시간이 많이 소요된 문제이다..! 하나씩 정리하며 되짚어 보자. 전체적인 코드 흐름 우선 퍼즐을 맞추는 문제는 이전에 한번 풀어본적이 있어서, 퍼즐 조각의 4가지 형태 (90º 씩 회전한 형태)를 비교해서 퍼즐을 맞춰야한다는 아이디어를 생각해냈다. 그리고 이 퍼즐조각을 나타내는 형태는 좌표계들의 집합으로 설정하였고. game_board, table 을 BFS로 탐색하여 퍼즐 조각을 추출해냈다. 코드의 make table pices 부분에서 보면 table 에 있는 퍼즐 조각들을 먼저 추출해서 담았다. 이를 사용해서 game_board의 빈칸에 하나씩 비교하며 채워넣어 줄 것이다. 보드에서 퍼즐 조각을 추출하는 코드는 makePuzzlePice 함수가 담당하였다. 그리고 나서 game_board를 탐색하며 빈 퍼즐 조각을 추출하며 보드판을 채워주었다. 코드의 matching …

1. 문제 고득점 Kit 아이템 줍기 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 처음에는 조금 무식한 방법을 생각했다. 그림으로 표현하자면 이렇다. 이처럼 현재 x 와 이전 x 를 비교하며 좌표계에 다시 경로를 표시하는 느낌으로 코드를 작성하려 했는데, 너무 비효율적이고 구현의 복잡도가 올라갔다. 또한 엣지 케이스 또한 대응하기가 어려웠다. 이 그림과 같은 모양으로 꺾인 경로가 있다면, 2차원 배열로 나타냈을 떄 잘못된 경로로 탐색을 할 수 있다 (우측 배열) 이런 경우를 대응하지 못해서 인터넷에서 다른 방법을 찾아봤다. 이곳에서 풀이를 봤는데, 주요한 해결 방법은 다음과 같았다. 1번은 내가 뻘짓한게 무색할정도로 쉬운 해결 방법이였다ㅜ 난 뭘한걸까 2번은 보니까 아하! 했다. 이런 방법이 있구나..! 천재인가 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 타겟 넘버 2. 핵심 아이디어 3. 코드 [DFS] [BFS] EffectiveQueue 이 코드는 이곳 에서 작성된 코드입니다. LinkedQueue 이 코드는 이곳 에서 작성된 코드입니다. DoubleStackQueue 이 코드는 이곳 에서 작성된 코드입니다. 4. 풀이 과정 간단하게 숫자들을 DFS/BFS 로 탐색하는 코드를 구현하면 되는 문제였다. 나는 BFS로 문제를 먼저 풀었는데 시간초과가 났다..! 그리고 나서 DFS로 풀었는데, 시간초과가 나지 않았다. 이상해서 왜인지 찾아봤는데.. 이 명령어 때문이였다. !!!! 나만 이 명령어 O(1)인줄 알고 있었나.. 무튼 다른 방식으로 구현된 queue를 사용해서 실행해보니 통과했다. 내가 써본 queue는 , , 인데 각각의 시간 효율이 달랐다. EffectiveQueue DoubleStackQueue LinkedQueue EffectiveQueue > LinkedQueue > Doub…

들어가면서 Swift 는 open source 입니다. 아주 접근이 쉬운 혜자 언어죠. 이 오픈소스 코드를 웹상에서 뜯어보려면.. 정말 엄청 힘들고 사실상 불가능에 가깝다. 특정한 자료구조, 기능이 궁금한데 하나의 메소드 안에서 다른 여러 메소들이 중첩으로 사용되고 있고.. 여러 프로토콜을 준수하고.. 프로토콜 메소드도 사용하고.. 이걸 정말 하나하나 웹상에서 찾아가면서 혹은 로컬에서 해당 swift 파일을 열어서 뜯어보기란 불가능하다. 그래서 이번 포스트에서 Swift 를 빌드하여 xcode로 열어 뜯어볼 수 있는 방법을 소개하고자 한다. Swift 빌드 macOS 기준 셋팅 방법임! 다른 OS 는 이곳 가이드를 참조해야함. Swift 는 여러 OS, Architecture 를 지원하고 있다. 그리고 여러 환경에 맞춰 빌드를 할 수 있도록 빌드 스크립트를 제공해준다. 다만 빌드에 필요한 Swift의 Dependency와 컴파일 툴은 직접 설치해야한다. 하나씩 해보자! 준비물 …

1. 문제 고득점 Kit 여행경로 2. 핵심 아이디어 3. 코드 4. 풀이 과정 탐색문제인데, 특이하게 알파벳 사전순으로 정렬된 경로를 출력해야한다. 다음과 같이 코드 플로우를 생각하였다. 이렇게 풀었고, 테스트 케이스도 무난히 통과하길래 정답인줄 알았다. 그런데 테스트 케이스 1번 에서 실패했다. (2,3,4 모두 통과) 이유가 뭔가 보니, 나는 항공권으로 갈 수 있는 경로를 나타낸 2차원 배열을 [[Bool]] 로 사용해서 썼는데, 이 때 경로가 같은 항공권이 여러개 중복으로 있을경우, 해당 상황을 나타내지 못해서 실패하는 것이였다. 그래서 해당 2차원 배열을 [[Int]]로 바꾸면 항공권이 중복으로 존재하는 경우 숫자로 표현이 가능하다. 이렇게 바꿔서 문제를 통과했다! 는 문제의 상황과 맞지 않는 알고리즘이라 생각해서 따로 구현하지 않았다. 여행 순서를 이미 정렬로 어느정도 정했는데 BFS 로 탐색하여 루트를 찾는 것은 비효율적이다. 찾긴 찾겠지만.. 오래 걸릴 것이다.…

1. 문제 고득점 Kit 단어 변환 2. 핵심 아이디어 3. 코드 [DFS] [BFS] 4. 풀이 과정 다음과 같이 풀면 되겠다고 생각했다. 우선 DFS로의 구현이 쉬울 것 같아서 먼저 구현했고, 다음에 BFS로 구현했다. 성능은 큰 차이 없을 것 같다. 최소 cnt를 조건으로 비교하는 조건은 두 방법 모두 있기 때문에, 결국 최소 cnt 를 찾기위해서 탐색하는 양은 비슷하다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

언제 2023년 2월 6일 어디서 서울 강남구 역삼역 근처 어떻게 면접은 크게 3부분 나눠져서 이루어졌다. 1. 스몰토크 간단하게 자기소개를 해주셨다. 지원자만 자기소개를 하는줄 알았는데, 면접관 분들이 먼저 해주셔서 조금 편하게 자기소개를 할 수 있었다. (면접관은 총 3분이셨다!) 그 다음 내가 자기소개를 한 것을 바탕으로 스몰토크를 했었는데, 나는 자기소개에서 취미가 수영과 헬스라고 소개했었다. 그래서 수영에 대해서 물어봐주셨고 수영에 대해 이런저런 이야기를 나눴다. 모임에 대해서도 이야기 했는데, 나는 모임이 좋고 즐긴다고 답했다. (모각코, 보드게임, 번개 등등) 그리고 주량과 좋아하는 술을 물어보셨는데, 모임과 노는것을 즐긴다고 느낄 수 있었다. 이렇게 간단한 스몰토크를 한 후 공통질문으로 넘어갔다! 면접관분들이 분위기를 많이 풀어주시고 재미있게 이야기 해주셔서 긴장을 많이 풀 수 있었다. 🙏 2. 공통질문 지원동기 1. 매쉬업을 지원하게 된 동기가 무엇인지? 매쉬업의 …

1. 문제 고득점 Kit 게임 맵 최단거리 2. 핵심 아이디어 3. 코드 [swift] [python] 4. 풀이 과정 흔히 보던 BFS/DFS 탐색 문제였다! 로 아직 탐색하지 않은 경로 (maps[dx][dy] == 1 인 경우) 와 벽을 피해주면서 탐색하면 되었다. 그렇게 쉽게 문제를 푼 다음, DFS로도 문제를 풀어보려 했었는데… 로는 문제가 풀리지 않았다. [python] 이 DFS 코드가 실패하는 이유는 탐색하는 경로가 너무나 많아지기 때문이다. 이런 형태의 맵이 있다고 가정한다면, DFS는 교차로 (위, 오른쪽, 아래쪽) 를 모두 3^n * k (n는 삼거리의 개수, k는 삼거리의 경로 개수) 연산으로 탐색을 해야하기 때문에… 시간복잡도가 망하는 것이였다. 이처럼 문제에서 최단 거리를 제공한다면 (마지막 종착지가 정해져있고 가중치가 없음) BFS가 확실히 좋은 선택이다 라고 느꼈다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 네트워크 2. 핵심 아이디어 3. 코드 [DFS] [BFS] 4. 풀이 과정 문제를 보고 다음과 같이 생각했다. 이 문제를 푼 기억이 희미하게 있었다.. 아마 예전에 한번 풀었어서 쉽게 풀이가 떠오른 것 같다. 해당 플로우로 코드를 작성하였다! 처음에는 DFS로 구현을 하였고 BFS로도 구현 해보았다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 도둑질 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 우선 DFS 로 생각을 하면, 모든 경우를 탐색하는 경우를 찾기 위해서는 찾거나 찾지 않거나 두가지의 경우를 생각하면 된다. 그런데 한집을 털면 인접한 두 집은 털 수 없으니 다음과 같이 생각하고 점화식을 세울 수 있다. dp[i] = max(dp[i-1], dp[i-2] + money[i]) 뭔가 어디서 본듯한 점화식을 세우고 나서 보면, 집이 원형 으로 줄 세워져있다는 조건을 처리해줘야하는데, 이 두가지 조건은 양립할 수 없으므로, 두가지의 경우 모두 따로 점화식을 사용하여 값을 구해주면 된다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 등굣길 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 처음엔 DFS로 여러 경로를 탐색하면 바로 풀 수 있지 않나? 생각을 했다. 이 생각을 바탕으로 코드를 작성하였는데.. 시원하게~ 시간초과가 먹혔다. 이것도 바로 이전에 풀었던 정수삼각형 과 비슷한 점화식으로 풀어야하는 문제였다. 으로만 방향이동이 가능하기 때문에, dp[i][j] = dp[i-1][j] + dp[i][j-1] 새로 값을 넣을 칸 = 바로 위칸까지의 경로수 + 바로 왼쪽칸 까지의 경로수 이 점화식이 성립하는거였다. 나는 왜 바로 알아차리지 못했을까..! 🥲 이곳을 참고해서 알게되었다.. 덧붙여 프로그래머스 문제들 swift 지원을 왜이렇게 안하는걸까… 3개에 하나꼴로 지원을 안하는 느낌이다. 😿 주절주절… 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 정수 삼각형 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 간단하게 DFS 로 거쳐간 숫자를 탐색 후 업데이트 하면 되지 않을까 생각을 했는데.. DFS로 풀었더니 시간초과가 났다. 조금 성능을 개선해보기 위해서 0으로 초기화 된 Visit 배열을 만들어, DFS 로 탐색을 할 때 한번 더 조건을 걸어 탐색하는 코드를 작성해봤다. 하지만 여전히 효율성 테스트는 통과하지 못했다..ㅜ 이곳 을 참고하여 답을 봤는데, 이라는게 이때 사용되는거구나 알게되었다. 확실히 문제를 많이 풀어야 어떻게 풀지 좀 감을 잡을 수 있을 것 같다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit N으로 표현 2. 핵심 아이디어 3. 코드 [DFS] [BruteForce] 4. 풀이 과정 처음 문제를 풀때, 카테고리가 DP 라는 타이틀을 달고있어서 점화식을 찾아야겠다 라며 머리를 싸맸는데… 결국 못찾아서 인터넷에서 답을 봤다. 이곳을 봤는데.. 알고보니 점화식이 아니라 DFS BFS 를 이용한 완전탐색을 통해 문제를 풀었어야 했다. DFS 를 이용한 코드는 피로도 에서 나온 DFS와 상당히 유사하다. 똑같이 depth 를 확인하는데, N으로 표현은 최소 depth를 찾아야하고 피로도는 최대 depth를 찾아야하는 문제였다. 똑같은 DFS이지만 알고리즘이 조금 다른 방식으로도 문제를 푼 곳도 있었다. (이곳) 차이점은 stack을 이용하고, 조금 더 정밀한 조건을 줘서 조금 더 탐색 시간을 단축시키는 것에 있었다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 단속카메라 2. 핵심 아이디어 3. 코드 4. 풀이 과정 일단.. 문제를 완전히 잘못 생각했다. 나는 이 문제가 정점 2개가 주어지고, 해당 정점들에 단속 카메라를 설치해나가는 것인줄 알았는데… 주어진 배열은 그게아니라 구간 을 나타낸 것이였다. 그래서 원래 쓰던 풀이를 지우고, 다시 생각해봤는데 잘 풀리지가 않았다. 문제를 잘못 이해했다는 것에 멘탈이 나가버린걸까.. 머리가 안돌아갔다. 그래서 이곳 을 참조하였고 아주 간결한 풀이에 넋이 나갔다. 이 코드가 내가 생각했던 풀이와 가상 유사했는데, 그보다 간결한 풀이가 있었다… 진출지점을 정렬하고, 진입지점 보다 작은지 확인하고 count를 늘리고, 카메라의 위치를 갱신한다 어떻게 이런 생각을 바로 떠올릴 수 있을까. 나는 노력하는 수 밖에 없는 것 같다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 섬 연결하기 2. 핵심 아이디어 3. 코드 4. 풀이 과정 결론은 다익스트라 같은 알고리즘을 쓰면 될 것 같은데? 라는 생각을 가지게 되었고, 찾아봤는데.. 이라는 비슷하면서 많이 다른 알고리즘이 이 문제 풀이에 더 맞다는 것을 알게되었다. 크루스칼 알고리즘 이란? 크루스칼 알고리즘은 를 찾기위해 고안된 알고리즘이다. 이 알고리즘에서는 과 가 활용된다. 최소 신장 트리 우선 란 이 두가지 조건을 만족하는 그래프이다. 이와 같이 모든 정점이 연결되어 있고 가중치가 있는 그래프가 있다면 이렇게 4가지의 신장 트리가 만들어질 수 있다. 이중에 는 간선의 가중치의 합이 가장 적은 4번째 신장 트리이다. 구현 크루스칼 알고리즘에서는 먼저 한 후, 정렬된 순서대로 간선을 추가한다. 간선을 추가하는 과정에서 가 활용되는데, 서로 중복되지 않는 집합을 표현하기 위해 사용된다. 구체적인 동작 과정은 이곳을 참고하면된다. 구현의 핵심 아이디어는 요약하자면 최…

1. 문제 고득점 Kit 구명보트 2. 핵심 아이디어 3. 코드 [swift] [python] 4. 풀이 과정 처음 문제를 보고 다음과 같이 생각했다. 여기까지 잘 생각을 하고, 구현을 하는데… 문득 다른 생각이 떠올랐다. 가장 큰 몸무게와 합하여 limit과 가장 가까운 몸무게를 찾아야하지 않나? 예컨데 이런 것이다. limit이 100kg이고, 사람들이 80kg, 20kg, 10kg 이 있으면, 80kg 과 20kg 의 사람을 쌍으로 보트에 타야 가장 많이 보트를 태울 수 있지 않는가? 그러나 이는 틀린 것이다. 서로 증감이 반대이기 때문에, 항상 최대의 짝을 지을 수 있는 경우는 최대와 최소 몸무게가 짝이 되었을 때이다. 앞선 예제에서 80 + 20 으로 짝을 짓는 것은 20 보다 작은 몸무게를 제치고 선택을 하는 것인데, 이렇게 선택을 해도 큰 의미가 없다. 왜냐하면 그 다음 최대 몸무게는 같거나 감소 하고 앞서 제쳐져 남아있는 최소 몸무게는 이미 그전 최대 몸무게와 조…

1. 문제 고득점 Kit 큰 수 만들기 2. 핵심 아이디어 3. 코드 4. 풀이 과정 처음의 생각은 다음과 같이 생각했다. 제거할 개수말고 뽑을 개수를 기반으로 조합해서, DFS 로 모든 경우를 탐색하는 방법으로 문제를 풀려고 했다. [DFS] 탐색을 일직선으로 (방문을 시작한 숫자의 전 숫자를 방문하지 않도록) 이렇게 visited 의 방문을 로만 설정하여서 구현하였다. 그런데 이 방법은 시간초과가 되었다ㅜ 다른 방법으로 큐를 이용하여 BFS를 사용해서 풀어봤다. 그런데 모든 경우를 탐색하는 건 DFS BFS 모두 똑같아서, 여전히 시간초과였다. 어떻게 풀어야할지 감이 안잡혀서 이곳 을 참고하였다. DFS를 풀고난 후 비슷한 생각을 했었는데, 라고 잘못생각하여 이 풀이까지 도달을 못했었다.🥲 매번 반복문의 실행마다 배열의 앞순서에 있는 숫자와 비교가 일어나고, 제거할 수 있는 카운트만큼 교체가 될 것이기 때문에 로 비교할 필요가 없었다. 그리디 어렵다.. 문제의 상황에 대…

1. 문제 고득점 Kit Hello 조이스틱 2. 핵심 아이디어 3. 코드 4. 풀이 과정 쉬운 문제인줄 알았는데.. 생각보다 훨씬 어려웠다. 처음의 생각은 이랬다. 여기서 조이스틱의 이동을 코드로 작성하는 과정에서, 좌측 우측을 반복문으로 탐색하고 최소 값을 가지는 길을 선택하면 된다고 생각했다.. 그런데 알고보니 지금까지 왔던 길을 다시 되돌아 가는 것이 빠른 길일때가 있었다. 이 경우를 어떻게 처리할지 감이 안잡혀 이곳을 참고하여 코드를 작성하였다. 핵심은 index 0 인 자리에서 앞 뒤로 갔을 때를 계산하여, 가장 빠른 경우 모두 찾아주는 것이였다. 어렵다 어려워..! 5. 다른 사람의 코드 내가 참고한 코드인데, 아주 깔끔하다..!👍 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드

1. 문제 고득점 Kit 모음사전 2. 핵심 아이디어 “ 3. 코드 4. 풀이 과정 어떻게 풀어야할지 한 30분정도 고민을 했는데, 도무지 방법이 떠오르지 않아서, 다른 사람의 풀이를 참고했다. 내가 참고한 곳은 이곳 이다. 여기서는 DFS를 멈추는 flag가 설정되어 있지 않아서, 조금 리팩토링 해서 코드를 작성했다. 답을 보면 단순한데, 문제를 풀때는 AAAAA -> AAAAE -> AAAAI -> … -> E -> EE 이런식으로 사전이 형성되는것이 DFS의 재귀로 만들 수 있다는 것을 떠올리기가 힘들었다. 가 이 풀이의 핵심 키였다. 5. 다른 사람의 코드 다른 글자로 변경될 떄 필요한 자릿수마다의 코스트를 미리 저장해서 더해주는 방법이 있었다. 그런데 AAAAA -> EAAAA 로 변경될 떄 코스트를 어떻게 알아낸걸까? 이를 파악하기가 실전에서는 조금 어려울 것 같다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드

1. 문제 고득점 Kit 체육복 2. 핵심 아이디어 3. 코드 4. 풀이 과정 문제를 보고 다음과 같이 생각했다. 이를 바탕으로 코드의 흐름을 짜봤다. 이렇게 해서 문제가 잘 풀릴줄 알았건만…! 계속 실패가 떠서 뭐가 잘못되었나 봤더니, 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다. 이걸 안보고 풀다가 실패가 계속 뜬것..! 그래서 dict 을 만드는 반복문에 코드를 추가하여, 잃어버린 체육복을 돌려줬다. 문제 조건을 잘 보자! 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 전력망을 둘로 나누기 2. 핵심 아이디어 3. 코드 [BFS] [DFS] 4. 풀이 과정 문제를 보고 다음과 같이 생각하고, 구해야할 것을 생각했다. 그래서 생각했던 방식대로 전선을 끊고, 끊은 전선대로 graph를 만들어서 사용하였다. 첫번째로 그래프를 탐색을 위해 사용한 방식은 인데, 스택을 사용하여 첫번째 타워에 연결된 노드의 개수를 구한 후, 전체 개수에 빼줬다. 이는 문제에서 송전탑이 전선을 통해 형태를 이루고 있기 때문에 가능한 방식이였다. 두번쨰로는 으로 재귀를 통해 구현하였다. 구현이 익숙치 않아, 조금 많이 버벅 거리고 코드가 깔끔하지 않다고 느꼈다. 하단에 다른 사람이 구현한 DFS 코드를 보고 아직 한참 멀었구나 느꼈다..! BFS DFS 나의 코드에서는 BFS 가 조금 더 좋은 성능을 보여줬다. 구현하기도 비교적 편하고, 더 익숙해서 그런지 코드를 읽기도 편한 느낌이다. 나는 완전탐색에서는 BFS 가 더 좋다..! 5.…

1. 문제 고득점 Kit 피로도 2. 핵심 아이디어 3. 코드 [순열] [DFS] 4. 풀이 과정 처음에는 다음과 같이 생각하여 정리하였다. 필요사항: 우선 시 되는 것: 소모 피로도가 낮은 것. 소모 피로도 1순위, 최소 필요 피로도 2순위로 정렬. 선택을 해나가면서 가능한 던전 탐색. 이런식으로 정렬을 사용해서 문제를 풀면 어떨까 생각을 했었는데, 생각해보니 이렇게 풀면 던전을 방문하는 를 커버할 수가 없어서, 틀리게 된다. 그래서 로 던전에 방문하는 모든 순서를 구해서 탐색하는 것을 생각했고, 해당 코드가 위에 있다. 그런데 이렇게 풀면 모든 경우의 수를 다 탐색을 하는거라 상당히 비효율적 일 것이라 생각했다. 그래서 로 다시 한번 풀어보고 테스트 했다. 순열 DFS 차이가 엄청나다!! 순열은 정말 어쩔 수 없을 때 사용하자.. 그리고 또 하나 발견한 것이 에 관한 것인데, 애가 엄청난 시간을 잡아먹는다는 것을 이번에 발견했다. DFS Enumerated DFS…

1. 문제 고득점 Kit 카펫 2. 핵심 아이디어 3. 코드 [재귀] [stack] 4. 풀이 과정 처음에 문제를 어떻게 풀어야할지 감이 잘 안왔는데, 갈색 타일이 노란색 타일의 테두리 1열을 차지한다 라는 문구에서 힌트를 얻어 규칙을 찾아냈다. 가로, 세로를 늘리는 동작을 반복하여 만족하는 brown, yellow의 갯수를 찾는다. (가로 >= 세로 일때 세로를 늘림) 가로로 늘리는 동작: yellow + 1*(height-2), brown + 2 세로로 늘리는 동작: yellow * n, brown + 2*n 이 규칙을 따라 가로로 타일을 늘려가면서 세로로 늘렸을때 경우를 체킹하면 될 것 같다고 생각하였고, 한번 를 사용하여 문제를 풀어봤다. 그 다음에 시간초 차이가 얼마나 나는지 궁금해서 stack 으로도 한번 풀어봤는데, 결과는 놀라웠다. recursion stack 숫자가 큰 테스트 케이스에서 5배 정도 시간차이가 벌어졌다. 아마도 재귀는 정답을 찾은 후에도 …

1. 문제 고득점 Kit 소수 찾기 2. 핵심 아이디어 3. 코드 4. 풀이 과정 풀이를 다음과 같이 두가지 방법을 생각했다. 그런데 2번 방법은 더 복잡하게 푸는 것 같아서 직관적인 1번 방법으로 코드를 구현하기로 했다. 코드 플로우를 다음과 같이 생각했다. 우선 조합해서 만들어진 수들이 순서가 상관있었기 떄문에 을 사용했다. ex) 17, 71 해당코드는 이곳 에서 확인할 수 있다. 조합으로 만들어진 string 중에 중복되는 string은 거르기 위해 set으로 에 문자열을 넣어가며 중복을 판별하였다. 소수 판별은 isPrime 메소드를 만들어 사용했는데 제곱근을 이용해서 2 씩 n을 늘려가며 소수를 판별하면 $$O(\frac{1}{2}\sqrt{n})$$ 의 시간복잡도를 가진다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 모의고사 2. 핵심 아이디어 3. 코드 4. 풀이 과정 문제를 보고 다음과 같이 생각하였다. 이를 바탕으로 찍는 방식을 answer에 대입하여 정답의 갯수를 확인하는 코드의 플로우는 다음과 같이 구상하였다. 이대로 구현하여 쉽게 문제를 맞혔는데, 다른 사람의 코드를 보고나니 나의 코드에 아쉬운 부분이 있었다. 아래에 다른 사람의 코드를 보면 아주 깔끔하고 우아하게 문제를 해결했다. 5. 다른 사람의 코드 나의 코드와 결정적으로 다른점은 아래와 같았다. 보고 배울점이 많은 코드였다. 특히 dictionary를 이렇게 선언해서 과 같이 접근하는 방식이 생소해서 뭔가 싶었는데, 이건 ‘튜플’ 이였다. 이렇게 데이터 그룹을 임시로 이름을 붙여서 사용하는게 정말 괜찮은 방식이라 느꼈다. 직관성 up. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드

1. 문제 고득점 Kit 2. 핵심 아이디어 3. 코드 4. 풀이 과정 문제를 이해하는데 시간을 많이 썼고, 구현 방법이 곧바로 떠오르지 않아서 또 헤맸던 문제이다. 현재 답으로 제출한 코드도 문제를 조금 오해해서 작성한 코드인데, 나는 가로 세로 중 최솟값이 지갑들(sizes) 말고 다른 숫자에서 나올 수도 있을 것이라 생각하고 코드를 작성했다. 이는 틀린 것으로, 최대값 최소값 모두 sizes 안에 있는 지갑의 크기에서 산출된다. (당연한건데 왜 이상하게 생각했을까..!) 5. 다른 사람의 코드 깔끔하게 size 중에서 최대값 최소값을 찾고있다. 살짝 재귀적 느낌의 변수가 특이하다. 👍 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드

1. 문제 고득점 Kit H-Index 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 문제를 보고 다음과 같이 생각하였다. h 번이상 인용, h 편 이상 인용 -> 인용된 횟수와 인용된 갯수가 함께 h 이상이여야함. h 번 이하 인용 -> H-Index 의 최대를 구해야하고, H-Index 가 인용횟수 범위를 이상, 이하 모두 포함하기 떄문에 별로 상관 없음 때문에 ‘h 번이상 인용, h 편 이상 인용’ 이 조건에 맞는지 검증을 해야하기 떄문에 다음과 같이 코드의 플로우를 생각했다. max citation 만큼 반복 1부터 검증 내림차순으로 정렬된 citations 에서 h 번 이상 인용된 논문이 몇개인지 확인. 불만족 시 현재까지의 최대 h-index return 그대로 구현하니까 통과할뻔 했는데, 오류가 발생했다. 크래쉬가 날곳이 어딘지 생각해보니 maxCitation을 구하고, 1부터 반복문을 실행하는 구간이였다. maxCitation이 0일 경우 오류가…

1. 문제 고득점 Kit 가장 큰 수 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 우선 문제를 보자 아래와 같은 생각을 했다. 정수를 이어 붙였을 떄 가장 큰수를 구하라 앞자리 수가 가장 큰 수를 붙여서 만든 수 문자로 정렬해놓고 붙이면 되지않나? 그래서 단순하게 문자를 대소 비교해서 정렬 했는데, 제대로 정렬이 되지 않는 상황이 발생했다. 예를들면 “121” 과 “12”, “10” 과 “1” 문자열에서는 이들을 “121” 과 “10” 이 우선되게 정렬을 했다. 그래서 그 다음 든 생각이 ‘문자열 안의 chracter 를 자릿수마다 하나씩 비교하자’ 였는데, 문자열 서로의 길이가 다를 경우, 자릿수를 다시 반복해서 비교해줘야하는 번거롭고 비효율적인 문제가 있었다. 고민고민을 하다 결국 좋은 방법이 떠올랐는데, 하는 것이였다. [swift] 그런데 또 생각해보니 이렇게 하나하나씩 반복문으로 비교할 필요가 없었다. 어차피 합쳤을 떄 큰수 대로 정렬하면 되지 않는가?…

1. 문제 고득점 Kit K번째수 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 문제에서 요구하는대로 코드의 플로우를 다음과 같이 생각했다. commands 1,2 로 배열 슬라이싱 슬라이싱한 배열을 정렬 commands 3 번쨰 원소 정답 배열에 추가 -> 반복 그대로 구현해서 풀었는데, 푸는 과정에서 에 대한 이해를 잘 몰라서 오류가 발생했었다. 이 코드로 처음에 배열을 곧바로 정렬을 해서 인덱싱을 해줬는데, index out of range 오류가 발생했다. 이유는 즉슨 slicedArray 의 index 값이 새로만들어 지지 않기 때문이다. 왜냐하면 는 배열을 새로 만들어 내는게 아니라, 참조해서 만들어지기 때문이다. 또한 원래 배열의 indices 를 공유한다. -> 기존 배열의 idnex 값들이 유지가 됨. 그래서 새롭게 배열을 만들어내는 sorted 는 index 오류가 없었고, sort 는 index 오류가 발생했다. 때문에 그대로 배열을 유지…

1. 문제 고득점 Kit 이중우선순위큐 2. 핵심 아이디어 3. 코드 [swift] 4. 풀이 과정 문제에서 삽입, 최댓값 삭제, 최솟값 삭제 세개의 연산을 반복하기 떄문에, 최소 최대 두개를 만들어 각각 사용을 하면 문제가 풀릴 것 같아서 그대로 구현하였다. 다만 효용이 떨어져 시간초과날 것을 예상했지만 일단 구현 후 개선점을 찾으려 했었는데, 시간초는 문제에서 테스팅을 하지 않았고, 그래서 쉽게 통과를 한 것 같다. 5. 다른 사람의 코드 [swift] 프로그래머스의 다른 사람의 코드를 봤는데, 그냥 배열을 사용해서 푼게 많았다. 테스트케이스 테스팅을 돌려보니 과 큰 차이는 나지 않았다. (미세하게 heap 이 더 빨랐다) 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드

1. 문제 고득점 Kit 디스크 컨트롤러 2. 핵심 아이디어 , (최소 작업 우선 스케줄링) 3. 코드 [swift] [swift] 4. 풀이 과정 처음에는 , 문제인줄 알았다.. 그런데 문제의 요구사항과 제한사항을 만족하는 조건 요청부터 종료까지 걸린 시간의 최소 먼저 요청이 들어온 작업부터 처리 이 두가지를 만족 하려면 와 같은 알고리즘으로, 현재 요청 시간을 만족하고 (작업을 시작할 수 있고) 그 중 가장 빨리 끝나는 작업 을 선택하며 작업을 수행하면 되었다. 그런데 어떤식으로 처리할지 감이 안잡혀 블로그 글을 참고했다. 그렇게 해서 위와 같이 을 사용한 코드를 작성했는데, programmers 에서는 분류가 으로 되어있어서 heap 으로 다시 풀어봤다. heap sort 그런데 sortedJobs 와 tempJobs 에 각각 append 하는 방식 때문인지, 시간이 오히려 더 걸렸다. tempJobs 를 없애고 구현을 할수도 있을 것 같은데… 한번 고민을 다시…

1. 문제 고득점 Kit 더 맵게 2. 핵심 아이디어 을 이용한 3. 코드 [python] 코드 출처 4. 풀이 과정 [python] 플로우를 다음과 같이 생각했다. 힙을 이용한 를 잘몰라서 시간초과 날 것을 예상했지만, 을 사용해 일단 풀었다. 역시나 시간초과였고, 블로그를 참고하기로 했다. 알고리즘 보고 어떤 것인지 대충 이해를 했는데, 한번 Swift 로 heap 을 이용해 우선순위 큐를 구현해봐야겠다고 생각했다. 일단 파이썬은 다른사람의 코드를 적었는데, 해당 코드를 바탕으로 Swift 로 heap을 이용해 우선순위큐를 구현해보기로 했다. [swift] heap 과 priorityQueue 의 구현은 를 참고히였다. 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정

1. 문제 고득점 Kit 기능개발 2. 핵심 아이디어 와 비슷한 동작을 하는 반복문. 3. 코드 4. 풀이 과정 풀이의 플로우를 한번 생각을 해본 다음 문제를 풀었다. 그런데 애초에 프로그래머스에서 분류가 스택/큐 라고 딱 정해져 있으니, ‘해당 플로우에서 어떤 알고리즘을 이용해서 풀어야할까?’ 라는 물음 없이 스택/큐로 풀어야겠다 라는 생각이 그냥 들어서 코드 작성 전 알고리즘 플로우를 구상하는 연습을 조금 아쉽게 했다. 백준으로 넘어가면 이제 어떤 알고리즘으로 문제를 풀어야할지 생각을 하는 연습이 되지않을까 생각한다. 코드에서도 적혀있듯이 progress + speed 를 반복해서 더해준다. 첫번쨰 작업이 완료되었다면 그 다음 작업도 확인해준다. 완료된 작업을 answer 배열에 추가해준다. 이렇게 플로우를 생각하고, 구현하면서 필요한 변수를 그떄마다 추가했다. 변수를 미리 정하는건 특별한 자료구조를 사용해야할때 필요한 작업일듯 하다. 그냥 구현하는거면 코드를 작성하면서 생각…

1. 문제 고득점 Kit 주식가격 2. 핵심 아이디어 를 이용한 반복문. , 를 사용하여 배열 슬라이싱. 주의: endIndex 는 실제 사용할 수 있는 Index + 1 을 반환함 그래서 와 같이 쓰라는데, 왜 이렇게 구현되었을까? 음.. 3. 코드 Python Swift Swift 에는 파이썬의 가 없어서 , 를 이용하여 배열 슬라이싱을 했다. 4. 풀이 과정 일단 해당 문제에서 Swift 채점을 지원하지 않았기 떄문에, 파이썬으로 먼저 구현한 후 Swift 코드로 바꿨다. answer 배열을 미리 만들어 놓고, 주식 가격을 deque 에 차례대로 넣어가며 반복문으로 가격을 검증 & answer 배열에 업데이트 하려고 했는데 해당 방식에서 비효율적인 삽입과 삭제가 일어났고, 시간초과를 초래했다. 그리고 길을 잃어서 어떻게 풀어야할지 감이 안잡혔다.. 그래서 다른 사람의 코드를 참고했다. 참고 코드를 바탕으로 상단의 풀이 코드가 작성되었다. 불필요한 삽입, 삭제 없이…

1. 문제 고득점 Kit 베스트앨범 2. 핵심 아이디어 Dictionary 를 이용한 , . 3. 코드 4. 풀이 과정 문제에서 명확한 문제해결의 흐름을 준다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 이를 그대로 코드의 플로우로 옮긴다면 장르에 속한 노래의 재생횟수를 구한다. 이를 재생횟수의 내림차 순으로 정렬한다. 정렬된 장르의 순서에 따라 가장 많이 재생된 노래를 수록한다. (재생 횟수가 같다면 고유 번호가 낮은 노래 우선) 따라서 필요한 것은 , 이 두가지이다. 이 배열들을 만들때 와 를 사용하였다. 5. 다른 사람의 코드 하나의 dictionary 안에 튜플 형태로 play, music 두개를 두는 것이 인상적이였다. 아주 깔끔한듯! 1. 문제 2. 핵심 아이디어 3. 코드 4. 풀이 과정 5. 다른 사람의 코드