220615_w1_랜덤유형 - Sunny-W-Park/elice-sw2-algorithms GitHub Wiki

박선우 - #1009 분산처리

문제 해석

  • 컴퓨터 10대로 데이터 처리
  • 1번: 1번 컴퓨터 / 2번: 2번 컴퓨터 ... / 10번: 10번 컴퓨터 / 11번: 다시 1번 컴퓨터 패턴
  • 즉, n번째 컴퓨터는 10으로 나눈 나머지 번째의 컴퓨터로 처리, 나머지가 0일 경우 10번 컴퓨터
  • N = 테스트 케이스 수
  • a, b가 주어지고, a^b 컴퓨터는 몇번째로 처리하는지 구하기(=10으로 나눴을 때 나머지는?)

접근 및 풀이과정

  • 1~9까지 거듭제곱했을 때의 패턴을 파악
    • 1: 1
    • 2: 2, 4, 8, 6
    • 3: 3, 9, 7, 1
    • 4: 4, 6
    • 5: 5
    • 6: 6
    • 7: 7, 9, 3, 1
    • 8: 8, 4, 2, 6
    • 9: 9, 1
  • 10은 나누어 떨어지는 경우 -> 최종 출력 10
  • 경우의 수를 구분해보면 [1, 5, 6]은 1가지, [4, 9]는 2가지, [2, 3, 7, 8]은 4가지
    • a^b에서 a%10 값으로 판단
    • 1가지일 경우: a^b 에서 a%10 그대로 출력
    • 2가지일 경우: a^b 에서 b를 2으로 나눈 나머지를 구하고, 나머지가 0일 경우 a%10 그대로 출력, 아니면 a%10을 제곱한 값의 1의 자리 출력(%10)
    • 4가지일 경우: a^b 에서 b를 4로 나눈 나머지를 구하고, 나머지가 0일 경우 a^4%10 출력, 아니면 a%10에 b%4을 제곱한 값의 1의 자리 출력(%10)

백성호 - #2667-단지번호 붙이기

문제 해석

  • N*N 크기의 0,1로 이루어진 지도가 주어진다.
  • 0은 집이 없는 곳, 1은 집이 있는 곳을 나타낸다.
  • 집이 있는 곳 상,하,좌,우에 집이 있다면 두 집은 연결이 되어있는 상태이다.
  • 연결된 집의 모임을 단지로 정의할 때, 단지의 총 개수와 각 단지의 집의 개수를 오름차순으로 정렬하여 출력

접근

  • DFS 함수 활용
    • DFS로 집인 경우 상하좌우를 탐색하여, 연결된 집들을 방문 처리
    • 방문 처리 시, 전역 변수에 집 카운트 증가
  • 지도 전체 탐색 시, DFS가 단지 마다 처음 실행 될 경우 집의 개수 초기화 + 단지 개수 증가

풀이 과정

  • 그래프를 0, 1로 이루어진 2차원 배열로 입력받음
  • DFS 함수 정의
    • graph를 벗어나거나 (x,y가 0미만, N 이상), 집이 아니거나 방문 했다면 (숫자 0) return으로 함수 종료
    • 집이라면 방문 처리 후 (1 => 0), 집 개수를 나타내는 전역 변수 house에 1 증가, 상하좌우 DFS 함수 재귀 반복
  • 총 단지 수를 result 변수로 정의, 집의 개수를 기록할 house_array를 []로 설정
  • 이중 for 문으로 graph 전체 탐색, 집이 발견되면 result에 1 증가 + DFS 탐색 + DFS로 증가된 house 개수를 house_array에 추가
  • sort로 house_array 오름차수 정렬
  • 문제 출력 양식에 맞게, result 출력 후, house_array의 원소들 출력

지의신 - 프로그래머스-정수 삼각형

문제 해석

  • 삼각형 모양의 배열이 입력으로 주어진다.
  • 첫줄은 숫자 한개, 두번째 줄은 숫자 두개, n번쨰 줄은 숫자 n개가 주어진다.
  • 첫줄 부터 마지막 줄까지, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 것이다. 그리고 그 합을 리턴한다.
  • 아래칸으로 이동할 때는 대각선 방향으로 한칸 오른쪽 or 왼쪽으로만 이동이 가능하다.

접근

  • DP 함수 활용
    • DP 배열을 만들지 않고, 기존에 입력으로 주어진 배열을 갱신해 나간다.
    • 두번 째줄부터 시작해서, 위에 칸중에서 대각선의 한칸 왼쪽 or 오른쪽에서 더 큰 숫자를 더해서 갱신한다.
  • 그럼 마지막 줄에서 제일 큰 값을 찾으면 그것이 정답이다.

풀이 과정

  • 삼각형 모양(triangle)의 배열의 길이를 len 함수를 통해서 구한다.
  • DP 함수 정의
    • 1부터(두번째 줄) 마지막줄(len)까지 반복문을 돈다. i
    • 해당 줄에서, 첫번째 원소와, 마지막 원소는 위에칸에서 하나의 숫자로만 더해서 갱신할 수 있으므로, triangle[i][0] += triangle[i-1][0], triangle[i][i] += triangle[i-1][i-1] 이렇게 갱신한다.
    • 그리고 첫번째 원소와, 마지막 원소 사이에 있는 원소들은 위에칸의 두 숫자중에서 더 큰 값으로 갱신한다.
  • 반복문이 끝나고, answer = max(triangle[leng-1]) 이렇게 마지막줄에서 제일 큰 숫자를 반환하면 정답이다.

주지호 - 프로그래머스-문자열 압축

문제 해석

  • 반복되는 알파벳을 포함하는 문자열을 압축하여 반복횟수를 숫자로 표현한다.
  • 압축할 문자열 개수를 기준으로, 가장 짧게 압축할 수 있는 문자열의 길이를 반환한다.

접근

  • 최악의 경우는 2 이상의 단위로 압축할 수 없는 것, 즉 전혀 압축되지 않고 기존의 문자열 길이를 리턴해야 하는 것이다.
  • 따라서 초기 시작 값을 문자열 길이로 시작하고, 기존 값보다 짧을 때마다 현재 문자열의 길이를 할당하여 줄여나간다.
  • 한 번이라도 줄여야 의미가 있으므로, 반복문의 상한선을 문자열 길이의 절반으로 할당한다.

풀이 과정

  • 1부터 문자열길이의 절반 + 2 를 더한 값 까지 반복문을 선언한다.

    • 1부터 시작하는 이유는, 현재 검사할 currword 변수는 문자열[:i]의 형태로, 0~i까지의 인덱스를 슬라이싱하기 때문이다
    • 문자열길이의 절반 + 2 를 더해주는 이유는, 입력받는 문자열의 길이가 1일 경우 에러가 발생하기 때문이다.
      • 따라서 문자열 길이가 1일 경우의 예외처리를 해준다면, 반복문의 조건이 바뀌어도 무방하다

  • 현재 검사할 currword 변수가 다음 단어라면(s[j:j+i]), 현재 단어가 얼마나 중복되어 있는지 나타내는 count 함수를 증가시키고 넘어간다.

    • count를 할당하는 이유는 해당 단어가 전혀 중복되지 않았을 때와 그렇지 않을 때의 예외처리가 필요하기 때문이다.
      • 2개라면 "2단어" 로 표기하지만 중복되지 않는다면 "1단어" 가 아닌 "단어" 로 표기해야 함

  • 만약 다음 단어가 현재 단어와 다르다면, word객체(현재 단위로 검사하는 결과값을 나타낼 변수)에 count변수 + currword를 더해준다.

    • ex) abcabc => 2abc, abc => abc

  • 그 후 count를 1로 초기화 후, 현재 단위의 다음 단어가 반복되는지 문자열의 절반까지 검사한다.

  • 해당 단위의 검사를 마친 후, 처음 초기화해주었던 sol함수(문자열 전체의 길이)와 비교 해서, min(sol, len(word))를 통해 더 짧은 값을 sol변수에 할당해준다.

  • 이를 반복하여, 1부터 문자열길이의 반 + 2 값 까지 전부 계산한다