백준 문제풀이 (31) 썸네일형 리스트형 [백준(BOJ)/C++] 14713번: 앵무새 - 코딩밥상 https://www.acmicpc.net/problem/14713 14713번: 앵무새 자가용 비행기를 타고 세계 일주를 하던 pps789와 cseteram은 어느 날 엔진 고장으로 인해 이름 모를 섬에 불시착하게 된다. 그들은 이 섬을 탐험하는 도중 아주 신기한 사실을 알게 되었는데, 바로 www.acmicpc.net 접근 방법 이 문제의 주안점은 앵무새의 문장마다 단어의 순서대로 결과값과 비교하여 단어들이 올 수 있는지 비교하는 것이었다. 즉 앵무새의 문장에서 단어들이 선입 선출(FIFO)로 나올 수 있다면 Possible, 없다면 Impossible인 것이다. 따라서 선입 선출을 다루기에 적합한 자료구조인 큐를 이용하였고 앵무새의 문장을 각각 따로 구분하여 넣어줄 자료구조로 벡터를 선택했다. ge.. [백준(BOJ)/C++] 1966번: 프린터 큐 - 코딩밥상 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 접근방법 처음엔 단순히 파일이 들어오는 순서대로 인덱스값과 우선순위 값을 pair로 저장하여 큐에 넣어주고 큐의 front값의 우선순위값과 비교하여 더 높은 우선순위가 등장하면 큐에 다시 넣어주고 우선순위가 더 높은 파일이 없는 경우에 큐에서 빼주는 식으로 코드를 짰다 (오답 코드) 하지만 이렇게 되면 우선순위값이 동일한 경우에는 순서가 바뀌게 된다. 이렇게 한참을 어디에서 틀렸는지 고민하다가 디버깅.. [백준(BOJ)/C++] 1918번: 후위 표기식 - 코딩밥상 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 접근방법 대표적인 스택 자료구조를 활용하여 풀 수 있는 문제이다. 우리가 흔히 알고있는 계산식은 중위 표기식인데 이는 피연산자 사이에 연산자가 들어가는 구조이지만, 이 문제에서 제시하는 후위 표기식은 피연산자 뒤에 연산자를 나타내는 방식으로 컴퓨터 논리 순서에 용이하게 식을 바꾸는 문제이다. 즉 중위표기식에서 연산자만 따로 스택에 관리하여 후위 표기식으로 풀어쓰는 방식이다. 알고리즘 -입력 받.. [백준(BOJ)/C++] 13335번: 트럭 - 코딩밥상 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 접근 방법 처음 이 문제를 봤을땐 단순히 트럭들을 배열에 넣어주고 다리위에 올라가고 내려오는 값을 변수에 쌓아주었다. 그 과정에서 인덱스로 값을 관리하는데에 한계가 있었고, 트럭이 입력 순서대로 들어가고 나가기 때문에 선입선출인 자료구조인 queue를 활용했다. 트러블 슈팅 큐로 트럭들을 넣어주고 다리위 무게를 받고 무게가 넘어가면 다리위에 올라간 .. [백준(BOJ)/C++] 11724번: 연결 요소의 개수 - 코딩밥상 https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 스터디에서 간략하게 알고리즘 토론을 한 문제여서 어떻게 접근할 지는 명확했다. 각 노드들을 한번씩 dfs를 돌리고 방문처리 해주는데, 만약 들린 노드가 방문하지 않은 상태라면 그 노드는 다른 요소인 것이다. 왜냐하면 연결된 노드는 첫 dfs를 돌린 노드를 통해 방문 처리가 되었을 것이다. 이를 코드를 .. [백준(BOJ)/C++] 2178번: 미로 탐색 - 코딩밥상 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 미로문제는 대표적인 bfs란것을 알고 있었기에 바로 문제 풀이에 들어갔는데, 처음부터 막힌 부분이 상하좌우의 결과에 따라 값이 결정된다는 것이었다. 이게 스터디때 배웠던 알고리즘이구나 생각했다. 미로를 2차원 평면 좌표로 생각하고 x,y값을 pair를 사용하여 관리했다. bfs를 활용하기 위해 큐를 만들어 주고 다음과 같이 BFS를 사용하여 x,y값을 바꿔가며 가능한 지점으로 이동하면 되는것이다.. [백준(BOJ)/C++] 1260번: DFS와 BFS - 코딩밥상 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 정점과 간선의 갯수와 시작하는 지점까지 알려주는 친절한 문제이다. 기본적인 DFS와 BFS의 개념을 물어보는 기본 문제인데, 이 문제를 통해 알고는 있었지만 헷갈리던 개념들과 동작원리를 좀 더 세세하게 익힐 수 있었다. 우선 수업에서 입력받는 값들을 보면 헷갈릴거라고 하셨는데 문제를 접하고 나서야 그게 무슨 의미인가 알 수 있.. [백준(BOJ)/C++] 1932번: 정수 삼각형 - 코딩밥상 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 접근 방법, 논리 흐름(알고리즘) 우선 점차적으로 내려갈 수 있는 경우의 수를 생각해 보았고, 각 점마다 최댓값을 저장하기에 전 칸을 더하여 저장하는 dp로 풀 수 있다고 생각했다. 문제를 보고 그림을 그려보고 가능한 길을 모두 그려본 결과 다음과 같은 패턴을 발견할 수 있었다. 가장 왼쪽과 가장 오른쪽 즉 삼각형의 변에 해당하는 끝 점들은 올라가는 경우의 수가 바로 위점 하나이다. 반면 끝 점들이 아닌 중간 점들의 경우 왼쪽과 오른쪽으로 올라 가는 경우가 있는데, 최.. 이전 1 2 3 4 다음
