Skip to content

studying-ice-bear/codingtest-study

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

공부하는 아이스베어 코테스터디

목표

기간

2022.08.08 ~

기록

0808

0815

공휴일에도 스터디하는 사람 성공한대요~

0822

  • 카테고리: 백트랙킹, 동적계획법1
    • 출제 빈도를 고려하여(스터디원 뇌피셜) 기하1과 정수론과 조합론은 스터디에서 진행하지 않기로 함.
    • 의논한 문제
      • N-queen
        • 힌트: 충돌하지 않게 위치시키려면 같은 행 또는 열을 배제해야 하기때문에, 1차원배열에 저장해도 된다(2차원 배열이 없어도 표현 가능하다.)
          • 예를 들어, [0, 2, 3, 1]는 1행 2열, 2행 3열, 3행 1열에 퀸이 위치한다는 의미.
      • 포도주 시식
        • 계단 오르기와 비슷하지만 시작점과 끝점이 없다는 것이 다르다.
        • 해결 못한 반례 (해결했다면 '질문'채널에 설명 남겨주기~)
          답 : 36
          Input:
          10
          0
          0
          10
          0
          5
          10
          0
          0
          1
          10
          
  • 랜덤문제: 스택/큐같은 숫자는 싫어
    • 다들 푼 방식이 비슷하고, 배열이나 큐를 사용해서 풀었다.
    • 프로그래머스에서 파이써닉하게 푼 것도 신기했음
      return  [arr[i] for i in range(len(arr)) if not(arr[i:i+1] == arr[i+1:i+2])]
    • 자바스크립트로 filter를 사용해서 한 줄에 나타낸 코드가 있었음
      return arr.filter((val,index) => val != arr[index+1]);

0829

  • 카테고리: 누적합, 그리디 알고리즘
    • 의논한 문제
      • 나머지 합
        • 힌트: 누적 합의 나머지를 구하고 그 값이 같은 것끼리 그룹을 형성한다. 각 그룹에서 2개를 고르면(조합) 범위가 형성된다. 나머지가 같기 때문에 두 값의 차가 0이라서, 최종적으로 누적합을 M으로 나누면 0이 된다.
  • 랜덤문제: 더 맵게
    • 모두 heapq 사용해서 문제를 풀었다.
    • 우성님이 소개해 준 함수
      • all(iterable): iterable 요소가 모두 참이면 True 반환
      • any(iterable): iterable 요소가 하나라도 참이면 True 반환

0905

0912

  • 추석연휴로 쉬어가기

0919

  • 카테고리: 분할정복, 이분탐색
    • 의논한 문제
      • 랜선 자르기: 각 랜선을 특정 개수로 똑같이 자를 때 최대 길이 구하기
      • 행렬제곱
        • 4시간을 투자한 혜선님의 조언: 나머지를 구하는 문제인데 시간초과를 만났다면 ⭐ 모듈러 연산 ⭐ 사용하기
          1. (a + b) mod n = ((a mod n) + (b mod n)) mod n
          2. (a - b) mod n = ((a mod n) - (b mod n)) mod n
          3. (a * b) mod n = ((a mod n) * (b mod n)) mod n
        • 곱셈이랑 유사하다.
  • 랜덤문제: 완전탐색모음사전

0926

1003

1010

1017

  • 카테고리: 최단경로
    • 혜선님의 최단경로 풀이법: dfs, bfs 처럼 코드에 틀이 있어서, 다익스트라를 공부하면 문제를 풀 수 있습니다! 노스트라다무스
  • 랜덤문제: 이분탐색입국심사
    • 주어진 시간 동안 모든 심사관은 총 몇 명을 심사할 수 있는가를 확인하면서 시간 범위를 줄여나가는 것이 포인트.

1024

  • 카테고리: 투포인터 + 최단경로
  • 랜덤문제: 그래프방의개수
    • 레벨5의 고난이도 문제
      • Screen Shot 2022-10-24 at 9 39 43 PM 풀었으면 반4자2를 얻을 수 있었던 문제..
    • 모래시계 같은 도형도 확인하기 위해서 dx,dy = [0,1,1,1,0,-1,-1,-1],[1,1,0,-1,-1,-1,0,1]를 두번씩 더한다. 1x1를 2x2라고 생각하면 된다.

1031

  • 카테고리: 동적 계획법과 최단거리 역추적
    • 취업준비로 인해 문제를 많이 풀어오지 않아서 앞으로 진행방식을 변경함.

      각자 맡은 문제를 설명하고 다른 방식으로 푼 팀원이 첨언하기.

    • 다음 주에 설명할 문제
      • LCS 2 ➡️ 혜선 / 숨바꼭질 4 ➡️ 유진 / DSLR ➡️ 하영 / 최소비용 구하기 2 ➡️ 혜진 / 플로이드 2 ➡️ 보선
  • 랜덤문제: 해시위장
    • 대부분 수학의 조합 방식으로 풀었다
    • 보선님이 알려준 꿀팁: Javascript의 Map을 iterable하게 접근하는 방법은 for ... of를 사용하는 것이다.
    • 혜선님이 알려준 꿀팁: 기본값을 생성해주는 딕셔너리 자료형 from collections import defaultdict
      • 관련 글 갈무리 (출처: daleseo.com)

        파이썬의 내장 모듈인 collections의 defaultdict 클래스는 이러한 경우 사용하면 딱 인데요. defaultdict 클래스의 생성자로 기본값을 생성해주는 함수를 넘기면, 모든 키에 대해서 값이 없는 경우 자동으로 생성자의 인자로 넘어온 함수를 호출하여 그 결과값으로 설정해줍니다.

1107

  • 카테고리: 동적 계획법과 최단거리 역추적
    • LCS2
      • 2차원 배열에서 문자가 같으면 이전 값과 1을 더해서 저장한다. (가장자리에도 같은 방식으로 값을 넣기 위해서 패딩 값을 넣어준다.)
      • 2차원 배열을 이용해서 역추적을 하여 부분 문자열을 출력한다.
      • LCS 참고 블로그
    • 숨바꼭질4
      • bfs로 -1, 1, *2 인 상황을 모두 접근한다 (위치값을 같이 저장한다)
    • DSLR
      • 프로그래머스 조이스틱과 유사한 문제
      • 방문 사실을 저장하면서 전체를 다 훑어본다.
    • 최소비용 구하기 2
      • 다익스트라 이용
        • 힙을 사용하면 시간복잡도가 작아진다.
    • 플로이드 2

1114

  • 카테고리: 트리
    • 트리의 부모 찾기(11725)
    • 트리의 지름(1967)
      • 첫 노드에서 가장 멀리 떨어져있는 노드를 찾고, 그 노드에서 가장 멀리 떨어져 있는 노드의 거리를 찾으면 그게 트리의 지름이다.
      • 증명이 어려워서 완벽히 이해하지 못했다.
    • 트리 순회(1991)
      • 재귀를 이용하여 전위순회, 중위순회, 후위순회
    • 트리의 순회(2263)
      • 후위순회의 마지막이 항상 루트 노드이고, 중위순회는 루트노드를 중심으로 왼쪽자식트리와 오른쪽자식트리를 구분지을 수 있다. 이때, 자식트리들의 개수를 알아내서 후위순회에서도 왼쪽자식트리의 범위를 구하고 오른쪽자식트리의 범위를 구한다. 각 자식트리의 루트를 구해서 중위순회에서 자식의 자식트리를 구한다. (반복)
    • 이진 검색 트리(5639)
      • 부모노드를 기점으로 왼쪽자식은 부모노드보다 작고, 오른쪽자식은 부모노드보다 크다는 특징을 유념하고 전위순회로 트리를 파악하여 후위순회 결과를 구한다.
    • 트리(4803)
      • 그래프의 모든 노드를 확인하여 트리가 만들어지는지(사이클이 없는지) 확인한다.
  • 랜덤문제: 스택/큐기능개발
    • 주먹구구 방식 대신에, 첫번째 프로그래스가 완료되려면 며칠이 지나야하는지 계산하면 더 빠르다.
    • 모든 프로그레스가 필요한 날짜를 계산하여 처리하는 방법도 있다.

계획 변경

1121

1128

  • 카테고리: DP
    • 퇴사
      • 뒤에서부터 일을 할 수 있는지 확인하면서 최댓값을 계산한다.
    • RGB 거리
      • 현재 위치에서 최소값을 구할 수 있게 위에 열에서 최솟값과 현재 값을 더해서 저장한다.
    • 1, 2, 3 더하기
      • 노가다로 규칙을 찾아서 해결(1일 때 결과값이 2일 때 결과값의 일부와 유사하다)
    • 가장 큰 증가 부분 수열
      • 주어진 수열에서 부분수열 범위 안에서 나올 수 있는 부분수열을 구한다.
    • 디스크 컨트롤러
      • 프로세스 상태관리처럼 덱의 준비큐, 우선순위큐의 대기큐를 만들어서 관리한다. 현재 시간보다 이전에 요청된 것이면 대기큐에 넣고, 현재 요청된 것이면 바로 처리하고, 현재 시간보다 이후에 요청된 것이면 대기큐에 넣은 것들을 하나씩 빼서 처리한다.
  • 랜덤문제: DP정수 삼각형
    • 트리의 루트 -> 리프 방법과 리프 -> 루트 방법 모두 존재한다. 다만 루트 -> 리프 방법이 인덱스 접근할 때 까다롭다.

1205

  • 카테고리: 시뮬레이션

    • 감시
    • 테트로미노
      • 특정 범위 안에 모든 도형이 들어갈 수 있다는 규칙을 찾아야하고, ㅗ, ㅏ, ㅜ, ㅓ 모양인 경우 dfs 처리방법이 조금 다르다.
    • 로봇 청소기
      • 규칙을 찾는 게 어려움: 방향을 꺾는 경우, 뒤로 가야하는 경우
    • 트럭
      • 덱을 이용해서 다리 역할을 한다.
  • 랜덤문제: 정렬K번째수

1212

1221

1226

  • 랜덤문제

0102

0109

  • 카테고리: 투포인터

  • 랜덤문제

    • 스택의 올바른 괄호
    • 완전탐색의 피로도
      • 굉장히 파이써닉한 코드🐍 solution = lambda k, d: max([solution(k - u, d[:i] + d[i+1:]) + 1 for i, (m, u) in enumerate(d) if k >= m] or [0])
      • dfs로도 풀 수 있었음
        function solution(k, dungeons) {
            let result = -1;
            const dfs = (k, dungeons, depth) => {
                for (let i = 0; i < dungeons.length; i++) {
                    const [min, use] = dungeons[i]
                    if (!min || k < min) continue;
                    dfs(k - use, dungeons.map((v, index) => index === i ? [null, null] : v), depth + 1)
                }
                return (result = Math.max(depth, result))
            }
            dfs(k, dungeons, 0)
            return result;
        }

0116

0123

0130