daeunni/for_codingtest

Algorithm archive for future 🔥

for_codingtest's Issues

(DFS) 연구소 : 무작위 3개의 벽 생성에 대해

for i in range(n):
    for j in range(m):
        if data[i][j] == 0:  # 빈공간이면
            data[i][j] = 1
            count += 1

            dfs(count)

            data[i][j] = 0  # 여기는 무슨 의미인지 잘 모르겠어,,,
            count -= 1

위 코드가 왜 무작위로 3개의 벽을 생성하는 코드가 되는지 잘 모르겠다.

(Sorting) MaxProductOfThree : 모든 경우의 수에 적용되는 절대규칙을 찾아야하는 문제

"""
 MaxProductOfThree
  - 리스트 내 원소 3개 곱의 최댓값 찾기 
  - sorting을 활용해 모든 경우의 수에 적용되는 <절대규칙>을 찾는 문제 !
"""

def solution(A):
  A.sort()         # 오름차순 정렬 
  return max(A[-1]*A[-2]*A[-3], A[0]*A[1]*A[-1])

경우의 수

1. Max 값을 만드는 경우

   • 음수 * 음수 * 양수
   • 양수 * 양수 * 양수

2. 배열의 원소 구성 경우의 수

   • 모두 양수인 배열
   • 모두 음수인 배열
   • 양수 + 음수인 배열

(BFS) 바이러스 : 단방향그래프 저장방식 > 인접행렬로 변환에 대해

"""
바이러스 
  - BFS를 이용하는 것 같아 (시작노드는 항상 1)
"""
from collections import deque 

c = int(input())     # 컴퓨터 수 
pair = int(input())  # 연결된 쌍의 수 
result = 0 


# 연결된 쌍의 수 단방향그래프처럼 저장 >>>> (그래프 입력 방식을 바꿔야할 것 같다. 9, 1같은 경우 현재 count를 못하고 있음) 
# >>> matrix 형태로 바꿔보기 

graph = [[] for _ in range(c + 1)]
for _ in range(pair):
  a, b = map(int, input().split())    # a > b 
  graph[a].append(b)                        # 연결리스트 형태로 저장 

  # 그냥 반대도 고려해주면 안되냐 이렇게 
  graph[b].append(a)


## BFS로 1과 인접한 쌍 찾기 
q = deque([1])            # 시작노드 = 1 

# 방문여부 확인 
visited = [False for i in range(c+1)]    

while q : 
  now = q.popleft()
  # print(now)
  result += 1
  visited[now-1] = True

  # 인접노드 탐방 
  for next in graph[now]: 
    if visited[next-1] == False :
      q.append(next)
      visited[next-1] == True       # 방문체크 

print(result-1)

위 코드는 테스트케이스는 작동하는데, 단방향그래프 저장방식으로 그래프를 저장해서 통과하지 못한 코드이다.
이를 인접행렬로 저장하도록 변경하여 BFS를 적용하는 방법 생각해보기.. !

(MaxSlice) MaxSliceSum : 다이나믹 프로그래밍으로 다시풀기

문제

A non-empty array A consisting of N integers is given. A pair of integers (P, Q), such that 0 ≤ P ≤ Q < N, is called a slice of array A. The sum of a slice (P, Q) is the total of A[P] + A[P+1] + ... + A[Q].

Write a function:

class Solution { public int solution(int[] A); }

that, given an array A consisting of N integers, returns the maximum sum of any slice of A.

For example, given array A such that:

A[0] = 3 A[1] = 2 A[2] = -6
A[3] = 4 A[4] = 0
the function should return 5 because:

(3, 4) is a slice of A that has sum 4,
(2, 2) is a slice of A that has sum −6,
(0, 1) is a slice of A that has sum 5,
no other slice of A has sum greater than (0, 1).
Write an efficient algorithm for the following assumptions:

N is an integer within the range [1..1,000,000];
each element of array A is an integer within the range [−1,000,000..1,000,000];
the result will be an integer within the range [−2,147,483,648..2,147,483,647].

초기답안 (69%)

def solution(A):

  # 예외 1) 빈 리스트일 때 
  if len(A) == 0 : 
    return 0

  max_start = A[0]    # 우선 처음으로 초기화
  max_slice = A[0]    # 예외 2) 원소가 하나라 이 뒤에가 없을 때를 대비해 초깃값을 이렇게 설정 
  present = 0 

  # 각 원소별 반복문 
  for i in A : 
    present = 0 
    
    if i > max_start :
      max_start = i    # max_start값 업데이트 

    # 진짜 이중for문..? 
    for j in A[A.index(max_start):]:    # j에 max_start도 포함하게됨
      present += j     # 누적합 

      if present > max_slice : 
        max_slice = present

  return max_slice

# 아 이 경우에는 앞 값을 빼야하는데.. 처음값으로 초기화하면 안되는건가?? 
A = [-5, 2, 3]
solution(A)

(DFS) 적록색약 : 왜 내 코드는 안되는지 찾고싶어......

내 코드

"""
적록색약 
  - 음료수 얼려먹기 문제와 비슷하게 상하좌우 dfs로 접근
  - 음료수 얼려먹기 문제는 1의 영역만 파악했다면, 이 유형은 R, G, B의 유형을 각각 파악해야함 
  - 색맹인 사람과 아닌사람의 값을 구분해서 출력해줘야 했음
"""

n = int(input())
graph = []
count = []

for i in range(n):
  graph.append(list(map(str, input())))       # 그래프 세로줄 개수만큼 입력 > 입력시 띄어쓰기 하지말기!!!


# x, y 좌표로 그래프 내에서 움직이기 
def dfs(x, y, color):

  if x < 0  or x > n-1 or y < 0 or y > n-1 : 
    return False

  ## 특정 color와 같으면 dfs 수행 > 방문처리를 어떻게 할까? 
  if graph[x][y] == color:

    ## ********방문처리 체킹을 다르게하기 ******* 
    if graph[x][y] == 'R' or graph[x][y] == 'G':
      graph[x][y] = 'RG'
    else:
      graph[x][y] = 'v'    

    dfs(x-1, y, color)
    dfs(x, y-1, color)
    dfs(x+1, y, color)
    dfs(x, y+1, color)

    return True        # 이어져있는 쌍을 찾았을 때 

  else:
    return False

for color in ['R', 'G', 'B', 'RG']:
  temp = 0
  for i in range(n):
    for j in range(n):
      if dfs(i, j, color) == True:     # 특정 color 지정해서 확인 
        temp += 1

  count.append(temp)       # 색깔별 count를 적재 

print(sum(count[:3]), sum(count[2:]))  # 색맹 아닌사람, 색맹인사람 

정답코드

n = int(input())
picture = []
count = []

for i in range(n):
  picture.append(list(map(str, input())))    


def dfs(x,y,color):
    if x < 0 or  x > n-1 or y < 0 or y > n-1:
        return False

    ## 색깔별로 count 
    if picture[x][y] == color:

        ## 체킹을 다르게 함 
        if picture[x][y] == 'R' or picture[x][y] =='G':
            picture[x][y] = 'RG'
        else:
            picture[x][y] = 'v'

        dfs(x-1,y,color)
        dfs(x+1,y,color)
        dfs(x,y-1,color)
        dfs(x,y+1,color)

        return True
    else:
        return False

for color in ['R','G','B','RG']:       # 색깔별로 영역 개수 세기 
    temp = 0

    for i in range(n):
        for j in range(n):

            if dfs(i,j,color) == True:
                temp += 1

    count.append(temp)

print(sum(count[:3]), sum(count[2:]))

---

대체 뭐가 다른거야 ~~

(MaxSlice) MaxProfit : 문제 상황을 업데이트할 변수를 정해 간단히 만들기

업데이트할 변수를 정하기

"""
MaxProfit
  - 리스트 내에서 주식 가격의 가장 큰 이익을 구하는 문제
  - 인덱스의 순서는 유지하면서, 효율적으로 이익이 큰 경우를 탐색하는게 어려운 문제

1) 무조건 << []-작은값 >> 을 빼야 최대 이익을 얻을 수 있는 것은 자명하다
2) 순서대로 리스트 원소를 순회하면서 1) min값   2) profit값 을 업데이트하는 방식을 이용한다 ! 
"""

A = [23171, 21011, 21123, 21366, 21013, 21367]

def solution(A):

  # 예외 1) element 수가 적어 이익을 계산할 수 없을 때 
  if len(A) < 2:
    return 0

  # 최솟값은 우선 첫번째 원소로 잡는다
  min = A[0]
  profit = 0

  for price in A : 
    present = price - min     # 현재의 이익 

    # 현재 이익이 더 크면 업데이트 
    if profit < present : 
      profit = present

    # 최솟값 더 작으면 업데이트 
    if min > price : 
      min = price
    
    # >> 이러한 방식으로 하면 인덱스도 유지된다. 

  return profit

solution(A)

(백트래킹) N-queens 문제

현재 : 23.01.28
거의 다 온 것 같은데 어디가 문제일까? 꼭 혼자 힘으로 해결해보고 싶다...

def check(col, ori_col):
  if col == ori_col or col == ori_col+1 or col == ori_col-1 :
    return False    # 탈락 (상하좌우대각선 위치)
  else : 
    return True 

def Nqueens(depth):
  global count, ori_col, cur_count  

  if depth > n :      # 종료조건 
    return 

  # 특정 depth의 col number별 반복문 
  for idx in range(n) : 

    if depth == n and cur_count == n : 
      count += 1 
      return 

    # depth가 n보다 작으면 
    if check(field[idx], ori_col):     # 상하좌우 대각선 위치 X
      depth += 1
      ori_col = field[idx]
      cur_count += 1               # 이 raw의 queen의 위치는 정해졌다. 

      Nqueens(depth)

      depth -= 1                 # 백트래킹 이렇게 해도 되나? 
    
      cur_count -= 1

    # if cur_count < depth : 
    #   return 

if __name__ == '__main__':
  # n = int(input())
  n = 8 
  count = 0
  ori_col = 0 
  cur_count = 0
  field = list(range(n))      # field 설정 (중복 허용 X) 
  Nqueens(0)
  print(count)     # 경우의 수 

(큐) 프린터 큐 : 중복 고려해 코드 발전시키기

현재 내 코드

틀린거 아닌데, 중복된 경우를 고려하지 않아 문제가 생겼다.
https://www.acmicpc.net/problem/1966

import sys 
from collections import deque 
# input = sys.stdin.readline
t = int(input())
result = []

for _ in range(t):
  n, m = map(int, input().split())    # m : 궁금한 원소가 queue에서 몇번째 놓여있는지 나타냄
  imp = None
  output = []
  imp = deque(map(int, input().split()))

  # 궁금한 원소 
  find = imp[m]

  # 큐가 빌 때까지 반복 
  while imp : 
    if max(imp) == imp[0] : 
      output.append(imp.popleft())
    else:
      imp.append(imp.popleft())   # 왼쪽에서 빼서 가장 뒤에 재배치 

  result.append(output.index(find) + 1)      # 몇번째로 나왔는지 

for i in result :
  print(i)

리턴값은 다음과 같이 나온다.. 즉 1이 중복될 때 그냥 단순히 index로 find해서 문제가 생기는 것이다..

1
6 0
1 1 9 1 1 1
imp: deque([1, 1, 9, 1, 1, 1])
find: 1
중간 imp : deque([1, 9, 1, 1, 1, 1])
중간 imp : deque([9, 1, 1, 1, 1, 1])
중간 imp : deque([1, 1, 1, 1, 1])
중간 imp : deque([1, 1, 1, 1])
중간 imp : deque([1, 1, 1])
중간 imp : deque([1, 1])
중간 imp : deque([1])
중간 imp : deque([])
output: [9, 1, 1, 1, 1, 1]

이걸 수정해보자 !

(Leader) EquiLeader 문제 : 시간복잡도 개선하려면?

내 코드

시간 복잡도를 개선하려면 어떻게 해야할까....

현재는 O(N^2) 복잡도를 가진다

"""
Dominator
  - 리스트 내에서 절반 이상(+과반수) 발생하는 원소의 인덱스 리턴 
  - Counter의 most_common(1) 함수를 이용한다!
"""

from collections import Counter 

def solution(A):
  count_s = 0

  # 예외 1) 리스트가 비어있을 때 
  if len(A) == 0 :
    return 0

  # s를 일일히 순회하면서 잘라가기..? > 여기서 시간복잡도가 커진 것 같아
  for s in range(len(A)-1):
    left, right = A[:s+1], A[s+1:]

    # 두 부분의 leader가 같으면?
    left_count = Counter(left).most_common(1)[0]
    right_count = Counter(right).most_common(1)[0]

    # 과반수 넘는지 check 
    if left_count[1] > len(left)//2 and right_count[1] > len(right)//2:
      if left_count[0] == right_count[0] :
        count_s += 1
    
  return count_s

(Prefix Sum) Passing car문제 : 시간복잡도 관련

내 코드 - 시간 복잡도 O(N**2)

# from more_itertools import locate      # 이 함수는 코테에서 지원하지 않음 

def solution(A):
  result = 0

  # 0의 인덱스, 1의 인덱스 구분 
  zero = [i for i, x in enumerate(A) if x==0]
  one = [i for i, x in enumerate(A) if x==1]
  
  # 근데 이건 그냥 순회만 하는거니까 별로 연산량이 안들지 않을까? 
  for z in zero:
    for o in one:
      if z<o:
        result += 1
        
  # 초과하는 예외 경우 (경우의수 count)
  if result > 1000000000:
    return -1

  return result 

solution([0, 1, 0, 1, 1])

이 코드를 어떻게 개선할지 찾아보다가, 인터넷에서 다음과 같은 풀이들을 찾았다.

---

정답코드

왜지... 어떻게 저런 생각을 할 수 있는걸까...

(DFS) 섬의 개수 : 엄청 동일해보이는데 왜 내 코드는 안될까

음료수 얼려먹기와 분명 엄청 동일해보이는데 왜 내 코드는 안되는가....

# 재귀함수 문제에는 꼭 이 코드를 써주자 !! 
import sys
sys.setrecursionlimit(10 ** 6)


def dfs(x, y):

  # 영역 벗어나면 종료
  if x < 0 or x >= w or y < 0 or y >= h:
    return False
  
  if graph[x][y] == 0 : 
    return False

  # 아직 땅(1)을 방문하지 않았다면 
  if graph[x][y] == 1 :     
    graph[x][y] = 0 

    # 재귀적 호출 (상하좌우) + **대각선도 추가해야함**
    dfs(x-1, y)
    dfs(x, y-1)
    dfs(x+1, y)
    dfs(x, y+1)

    ## 대각선 추가
    dfs(x-1, y+1)
    dfs(x+1, y+1)
    dfs(x-1, y-1)
    dfs(x+1, y-1)

    return True

  return False

# 연속적으로 input 받기 
while True :
  w, h = map(int, input().split())    # 가로 * 세로 
  count = 0 

  # 둘다 0이면 중단 
  if w == 0 and h == 0 :
    break
  
  graph = []
  for _ in range(h):     # 세로만큼 입력 
    graph.append(list(map(int, input().split())))     # map 입력 (2차원 리스트)

  for i in range(h):
    for j in range(w):
      if dfs(i, j) == True:
        count += 1

  print(count)