백준41 [백준] Swift 1300 k번째 수 BS(Bineary Search) 문제 : 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차원 N*N 배열 값을 1차원 N*N배열로 바꾸었을때 k번째 인덱스의 값(m)을 구하는 문제였다. 예를 들어서 N = 4 배열이 있을때, 이를 1차원 배열로 늘여보면 이렇게 될 것이고 그러므로 이를 이분 탐색으로 접근 할 수 있는 것이다. 사실 선형 탐색으로 찾으려 .. 2022. 3. 31. [백준] 1516 게임 개발 문제 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 : 먼저 개발할 것이 있다는 점에서 위상 정렬 문제다. 👉🏻 위상정렬 알고리즘 자신의 노드로 향하는 다른 노드가 있을때 그 노드를 v[자신].push_back(향하는 노드)로 넣어줬다. 그리고 향하는 들어오는 노드의 값을 증가시켜줬다. (개념과 반대다) 즉 indegeree[향하는노드]++ 따라서 값을 도식화 하면 아래와 같다. 그리고 indegree가 0인 값부터 vec.. 2022. 3. 3. [백준] 2630 색종이 만들기 문제 : https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net 풀이 : 다음과 같이 색종이가 있을때 정사각형 크기로 나눠 색종이가 모두 파란면을 또는 하얀면을 띄게 하는 작은 정사각형 색종이로 만들고 만들어진 흰 색종이 개수, 파란 색종이 개수를 출력하는 문제다. 즉 분할 정복을 통해 탑다운 방식으로 나눠진 색종이가 조건에 맞는 색종이인지 검사하면 된다. 색종이 크기가 1x1일때까지 반복하므로 재귀를 통해 해결할수 있었다... 2022. 2. 24. [백준] 3020 개똥벌레 prefix sum(누적합) 문제 : https://www.acmicpc.net/problem/3020 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 분석 : 1. 석순과 종유석의 구분은 짝수인지 홀수인지다. 따라서 개똥벌레가 높이 1인 곳을 지난다면 종유석은 1인 높이, 석순은 H -1 인 높이를 동시에 지난다고 생각하면 된다. 2. 석순끼리의 (또는 종유석끼리의) 순서 바뀜은 상관이 없다. 개똥벌레는 N 길이를 통과하야 하기 때문이다. 석순의 길이만큼 가진 석순 개수를 배열에 저장한다. (종유석도 똑같다) 3. 높이가 H일때 개똥벌레는.. 2022. 2. 21. [백준] 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. [백준] 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. [백준] 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 다음
