* 나동빈님의 이코테 2021강의 정리

구현

• 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.
• 구현 유형의 문제: 풀이는 생각하는 건 쉽지만, 소스코드로 옮기기 어려운 문제.
• e.g.
  1. 알고리즘은 간단, 코드가 긴 문제.
  2. 실수 연산하고, 특정 소수점까지 출력하는 문제.
  3. 문자열을 특정한 기준에 맞춰 잘라서 처리하는 문제.
  4. 적절한 라이브러리 찾아서 사용하는 문제(e.g. 모든순열, 모든조합).
• 알고리즘에서 2차원 공간은 행렬(Matrix).
• 시뮬레이션, 완전탐색 묻는 방향벡터 자주 활용.

문제1: 상하좌우

• NxN 공간. 상,하,좌,우 이동. 시작 좌표는 가장 왼쪽 위 좌표 (1,1). 공간을 벗어나는 움직임 무시.

문제해결방법

• 시뮬레이션 유형. 구현이 중요한 대표적 문제.

답안(Python)

n = int(input())
x, y = 1, 1
plans = input().split()

# L, R, U, D에 따른 이동 방향
dx = [0,0,-1,1]
dy = [-1,1,0,0]
move_types = ['L','R','U','D']
for plan in plans:
	# 이동 후 좌표 구하기
	for i in range(len(move_types)):
    	if plan == move_types[i]:
        	nx = x + dx[i]
            ny = y + dy[i]
    # 공간으 벗어나는 경우 무시
	if nx<1 or ny<1 or nx>n or ny>n:
	continue
	# 이동 수행
	x,y =nx,ny          

답안(Java)

int n = sc.nextInt();
sc.nextLine(); // 버퍼비우기
String[] plans = sc.nextLine().split(" ");
int x = 1, y = 1;

int[] dx = {0,0,-1,1};
int[] dy = {-1,1,0,0};
char[] moveTypes = {'L','R','U','D'};

for(int i=0; i<plans.length; i++){
	char plan = plans[i].charAt(0);
    int nx= -1, ny= -1;
    for(int j=0; j<4; j++){
    	if(plan == moveTypes[j]){
        	nx = x+dx[j];
            ny = y+dy[j];
        }
     }
     if(nx<1 || ny<1 || nx>n || ny>n) continue;
     
     x=nx;
     y=ny;

문제2: 시각

• 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 문제. 00시 00분 00초 부터 N시 59분 59초.

문제해결방안

• 가능한 모든 시각의 경우를 하나씩 모두 세서 해결 -> 완전탐색(Brute Forcing), 가능한 경우의 수를 모두 검사해보는 탐색방법.

답안(Python)

n = int(input())
cnt = 0

for i in range(n+1):  
  for j in range(60):
    for k in range(60):
      if '3' in str(i)+str(j)+str(k):

답안(Java)

public static boolean check(int h, int m, int s){
if(h%10 == 3 || m/10==3 || m% 10 ==3|| s/10 ==3 || s%10==3) 
	return true;
 return false;
 }
 
 # main
 int h = sc.nextInt();
 int cnt = 0;
 for(int i=0; i<60; i++){
 	for(int j=0; j<60; j++){
    	for(int k=0; k<60; k++){
        	if(check(i,j,k)) cnt++;
            }
        }
   }

문제3: 왕실의 나이트

• 8x8의 좌표 평면. 나이틑 이동할 때 L자 형태로만 이동.
  1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동.
  2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동.
• 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수 구하기.

문제해결방법

• 8가지 경로를 하나씩 확인하며 각 위치도 이동이 가능한지 확인. 리스트로 8가지 방향에 대한 벡터를 정의.

답안(Python)

# 현재 나이트 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1

# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]

# 각 8가지의 방향으로 이동할 수 있는지 확인
result = 0
for step in steps:
	# 이동하고자 하는 위치 확인
    next_row = row+step[0]
    next_column = column+step[1]
    # 해당 위치로 이동 가능하면 카운트 증가
    if next_row >=1 and next_row <=8 and next_column>=1 and next_column<=8:
    	result +=1

답안(Java)

#Main
String inputData = sc.nextLine();
int row = inputData.charAt(1)-'0';
int column = inputData.charAt(0)-'a'+1;

int[] dx = {-2,-1,1,2,2,1,-1,-2}
int[] dy = {-1,-2,-2,-1,1,2,2,1}
int result = 0;
for(int i=0; i<8; i++){
	int nextRow = row+dx[i];
    int nextColumn = column+dy[i];
    if(nextRow>=1 && nextRow<=8 && nextColumn>=1 && nextColumn<=8){
    result += 1;
    }
 }

문제4: 문자열 재정렬

• 알파벳 대문자와 숫자로만 구성된 문자열을 알파벳은 오름차순, 숫자는 모두 더해서 출력.

문제해결방안

• 리스트에 저장된 알파벳을 정렬하고, 뒤에 합계를 붙여서 출력.

답안(Python)

n = input()
number = 0;
s_list = []

# 문자 하나씩 확인
for c in n:
  # 알파벳이면 리스트에 삽입
  if c.isalpha():
    s_list.append(c)
  # 숫자면 더하기
  else:
    number += int(c)
# 알파벳 오름차순 정렬
s_list.sort()

# 숫자가 하나라도 존재하면 리스트 뒤에 삽입
if number != 0:
  s_list.append(str(number))
  
# 리스트를 문자열로 변환하여 출력
print(''.join(s_list))

답안(Java)

# Main
String n = sc.next();
int num = 0;
ArrayList<Character> list = new ArrayList<Character>();

for(int i=0; i<n.length(); i++){
	if(Character.isLetter(n.charAt(i)){
    	list.add(n.charAt(i));
     }
     else{
     	num += str.charAt(i)-'0';
     }
}
Collection.sort(list);

for(int i=0; i<list.size(); i++){
	System.out.print(list.get(i));
    }
 if(num!=0) System.out.print(num);