ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [알고리즘] 구현 정리
    알고리즘 2022. 9. 16. 15:00
    728x90

    구현 → 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

    시뮬레이션, 완전탐색 위주

    유형

    • 알고리즘은 간단한데, 코드가 길어지는 문제
    • 실수연산을 다루고, 특정 소수좀까지 출력하는 문제
    • 문자열을 특정 기준에 따라서 끊어 처리하는 문제 ( 중요 )
    • 적절한 라이브러리를 찾아 사용해야하는 문제

    2차원 공간은 행렬(matrix)의 의미로 사용

    • 2차원 배열, 리스트 → (앞,뒤) ⇒ for 앞 - 뒤 → col row → x,y로 생각하기
    • 방향 벡터가 자주 사용
    # ->(가로) 열 (y)  , (세로) 행 (x)
    # 동 북 서 남
    dx = [0,-1,0,1] 
    dy = [1,0,-1,0]
    

    문제1) 상하좌우

    수행과정

    • N * N , 가장 왼쪽 좌표 (1,1) = 시작좌표 ( 1≤ N ≤ 100 )
    • 공간을 벗어나는 것은 무시하고 다음 명령 따르기
    n = int(input())
    x,y = 1,1
    plans = input().split()
    
    # 서 동 남 북
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    
    move_type = ['L','R','D','U']
    
    # 이동 계획을 하나씩 확인하기
    for plan in plans:
    	for i in range(len(move_type)): #이동후 좌표 구하기
    		if plan == move_type[i]:
    			nx = x + dx[i]
    			ny = y + dy[i]
    			# nx, ny에서 초기화를 하는것
    	if nx < 1 or ny < 1 or nx > n or ny > n: #공간을 벗어나는 경우 -> 무시한다 의미
    		continue
    	x,y = nx,ny
    print(x,y)
    

    문제2) 시각문제 ( 완전탐색 )

    수행과정

    • 정수 N, 00시 00분 00초 ~ N시 59분 59초까지의 모든 시각에서 3이 하나라도 포함되는 모든 경우의 수
    h = int(input())
    count = 0
    for i in range(h+1):
    	for j in range(60):
    		for k in range(60):
    			if '3' in str(i)+str(j)+str(k):
    				count += 1
    print(count)
    

    문제3) 왕실의 나이트

    수행과정

    • 8 * 8 체스판, 나이트는 L자로 이동, 체스판 밖으로 이동안함
    • 이동은 수직2칸 → 수평1칸 or 수평2칸 → 수직 1칸
    • 나이트 위치에 따라 이동 가능한 경우의 수를 구하기

    idea

    • 방향 벡터 사용
    • 다음 위치 값이 체스판을 벗어나지 않으면 카운트 값 증가
    input_data = input()
    row = int(input_data[1])
    col = int(ord(input_data[0]) - int(ord('a')) + 1 #열을 숫자로 표현하다는 조건때문
    
    steps= [(-2,-1), (-1,-2), (1,-2), (2,-1), (2,1), (1,2), (-1,2), (-2,1)] 
    
    res = 0
    for step in steps:
    	next_row = row + step[0]
    	next_col = col + step[1]
    	if next_row >= 1 and next_row <= 8 and next_col >= 1 and next_col <= 8:
    		res += 1
    
    print(res)
    

    문제4) 문자열 재정렬

    수행과정

    • 입력: 문자의 대문자 + 숫자 (0~9)

    idea

    • 문자를 오름차순으로 정렬 후, 숫자만 더한값을 뒤에 정렬
    data= input()
    res = []
    value = 0
    
    for x in data:
    	if x.isalpha(): #isalpha는 알파벳을 확인하는 내장함수
    		res.append(x)
    	else:
    		value += int(x)
    
    res.sort()
    if value != 0:
    	res.append(str(value))
    print(''.join(res))
    
Designed by Tistory.