본문 바로가기

Algorithm🐰/백준61

[백준] 7576 토마토 BFS 문제 : https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 분석 : 이런식으로 토마토 농장이 존재 할때 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸 을 의미한다. 익은 토마토 중심으로 상하좌우로 하루마다 토마토가 익는데 몇일이면 농장 내 모든 토마토가 익는지 날짜를 출력하는 문제였다. 우선 토마토 농장을 탐색한다는 점에서 BFS, DFS로 접근해야 한다 생각했고 탐색을 하면서 방문하지 .. 2021. 12. 10.

[백준] 15681 트리와 쿼리 DP + DFS 문제 : https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 분석 : 밑에 알고리즘 분류를 보았을 때 '트리에서의 DP' 가 눈에 띄었다. 트리에서의 DP ? 그게 뭐지 그러면 트리 자료 구조를 구현해야 하는 건가 ... 싶어 다른 블로그들을 참고하였다. https://chanhuiseok.github.io/posts/algo-56/ 알고리즘 - 트리 DP 문제 풀기(트리에서의 Dyna.. 2021. 9. 9.

[백준] 1463 1로 만들기 DP 문제 : https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 분석 : 재귀와 메모제이션을 이용해 풀었다. 처음에 if (d[n] > 0) return d[n]; 부분을 넣어주지 않아 시간 초과가 났었고 d[1]일때 n == 1일때 처리를 return 0으로 처리 해주지 않아 100퍼에서 에러로 헤맸다 c++ 코드 : // // 1463_makeOne.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/08/23. // #include #include #include using namespace std; int d[10000.. 2021. 8. 23.

[백준] 5567 결혼식 구현 문제 : https://www.acmicpc.net/problem/5567 5567번: 결혼식 2와 3은 상근이의 친구이다. 또, 3과 4는 친구이기 때문에, 4는 상근이의 친구의 친구이다. 5와 6은 친구도 아니고, 친구의 친구도 아니다. 따라서 2,3,4 3명의 친구를 결혼식에 초대한다. www.acmicpc.net 분석 : 결혼식에 올 동기들 중 내 친구, 내 친구의 친구만 초대 하려면 몇명 초대 해야 묻는 문제였다. 친구 관계를 friends vector에 넣어 friends[친구] = ["친구의 친구들 리스트"] 를 찾으면 되는 문제지만 * 주의 해야 할 점이 있다. 친구의 친구가 내 친구일 수도 있기 때문이다. 따라서 우선 내 친구들만 queue에 넣어 result 값을 증가시켜준 다음 que.. 2021. 6. 13.

[백준] 2579 계단 오르기 DP 문제 : https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 분석 : 계단이 있을 시 계단을 오르는데 규칙이 있다 --> 점화식이군 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. stairArr [i] = i번째 계단의 값 d [i] = .. 2021. 6. 13.

[백준] 1149 RGB 거리 DP ㅇ문제 : www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 분석 : rgb 색깔을 양 옆 집마다 겹치지 않게 색칠하는데 그 최소 비용을 구하는 문제다. dp 배열은 2차원 배열로 이루어져 있으며 dp[i][0], dp[i][1], dp[i][2]는 각각 i번째 집까지 색칠할때 0-빨간색 최소 비용,1-노란색 최소 비용,2-파란색 최소 비용을 저장하고 있는 배열이다. 예를 들어 dp[1][1]은 이전 0번째 집을 색칠할때 드는 최소 비용에.. 2021. 5. 8.

[백준] 16236 아기 상어 DFS, Priority-Queue 문제 : www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 설명 : -> 아기 상어가 몇초 동안 물고기 잡아먹을 수 있는지 출력하시오 공간 n = 4 0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어가 움직일 수 있는 조건 1. 자기 주변에 인접한 물고기 && 먹을 수 있다면 가장 인접한 물고기를 먹으러 간다. 2. 인접한 물고기가 여러 마리라면 가장 위에 있는 물고기, 가장 왼쪽에 있는 물고기.. 2021. 5. 6.

[백준] 9095 1,2,3 더하기 DP 문제 : www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 분석 : 점화식을 세우면 간단히 해결할 수 있는 문제였다! 큰 문제가 작은 문제로 나누어지는 전형적인 dp 문제였고 1, 2, 3의 합으로 나타낸다는 것은 1일때 1 2일때 1 + 1 2 3일때 1 + 1 + 1 1 + 1 + 2 1 + 2 + 1 1 + 1 + 2 1 + 3 과 같이 나타내어지는 것을 의미한다. n = 4일 경우 나타내어지는 경우의 수를 memo[4]라고 하자 그럴때 경우의 수는 1 + memo[3] 2 + memo[2] 3 + memo[1] 일 것이다. 따라서 점화식은 memo[n.. 2021. 5. 4.

[백준] 1937 욕심쟁이 판다 🐼 DP 문제 : www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 분석 : n x n 판다 집이 있으면 판다는 상하 좌우로 움직일 수 있고 현 위치에서 다음 날이 될때 이동하는데 이동하는 칸에 먹이가 더 많아야 움직일 수 있는 욕심쟁이 친구다. 그래서 최대로 살 수 (?) 있게 하는 날을 구하는 문제였다. arr배열에 밥을 넣어주고 dp를 동시에 0으로 초기화 시켜준 뒤 dp 함수를 돌면서 최대로 살 수 있는 maxRice (maxLife 변수가 더 적절할듯.. 2021. 5. 2.

[백준] 13460 구슬 찾기2 BFS 문제 : www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 분석 : 이 문제는 삼성 어쩌구 역량 기출 문제였다. 아직 기출 문제에 대한 감이 없다. 기업 코딩테스트는 다 기업 코딩테스트 같아서 말이다 하하 어쩼든 그래프 이론을 복습하는 와중에 한번 풀어볼까 ? 해서 도전하게 되었다. 문제를 읽다가 이해가 되면 문제 포기를 못하겠다. input 받는것만 만들고 다른 블로그님들의 글을 참고하여 겨우 겨우 풀었다. .. 2021. 4. 22.

[백준] 2583 영역 구하기 DFS 문제: www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 분석 : 전 2667(단지 번호 붙이기)번와 비슷한 문제이나 주어지는 입력값이 조금 다르다 ! 문제를 보면 왼쪽 아래 꼭짓점과 오른쪽 위 꼭짓점의 좌표가 주어지고 이에따라 가지는 값의 범위를 구해 사각형을 1로 초기화 시켜 주었다. 그러면 남은 map의 좌표는 0이 될꺼고 dfs를 돌며 맵의 크기를 구하되 dfs_all로 끊어져 있는 곳들에 대해 반복적으로 수행하면 된다! c++ 코드.. 2021. 4. 22.

[백준] 1697 숨바꼭질 BFS 문제 : www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 분석 : 풀지 못했던 문제를 풀었다 🤭 처음엔 재귀로 접근하다 가까운 거리먼저 탐색 해야 한다는 것을 깨달았다. 최단 거리를 찾는 bfs 문제이므로 queue를 사용했고 수빈이의 움직임 moving 배열에 넣은 뒤 visit에 움직인 거리만큼을 +1 해줘서 누적시켰다. 그리고 k에 도달했을 때 누적된 값을 출력시키면 끝!! c++ 코드 : // // 1697_hide_seek.. 2021. 4. 21.

[백준] 9012 괄호 string 문제 : www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 분석: 유제를 본 적이 있어 어떻게 접근하면 효율적일까 고민하던 중 stack으로 푼 방식이 획기적이었다!! c++ 코드 : // // bracket.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/21. // #include #include #include using namespace std; int N; bool isBr.. 2021. 4. 21.

[백준] 1110 더하기 사이클 string 문제 : www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 분석 : 도움 없이 풀 수 있는거 보니 내 수준은 브론즈인가보다 ... 앞으로 더 발전해야지 주어진 예시만으로 조건을 생각한다면 규칙을 발견해 풀수 있는 문제였다. 풀이 : // // 1110_addCycle.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/21. // #include #include #include using namespa.. 2021. 4. 21.

[백준] 2309 일곱 난쟁이 backtracking 문제 : www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 분석 : 브론즈였음에도 어려웠다.. 앞으로 브루트 포스, 백트래킹쪽을 좀 더 공부해 보아야겠다. 종만북에서 보았던 아이디어를 가지고 문제 접근을 하였다. 각 난쟁이들은 100을 포함하는데 속하거나 안 속하거나 둘중 하나이다. 그러므로 모든 난쟁이들을 탐색하는데 return 문을 만나 재귀가 끝나게 되면 visit를 false로 해 속하지 않게끔 만들고 다른 원소들을 탐색하는 것이다. 이렇게 하여 속하는 원소들만.. 2021. 4. 6.

[백준] 1477 휴게소 세우기 문제 : www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 www.acmicpc.net 분석 : 풀땐 몰랐는데 예전 라우터 문제와 비슷한 방식의 문제다!! 생각한 틀린 방법 : for문을 한번씩 돌때마다 가장 간격이 큰 휴게소 지점을 반으로 나눠 그 지점에 휴게소를 세운다. // // 1477_rest.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/04/05. // #include #include #include #i.. 2021. 4. 5.

[백준] 치즈 2636 bfs 문제 : www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 분석 : 이 문제는 생각하기 복잡했지만 코드를 보니 단숨에 이해가 가는 듯 한 문제였다. 치즈의 겉면만 시간에 따라 어떻게 공기로 바꿀까 문제 그대로의 흐름을 따라 문제를 풀려 했지만 그렇게 되면은 안쪽의 공기와 바깥쪽의 공기가 구분이 되지 않아 순서가 엉망이 될 수도 있을 것 같았다. 같이 스터디 하는 언니의 코드 설명으로 치즈 입장에서가 아닌 공기 입장에서 다음 공기가 될 것인지 아닌지 판단하면 안쪽의 공기를 생각하지.. 2021. 4. 2.

[백준] 14502 연구소 bfs 문제 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 분석 : c++ 코드 : // // 14502_lab.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong on 2021/02/07. // #include #include #include #include #include #include #include using namespace std; int arr[8][8]; int c_arr[8][8]; int N, M; int zero_cnt; in.. 2021. 4. 1.

[백준] 11779 최소 비용 구하기2 dijkstra 문제 : www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 분석 : 이번 문제는 전 문제 1916번 2021.03.10 - [Algorithm🐰/백준] - [백준] 1916 최소비용 구하기 dijkstra 에 거쳐간 노드를 출력할 수 있도록 추가하는 작업이 필요하다. 따라서 while 문 안 for 문에 t 배열을 하나 추가해 그 전 노드를 인덱스 값으로 현재 노드의 값을 넣어주고 그 전 pop해온 노드(now)를 값으로 받도록.. 2021. 3. 10.

[백준] 1916 최소비용 구하기 dijkstra 문제 : www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 분석 : 이 문제 역시 대표적인 다익스트라 알고리즘 문제이다. 1753번 문제 2021.03.10 - [Algorithm🐰/백준] - [백준] 1753 최단 경로 dijkstra 에 가는 마지막 노드 end 만을 출력하게끔 변형하면 된다. c++ 코드 : // // 1916_min_cost.cpp // SOMA👩🏻‍💻 // // Created by JoSoJeong o.. 2021. 3. 10.

이전 1 2 3 4 다음

티스토리툴바