전체 글397

• 

  [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree) 신장 트리(Spanning Tree) 신장 트리는 연결 그래프의 부분 그래프이다. 그래프의 모든 정점과 간선의 부분 집합으로 구성되는 트리이고, 모든 노드는 적어도 하나의 간선에 연결이 되어있어야 한다. 또한 이름에서 알 수 있듯이, 트리이므로 사이클이 존재해서는 안된다. 연결 그래프이므로, DFS(깊이 우선 탐색), BFS(너비 우선 탐색)를 이용하여 구현이 가능하다. 이 때 연결 그래프에는 하나의 신장트리 뿐만이 아닌 다양하게 존재할 수 있다. 이와 같은 연결 그래프가 있을 때, 나올 수 있는 신장 트리는 다음과 같다. 최소 신장 트리(Minimum Spanning Tree) 위에서 신장 트리에 대해 알아보았다. 그래프의 간선에 가중치가 있다면, 그것을 가중치 그래프라고 한다. 가중치 무방향 그래프에.. Algorithm 2022. 7. 21.

• 

  파이썬: 리스트(list)와 튜플(Tuple) 리스트와 튜플 파이썬에는 두 가지 다른 시퀀스 구조인 튜플과 리스트가 있다. 이들 항목은 다른 타입이 될 수 있다. 즉, 각 요소는 어떤 객체도 될 수 있다. 리스트 리스트는 데이터를 순차적으로 파악하는데 유용하다. 특히, 내용의 순서가 바뀔 수 있고, 문자열과 달리 변경이 가능하다. 리스트의 현재 위치에서 새로운 요소를 추가하거나 삭제 혹은 기존 요소를 덮어쓸 수 있다. 또한 동일한 값이 여러번 나타날 수 있다. 리스트 생성: [ ] 또는 list() 리스트는 0 또는 그 이상의 요소로 만들어진다. 콤마(,)로 구분하고, 대괄호([ ])로 둘러싸여 생성된다. 또한 list 함수로 빈 리스트를 할당할 수 있다. # list 생성 >>> empty_list = [] >>> days = ['Monday', .. Programming/Pyhton 2022. 7. 21.

• 

  파이썬: 숫자, 변수, 문자열 변수, 이름, 객체 파이썬에서는 모든 것(부울, 정수, 실수, 문자열, 데이터 구조, 함수, 프로그램)이 객체로 구현되어 있다. 즉, 파이썬은 다른 언어에는 결여된 언어 일관성과 유용한 기능을 제공한다. 객체는 데이터와 함께 무엇을 처리할 수 있는지 결정하는 부울 혹은 정수와 같은 타입이다. 객체의 타입이 int라면, 또 다른 int를 더할 수 있다는 것을 의미한다. 타입은 데이터 값이 변수인지, 상수인지 판단할 수 있다. 파이썬은 객체의 타입을 바꿀 수 없는 강타입이다. 프로그래밍 언어에서는 변수를 선언하여 사용할 수 있다. 파이썬에서 변수에 값을 할당할 때 =를 사용한다. a = 7 변수는 단지 이름일 뿐이다. 할당한다는 의미는 값을 복사하는 것이 아닌, 데이터가 담긴 객체에 그냥 이름을 붙이는 것이.. Programming/Pyhton 2022. 7. 20.

• [백준/BOJ] 12931번: 두 배 더하기 문제 https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주 www.acmicpc.net 해설 배열 A를 B로 만들 수도 있겠지만, 좀 더 쉽게 생각해보면 배열 B를 모두 0의 값을 가지게 만들어도 된다. 문제를 보면, 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 이를 반대로 생각하면 다음과 같다. 배열에 있는 값 하나를 1 감소시킨다. 배열에 있는 모든 값을 2로 나눈다. 여기서, 2번을 실행시키기 위해서는 모든 값이 짝수여야한.. PS(Problem Solving)/BOJ 2022. 7. 20.

• [백준/BOJ] 1245번: 농장 관리 문제 https://www.acmicpc.net/problem/1245 1245번: 농장 관리 첫째 줄에 정수 N(1 < N ≤ 100), M(1 < M ≤ 70)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄마다 격자의 높이를 의미하는 M개의 정수가 입력된다. 격자의 높이는 500보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 해설 농장의 산봉우리를 찾아야 한다. 따라서 전체 탐색을 해줘야 한다. 8방향을 확인하며 자신보다 높은 곳이 있다면 temp를 false로 바꿔준다. 또한 한 지점을 방문할 때마다 방문여부처리를 체크해준다. 자신보다 높은 곳이 없다면, 그 위치가 산봉우리가 된다. temp가 true라면 봉우리의 갯수를 증가시킨다. 소스 코드 import java.util.* p.. PS(Problem Solving)/BOJ 2022. 7. 18.

• [백준/BOJ] 7562번: 나이트의 이동 문제 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 해설 bfs의 기본적인 문제이다. 보통은 상하좌우 4방향으로만 이동하지만, 이 문제에서는 총 8방향으로 이동할 수 있다. 도착점에 도착하게 되면 bfs를 종료하고, 움직인 횟수를 출력하면 된다. 소스 코드 import java.util.* private val dy = intArrayOf(1, 1, -1, -1, 2, 2, -2, -2) private val dx = intArrayOf(-2,.. PS(Problem Solving)/BOJ 2022. 7. 17.

• [백준/BOJ] 2247번: 숨바꼭질 4 문제 https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 해설 https://jjunsu.tistory.com/197 [백준/BOJ] 1697번: 숨바꼭질 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순... PS(Problem Solving)/BOJ 2022. 7. 17.

• [백준/BOJ] 2468번: 안전 영역 출처 https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 해설 모든 지역이 물에 잠길 때까지 반복을 하며 안전한 영역이 가장 많을 때의 수를 구하면 된다. 때문에 입력을 받으면서 가장 높은 지역의 높이를 구해놓는다. ex) 최대높이 5 -> 0 ~ 5를 반복 각 지역에서 비가 온 만큼의 값을 빼준 후 bfs를 돌릴까 생각했지만, 이보다 비가 온 양보다 지역의 높이가 높을 때를 생각해주는 것이 더 편할 것 같았다. 따라서 if(arr[i][j] >= hei.. PS(Problem Solving)/BOJ 2022. 7. 15.

• [백준/BOJ] 7569번: 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자모양 상자의 칸에 하나씩 넣은 다음, 상자들을 수직으로 쌓아 올려서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 .. PS(Problem Solving)/BOJ 2022. 7. 14.

• [백준/BOJ] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하.. PS(Problem Solving)/BOJ 2022. 7. 13.

• [백준/BOJ] 7662번: 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제 이중 우선순위 큐(dual priority queue)는 전형적인 우선순위 큐처럼 데이터를 삽입, 삭제할 수 있는 자료 구조이다. 전형적인 큐와의 차이점은 데이터를 삭제할 때 연산(operation) 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점이다. 이중 우선순위 큐를 위해선 두 가지 연산이 사용되는데, 하나는 데이터를 삽입하는 연산이고 다른 하.. PS(Problem Solving)/BOJ 2022. 7. 12.

• [백준/BOJ] 3190번: 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임은 NxN 정사각 보드위에서 진행되고, 몇몇 칸에는 사과가 놓여져 있다. 보드의 상하좌우 끝에 벽이 있다. 게임이 시작할때 뱀은 맨위 맨좌측에 위치하고 뱀의 길이는 1 이다. 뱀은 처음에 오른쪽을 향한다. 뱀.. PS(Problem Solving)/BOJ 2022. 7. 5.

• [백준/BOJ] 9663번: N-Queen https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 해설 문제 그대로 퀸 N개가 서로 공격할 수 없게 놓으면 된다.이렇게 놓기 위한 조건으로는 같은 행 또.. PS(Problem Solving)/BOJ 2022. 7. 4.

• [백준/BOJ] 1202번: 보석 도둑 https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 문제 세계적인 도둑 상덕이는 보석점을 털기로 결심했다. 상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다. 상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그.. PS(Problem Solving)/BOJ 2022. 7. 3.

• [백준/BOJ] 14442번: 벽 부수고 이동하기 2 https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는.. PS(Problem Solving)/BOJ 2022. 6. 29.

• [백준/BOJ] 12851번: 숨바꼭질 3 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다. 수빈이와.. PS(Problem Solving)/BOJ 2022. 6. 24.

• [백준/BOJ] 12851번: 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈.. PS(Problem Solving)/BOJ 2022. 6. 23.

• [백준/BOJ] 1987번: 알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 .. PS(Problem Solving)/BOJ 2022. 6. 23.

• [백준/BOJ] 10026번: 적록색약 https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은.. PS(Problem Solving)/BOJ 2022. 6. 21.

• [백준/BOJ] 4963번: 섬의 개수 https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사각형이다. 두 정사각형이 같은 섬에 있으려면, 한 정사각형에서 다른 정사각형으로 걸어서 갈 수 있는 경로가 있어야 한다. 지도는 바다로 둘러싸여 있으며, 지도 밖으로 나갈 수 없다. 입력 입력은 여러 개의 테.. PS(Problem Solving)/BOJ 2022. 6. 20.