일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- Collection
- JDBC
- design-pattern
- DesignPattern
- 자바
- lambda calculus
- Python
- functional programming
- 스택
- Java
- 디자인패턴
- Eclipse
- Collections
- 겨울카카오인턴
- tcp
- 람다 칼큘러스
- 백준
- solid
- Pattern
- Rails
- exception
- 로버트마틴
- JavaScript
- 프로그래머스
- 함수형 프로그래밍
- javscript
- 파이썬
- 큐
- Spring
- Network
- Today
- Total
목록알고리즘 문제 풀이 (25)
개발자 노트
문제설명 https://programmers.co.kr/learn/courses/30/lessons/64065 카카오답게 문자열 처리하는 문제 예전에 처음 풀었을 땐 문제를 도저히 이해하지 못해서 넘어갔으나... 그 이유는 원소의 개수가 n개이고, **중복되는 원소가 없는** 튜플 `(a1, a2, a3, ..., an)`이 주어질 때(단, a1, a2, ..., an은 자연수), 이는 다음과 같이 집합 기호 '{', '}'를 이용해 표현할 수 있습니다. {{a1}, {a1, a2}, {a1, a2, a3}, {a1, a2, a3, a4}, ... {a1, a2, a3, a4, ..., an}}이렇게 열겨형 정의를 넘어갔기 때문인 것 같다. 이 부분을 잘 보면 튜플의 원소를 ..
문제설명 스택 및 이차원배열을 물어보는 문제 접근 바구니는 단순히 stack만을 이용하면 되고, 이차원 배열에서 뽑을 인형을 잘 두는게 포인트. 이차원 배열도 세로로 스택으로 보기 위해 각열에서 top을 미리 찾은 다음 뽑을 때마다 +1 씩 해주는 방식으로 접근했다. 왜냐하면 아래로 갈 수록 값이 증가하니까.(이 부분에서 디버깅하는데 10분 소요했다. (전체 풀이시간 30분)) 구현 def solution(board, moves): n = len(board) tops = [0 for _ in range(n)] #값이 있는 index for c in range(n): for r in range(n): if board[r][c] != 0: tops[c] = r break answer = 0 basket = ..
문제설명 https://programmers.co.kr/learn/courses/30/lessons/64063 문제 이해하는 것은 쉬운 편이나 어떻게 접근할 것인지 결정하는게 어려운 문제 1번방에 배정받은 사람이 있고 1번 방을 배정받기 원한다면 2번방을 배정해줘야 한다. 2번방에도 사람이 있다면 다음 사람이 없는 방인 3번방으로 배정. 예외도 없다. 방이 모두 5개있고 5번방을 2번 요청하는 경우는 input으로 주어지지 않는다고 적혀있다. 접근 1.UnionFind 딱 UnionFind가 생각나는 문제. 1~3번방에 사람이 있다면 결국 하나의 그룹을 이룬다고 생각할 수 있다. 그 이유는 1) 문제의 목표는 번호 x가 주어질 때 다음 방 배정을 찾는 것이다. 2) 번호가 1,2,3일 때 다음 방 배정은..
문제설명 트라이로 접근하는 것. 전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다. 접근 TRI 이용 완전탐색으로 접근하지 않는 이유 완전탐색으로 접근하면 시간복잡도는 엄청나다. 매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수) 따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다. tri접근시 공간복잡도 고려 0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000..
문제설명 구현문제. rotate는 삼성 기출 중 톱니바퀴라는 문제가 있다. 이를 참고하면 좋을 듯. 총 문제 풀이시간은 2시간 10분으로 접근 방법 정하기 및 절차 작성 => 30분소요 구현 1시간 30분 소요 첫 코드 작성 40분소요 rotate 디버깅 30분 소요(;; 절망적.) 인접 부분 잘못 고려하여 20분 소요 접근 문제의 큰 틀 접근 자체는 크게 어렵지 않아 보였을 것이다. 그나마 포인트가 될 것은 다음과 같다. 1)인접하다 원형을 단순히 테이블로 변형하여 인접을 고려하는데 큰 어려움이 없을 것이다. 다음 부분만 제외하고. i번째 원을 기준으로 1번째의 왼쪽인 M번째 수. M번째의 오른쪽인 1번째 수. 이것이 인접하다는 것만 고려해주면 큰 문제는 없다. 2)원판에 동일한 수가 있다면 삭제하는 ..
문제설명 아주 기초적인 BFS문제. 최단거리를 찾아라. 접근 카카오2020 신입공채 블록이동하기 문제를 풀다가 아주 복잡하게 최단경로 문제를 풀고 있는 것 같아 이 문제를 살펴보았다. 접근1 개별의 이동에 대해 방문정보를 가지고 있어서 모두 탐색하도록 정했다. (1,1)에서 (2,1)이동가능하면 (2,1)노드와 함께 방문정보 (1,1),(2,1)을 que에 넣어준다. (1,1)에서 (1,2)이동가능하면 (2,2)노드와 함께 방문정보 (1,1),(1,2)를 que에 넣어준다. (2,1)과 (1,2)모두 (2,2)이동이 가능하므로 각각의 방문에 (1,1),(2,1),(2,2), (1,1),(1,2),(2,2)를 que에 넣어준다. 굵은 표시에 있는 내용을 보면 '최단거리'를 구하는 문제이므로 ..
문제설명 구현문제이다. 구현문제는 늘 그렇듯 글을 잘 읽는게 중요하다. 접근 M과 N을 보면 시행횟수가 적다. 회전하는 경우까지 포함하면 대략 M*N*4(roate수)가 된다. 완전탐색을 적용하면 편하다. 초기 완전탐색 접근 방법은 이렇다. 접근1. DFS를 통한 완전탐색 매 단계 rotate할 건지 이동할 건지 선택.(이때 이동은 이동을 1칸씩 이동으로 정의) 해당 케이스가 자물쇠를 열 수 없다면 계속 탐색 baseCase는 rotate4번 다 돌았을 때 또는 이동 범위를 벗어났을 때이다. 이를 DFS로 구현한다. 이렇게 하니까 매단계 rotate구현하는게 너무 빡쎘다. 그리고 이렇게 짜면 비효율적이란 감이 들었다. 따라서 rotate 1회전 후 r,c모두 탐색, 2회전후 r,c 모두 탐색으로 접근하려..
문제설명 간단히 말하여 높이가 서로 다른 탑들이 주어졌을 때 탑 꼭대기 왼쪽방향에 해당 탑보다 큰 탑이 존재하면 해당 탑의 번호를(1부터 시작), 없으면 0을 출력한다. 문제를 이해하는데 있어 중요한 내용은 1.탑의 높이는 중복없음. 2.탑의 수는 50만이하 탑의 높이는 1억이하이다. 접근 아이디어가 곧바로 떠오르지 않아 예제를 통해 어떻게 접근할 지 결정하고자 했다. 예제 : 6 9 5 7 4 1.6기준 왼쪽에 탑이 없으므로 0출력 2.9기준 6은 낮으므로 또 0 출력 3.5기준 9가 높으므로 9의 번호인 2번 출력 4.7기준 왼쪽에 있는 5는 낮으나, 9가 만나 2추력 5.4기준 7을 만나 그 번호인 4출력. 위를 봤을 때 관심의 대상이 되는 빌딩기준 왼쪽에 더 큰 빌딩이 있는지 봐야하는데 단계가 지..
문제 설명 간단히 말하여 net의 수를 구하는 문제이다. 이와 유사한 문제는 삼성 코딩테스트, 백준의 컴퓨터 네트워크 수 구하기, 크루스칼 알고리즘 등에서 보이듯, 기본문제이다. 주어진 그래프의 자료형은 인접행렬(2차원 행렬)으로 주어졌고 무방향 그래프이다. 문제 접근 Union Find 한 그래프와 다른 한 그래프의 노드를 비교하여 서로 다른 그래프에 속해있다면 합쳐준다. 같은 그래프에 속해있는지 판단하는 방법은 서로의 루트노드가 같은지 비교하면 된다. BFS,DFS 깊이우선 탐색. 모든 노드에 대해 방문했는지 체크해주는 visited 리스트 or 비트를 구현하고 한 노드에 대해 탐색 후 탐색이 안된 노드를 찾아 탐색해주면 된다. 탐색이 안된 노드를 찾아 탐색하는 횟수가 곧 그래프의 수. 왜냐하면 DF..
문제 설명 오랜만에 구현문제를 접했고, 좀 빡쎘다. ㅎㅎ; 설명한대로 구현하면 되서 100% 구현이라 봐도 무방하다. 문제는 지문 그대로 이해하면 되고, 구현시 주의해야할 사항은 다음과 같다. 1번 말부터 순서대로 이동시킨다.(말의 이동순서가 결과에 영향을 미침) 말의 이동방향이 파란색 or 벽일 경우. 이동 방향을 반대로 한 뒤, 1칸 이동할 때 파란색이면 그대로 멈추기. 빨간색이거나 흰색일 경우 빨간색or흰색일 경우를 그대로 적용! (난 이 부분에서 헤맸다. 말만 그대로 이동시킴.) 문제 접근 접근은 큰 흐름을 고려한 뒤 구체적인 부분을 해결하는 방식으로 접근했다. i)전체적인 흐름 턴의 횟수를 1 증가시킨다. 말을 선택한다. 말의 다음 위치의 타일을 확인한다. 다음 위치의 타일의 색에 맞도록 말을 ..