두부의 코딩일기

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 최근에 풀었던 미로탐색(2178번), 숨바꼭질(1697번) 문제와 동일한 유형이다. 이 문제를 풀어보기 전에 먼저 풀어보는 걸 추천한다. 위 문제를 풀었으면 bfs 방법에 대해서는 확실히 이해했다고 가정하고 간단하게 설명하겠다. 이번 문제는 익은 토마토를 기준으로 상하좌우 한 칸씩 모든 토마토를 익혀야하는 문제이다. 즉, bfs를 중간에 끊지말고 끝까지 돌려야한다는 의미이다...

안녕하세요. 두부입니다. 오늘은 엑셀 중복값 입력을 방지하는 방법에 대해서 알아보겠습니다. 엑셀에서 제공하는 유효성 검사 기능을 가지고 사전에 중복값을 입력하는 실수를 방지할 수 있습니다. 위 데이터에서 '사번'을 중복된 데이터가 발생하지 않도록 제한해보겠습니다. 1. 입력하려는 범위를 드래그한 후에 [데이터] - [유효성 검사]를 클릭한다. 2. 유효성 조건 제한 대상에서 사용자 지정을 선택한다. 3. 수식 칸에 =COUNTIF(범위, 범위시작셀) = 1 을 입력한다. 해당 예제에서는 =COUNTIF( 를 입력 후에 중복값을 방지하려는 범위(A5부터 A20)까지 선택한다. ※ 선택한 후에는 꼭 F4를 눌러서 절대참조를 해준다. 절대참조를 해줬다면 콤마(,)를 입력하고 중복값을 방지하려는 범위의 시작 셀..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 해당 문제는 (0, 0)에서 출발해서 (N, M)까지 최단 경로를 구하는 bfs 문제이다. 서로 인접한 칸만 이동할 수 있으며 1은 이동할 수 있는 칸, 0은 벽을 의미한다. 예제 1번을 보면서 문제를 이해해보겠다. 예제 1번의 최단 경로를 그려보면 위와 같다. 이러한 유형의 문제는 대부분 입력 값을 넣어줄 Map 배열과 방문 여부를 판단하는 visited 배열 두 가지가 필요하다. int[][] map = new int[N+1..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이 최근에 풀어본 포도주 시식 문제(2156번)와 거의 똑같아서 점화식을 바로 찾을 수 있었다. 이 문제에서 제공하는 조건은 총 3가지이다. 1. 한 계단 혹은 두 계단을 오를 수 있다. 2. 연속된 3개의 계단은 밟을 수 없다. 3. 마지막 계단은 반드시 밟아야한다. 쉽게 생각해서 i번째 칸에 대해서 두 칸 전(i-2) + 현재 칸(i) 와 세 칸 전(i-3) + 한 칸 전(i-1) + 현재 칸(i)를 비..

HTML에서 div 태그는 주로 웹사이트의 레이아웃 구조를 설계하고 화면을 분할할 때 쓰인다. 과거 웹사이트에서는 table 태그로 공간 분할을 많이 했지만 요즘엔 div 태그를 이용한다고 한다. 하지만 div 태그는 하나의 공간을 의미하는 태그로 정확히 어떤 역할을 하는지 알 수가 없다. 그로인해 HTML5에서 레이아웃 관련 새로운 태그들이 추가되었다. 추가된 태그는 다음과 같다. 태그 설명 header 웹사이트의 메타데이터를 담고 있고, 페이지의 타이틀을 보여주는 부분 nav 페이지 이동할 때 이용하는 부분 aside 본문 옆에 존재하면서 주로 광고나 카테고리 목록으로 이용하는 부분 section 본문을 여러 개 포함하고 있는 부분 article 본문의 주내용이 들어가는 부분 footer 웹사이트의 ..

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 처음엔 dfs를 이용해서 접근했지만 시간을 구하는 게 어려워져서 bfs로 접근했다. 문제에서 제시된 수빈이가 이동하는 방법은 총 3가지이다. 1. n+1 2. n-1 3. 2n 위 방법으로 1초마다 한 번씩 이동할 수 있다. 예제를 통해서 문제를 차근차근 이해해보겠다. 1. 초기 상태 (0초) 2. 1초 수빈이가 이동할 수 있는 곳은 n+1 → 6 n-1 → 4 2..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 풀이 처음 문제를 봤을 때 이해가 잘 안갔다.. 검색을 하고나서야 이해가 갔다. 하나씩 이해해보겠다. 문제에선 두 개의 터렛 x, y 좌표와 류재명과의 r1, r2가 제공된다. 그렇다면 x, y를 기준으로 r1, r2의 반지름을 가진 원을 그릴 수 있다. 두 개의 원이 그러졌다면 A 터렛의 원과 B 터렛의 원의 접점 개수를 구하면 된다. 두 개의 원을 그렸을 때 생기는 접점의 개수에 대한 경우의 수는 몇 개일까? 위 그림처럼 여러가지가 있겠지만 4가..

https://www.acmicpc.net/problem/1652 1652번: 누울 자리를 찾아라 첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다. www.acmicpc.net 풀이 dfs, bfs 문제처럼 보이지만 쉽게 풀 수 있는 문제이다. 문제의 조건은 아래와 같다. 1. 2칸 이상의 빈 칸이 있으면 누울 수 있다. 2. 반드시 벽이나 짐에 닿게 된다. 이중 for문을 돌리면서 가로, 세로에 연속 2칸이 비어있으면 cnt++을 해준 후에 break; 문으로 for문을 빠져나왔다. 하지만 이렇게 하니까 예외 상황이 하나 생겼다. 바로 한 줄에 2개의 자리가 ..

https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 풀이 엄청 쉬운 문제라서 풀이라고 할 것도 없다. 주어진 변수는 총 4개 한수의 위치를 알려주는 x, y 우측 상단 꼭짓점을 알려주는 w, h 직사각형의 경계선까지 도달하는 최소 거리는 왼쪽, 오른쪽, 위, 아래 총 4가지이다. x, y, w-x, y-h의 최솟값을 구하면 된다. 최소값을 구하는 방법은 Math.min 혹은 if-else문을 사용하면 된다. 필자는 Math.mi..

다익스트라 알고리즘 (Dijkstra) 정의 음의 가중치가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘으로 BFS와 DP를 활용하는게 특징임 다익스트라 알고리즘 작동 원리 1. 방문하지 않은 정점들 중 거리가 짧은 정점부터 방문한다. 2. 해당 정점에서 인접하고 아직 방문하지 않은 정점들의 거리를 갱신한다. 예시를 보면서 살펴보겠다. A에서 E로 가는데 최단 거리는? A → D → C → E : 1 + 2 + 6 = 9 A → C → E : 4 + 6 = 10 A → B → D → C → E : 5 + 2 + 2 + 6 = 15 1. 시작 노드를 'A' 로 설정하고 이웃한 노드 중 거리가 짧은 순으로 노드를 선택해서 가중치(1, 4, 5)를 각 각 노드에 입력한다. 2. 1번..