네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2. 풀이 과정 처음엔 쉬운 풀이 방법이 있을까 생각하다가, 안 떠올라서 그냥 모든 경우의 수를 다 돌려보고 생각해봐야겠다 하고 구현했는데, 통과가 되었다. 위로, 아래로, 왼쪽으로, 오른쪽으로 각각 0, 1, 2, 3으로 생각하고 5개를 뽑는 중복 순열을 만들었다. 선택한 차례대로 함수를 실행시켜 결과를 냈다. 1) 최대값 구하기 - 처음 값을 입력받을 때..

0. Cookie와 Session이란? client 단위로 상태 정보를 유지할 때, 사용된다. client의 요청을 받은 server는 요청을 처리하고 응답을 해줄 때, Http protocol이 활용된다. Http protocol은 응답을 하고 나면 바로 연결을 해제하면서 사용된 정보가 유지되지 않는데 이를 stateless라고 한다. 이때, 정보를 유지하기 위해 Cookie와 Session을 사용한다. Cookie Session 공통점 Map 형식으로 관리하기 때문에 key값 중복X 차이점 Type javax.servlet.http.Cookie (Class) javax.servlet.http.HttpSession (Interface) 저장 위치 Client의 컴퓨터의 file Server의 메모리 저..

1. 문제 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 2. 풀이 과정 1 => N번째 집을 차례대로 색을 칠한다. 각자 자신의 앞의 집의 색깔만 피하면 된다. 단, 마지막 집은 첫 번째 집의 색깔도 고려해야하기 때문에 처음부터 첫 번째 집의 색에 따라 나눠 계산했다. 첫 번째 집 색에 따라 R[], G[], B[]를 만들어서 값을 업데이트해갔다. 이는 Dynamic Programming을 사용한 풀이 방법이라 ..

1. 문제 https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 2. 풀이과정 1. mid보다 작거나 같은 값 개수 세기 n이 5이고 검사하는 값을 mid = 6이라고 할 때, 6보다 작거나 같은 값의 개수를 세는 법은 아래와 같다. 1*1, 1*2, 1*3, 1*4, 1*5 2*1, 2*2, 2*3, 2*4 ,2*5 3*1, 3*2, 3*3, 3*4, 3*5 4*1, 4*2, 4*3, 4*4, 4*5 5*1, 5*2,..

1. 문제 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 2. 풀이과정 최단거리 구하기는 보통 bfs, 도착지점까지 경로를 구한다면 dfs를 주로 사용하는 것 같다. 이 문제는 최단거리를 구하는 문제로 bfs를 사용하여 풀었다. 최단거리만큼만 모든 경로를 탐색하기 때문에 최악의 경우(모든 경로 끝까지 전체탐색)을 막을 수 있다. 처음에는 boolean visited[N][M][2]로 3차원배열을 사용해서 visited..

1. 문제 https://www.acmicpc.net/problem/1726 1726번: 로봇 많은 공장에서 로봇이 이용되고 있다. 우리 월드 공장의 로봇은 바라보는 방향으로 궤도를 따라 움직이며, 움직이는 방향은 동, 서, 남, 북 가운데 하나이다. 로봇의 이동을 제어하는 명령어는 www.acmicpc.net 2. 풀이과정 문제를 처음 봤을 때, BFS를 떠올렸다가 1~3칸 전진과 1(90도)~2(180도)번 전진 처리가 복잡해 DFS로 풀었다. 그런데, 풀고나서 보니 DFS보다 BFS를 썼을 때 더 빠르게 구현할 수 있을 것 같아 BFS로 다시 풀어보았다. 결과적으로 BFS가 메모리, 시간 측면에서 더 효율적이다. 아래 그림은 두 코드에서 사용한 방향 전환할 때, 걸리는 시간을 구하는 방법이다. 동서..

1. 문제 https://www.acmicpc.net/problem/17135 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 2. 풀이과정 1. 궁수 3명의 위치에 대해 조합 구하기 2. 각 조합마다 simulation() 실행 [Simulation] 1.시간이 N(배열의 세로)만큼 지나서 더 봤자 적들이 없는 경우 or 그 전에 적들을 다 물리친 경우 반복 종료 1-1. 각 궁수마다 bfs로 가장 가까운 적을 찾음 but 찾고 있는 거리가 D보다 커지면 다음 궁수로 넘어감. 1-2. 가장 가까운 적을 찾으면, -cas..

1. 문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 2. 풀이 과정 1) 입력을 받으면서 집과 치킨집의 위치를 각각 저장 2) 저장된 치킨 집 중 M개를 뽑는 조합 구현 3) 조합마다 결과를 비교해서 최소값 찾기 tip) 집과 치킨집과의 거리는 매조합마다 쓰이므로 미리 저장해놓고 가져다 쓴다. import java.io.BufferedReader; import java.io.InputStreamReader; impo..

1. 문제 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 2. 풀이과정 n의 경우의 수 = (n-1에서 1x2블럭을 추가했을 때) + (n-2에서 2x1블럭 2개 혹은 2x2블럭 1개를 추가했을 때) 정리하면, f(n) = f(n-1) + f(n-2) * 2로 수식을 나타낼 수 있다. n = int(input()) x, y = 1, 3 for i in range(n-2): temp = y y = y + x*2 x = temp if n == 1: print(x) else: ..

1. 문제 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 2. 풀이 과정 n = int(input()) graph = [[*map(int, input().split())] for _ in range(n)] shark = 2 dxy = [(-1, 0), (0, -1), (0, 1), (1, 0)]#위왼오아 #먹을 물고기 찾기 def find(n1, n2): q = [] q.append((n1, n2, 0)) visited = [[0 fo..