분류 전체보기 (169) 썸네일형 리스트형 [백준] 1926_그림 BFS 실1 (Python3) 2024. 11. 7. 23:03 백준 BFS 먹으러 옴 https://www.acmicpc.net/problem/1926 실1이라서 보자마자 바로 BFS가 머리에 그려지는 수준 이중 for문으로 이차원 배열을 탐색하다가1을 발견하면, 그때부터 bfs를 시작한다 해당 시작점을 기준으로 상하좌우 노드를 탐색해서, 만약 1이라면 q에 넣어준다q에 더 이상 탐색할 점이 남지 않을 때까지 while문을 돌린다while문을 돌릴 때마다 그림의 크기+1을 해주고탐색이 다 끝나면 그림 크기를 return한다 이거 visited로 탐색 여부 볼 수 있을까 싶어서 visited 이차원 배열을 만들어서 False로 초기화 했는데중간에 좀 꼬여서 버렸다 다른 블로그 글을 찾아보니그냥 배열을 탐색하면서 그림 크기 더해주기에 사용했으면 1을 0으로 바꿔서 vi.. [프로그래머스] 네트워크-BFS/DFS lv.3 (Python3) 2024. 11. 7. 16:59 제가 그래프에 많이 약해서 그래프 좀 풀어보겠습니다.https://school.programmers.co.kr/learn/courses/30/lessons/43162 네트워크 2차원 배열이 있고, 각 열마다 어떤 번호와 연결되어 있는지 1, 연결되어 있지 않은지 0으로 표시합니다. A-B, B-C 연결에서 A와 C는 B를 통해 간접적으로 연결됩니다. 이런 간접 연결을 포함해서 같은 네트워크 상에 있는 컴퓨터의 최대 개수를 구합니다 BFS 기본 구조는 from collections import deque로 deque를 불러오고일단 q에 첫 번째 원소를 집어넣고while q를 돌려서 q가 빌떄까지 계속한다그 안에서 for문을 돌려 q에서 popleft 한 원소에 대해그 원소 주변에 있는 조건에 해당하는 원소.. [프로그래머스] 카펫 - 완전탐색 (C++) lv2 2024. 11. 6. 12:33 C++ 연습! 카펫의 가운데는 노란색, 테두리 1줄은 갈색갈색과 노란색의 cell 개수만 보고 카펫의 가로, 세로 크기를 알 수 있을까? 아이디어: 노란색의 가로+2 = 갈색 가로, 노란색 세로+2 = 갈색 세로 총 cell 개수 = 노랑+갈색; brown 가로세로 = 카펫 가로세로임그러면 brown의 가로세로를 순차적으로 점검하며 possibility를 분석하면 된다 brown 세로 길이 최솟값 = 3왜냐면 yellow의 최소 세로가 1임. 그리고 위아래로 brown cell이 1개씩 붙으니까 3 brown 세로 길이 최대 = 루트(총 cell 개수)왜냐면 총 개수를 어떻게 구겨넣든 일단 가로=세로가 되는 지점에서 멈춰야 되니까(그 이상으로 넘어가면, 그 이전에서 살펴본 것을 가로, 세로 길이만 바꿔서.. [프로그래머스] 소수 찾기 - 완전탐색 (C++) 2024. 11. 6. 11:48 c++언어에 익숙해지기파이썬 원툴 코테에서 c++ 코테로 전이하는 과정... (삽질 과정 모두 포함)(정답만 있는 포스트 아님) 한 자리 숫자가 적힌 종이조각이 흩어져 있다.흩어진 종이조각을 붙여 소수를 몇 개 만들 수 있는지 알아내자종이 조각에 적힌 문자열 numbers가 주어졌을 때종이조각으로 만들 수 있는 소수가 몇 개인지 return하자 아이디어1: 일단 str 형태로 숫자가 줄줄 붙어서 나온다.파이썬이었다면 list에 담아서 배열로 만들었을 것 같다c++은 어떻게 할 수 있을까? str.copy()를 사용해보자 #include #include #include #include using namespace std;int solution(string numbers) { int answer = .. [프로그래머스] 최소직사각형 - 완전탐색 (c++) 2024. 11. 6. 10:34 언어제한 코테 대비를 위해 C++과 친해지는 시간을 가져보자 lv.1 가장 간단한 문제! 파이썬으로 코테 준비를 해왔는데,후배가 c++이 파이썬 list랑 비슷한 기능을 지원해서 괜찮다길래 써보려고 함 https://school.programmers.co.kr/learn/courses/30/lessons/86491?language=cpp 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 가로 세로 길이가 각각 다른 명함이 있고이 명함들을 다 담을 수 있는 최소 가로세로를 가진 명함 케이스의 너비를 구해야 한다 여기에서 각 배열 요소의 sizes[i][0]과 sizes[i][1]의 각 max값을 구하면 편할.. Lec08. Syntax Analysis (4) - 10주차 1강 2024. 11. 5. 21:51 11월 4일 10주차 1강* 개인 공부를 위해 정리한 것입니다. 정확한 내용은 꼭 본인이 공부하는 교재를 참고하시기 바랍니다. LR Parsing with Ambiguous Grammars1. LR Parsing with Ambiguous GrammarsLR 파싱은 LL 파서보다 더 복잡한 문법 구조를 처리할 수 있음. LR>>LLAmbiguous 문법의 문제LR 기술을 적용하려면 ambiguity를 제거해야 함 E→E+E∣E∗E∣(E)∣id 이와 같은 문법은 E→E+T∣T, T→T∗F∣F, F→(E)∣id 이와 같이 바꿔야 함unambiguous 하게 문법을 작성하는 건 어렵고, 불가능한 경우도 있음LR 기술은 disambiguating rules 를 바탕으로 ambiguous grammer에 적용될 .. Lec07. Syntax Analysis (3) - 8주차 1강/2강 2024. 10. 25. 20:24 10월 21일 8주차 1강 + 10월 23일 8주차 2강 1. Bottom-Up ParsingBottom up parsing: 입력된 문자열에서 시작해 점차 상위로 올라가며 parse tree를 구성하는 과정leaf에서 시작해서 root로 작업이 진행됨문자열 w를 start symbol을 사용해서 점점 reducing하는 과정Reduction: production rule를 역방향으로 적용. production의 body를 head로 교체함id*id 예시에서, id*id가 순차적으로 축소되어 최종적으로 시작 기호 E로 변환 됨.Rightmost Derivation의 역순으로 구성됨. production rule을 역으로 적용해서 최종적으로 start symbol로 도달함.Expression Grammar.. [프로그래머스] 타겟넘버 - BFS/DFS 2024. 10. 24. 23:35 알고리즘 고득점 키트 BFS/DFS lv2 타겟넘버 숫자 배열이 주어지고, 목표 값이 있음각 숫자를 더하거나 빼서 목표 값을 만들고, 총 목표 값을 몇 가지로 만들 수 있는지 return하면 됨 혼자 못풀었음풀이 참고함 BFS 풀이 모든 연산을 저장하는 leaves 배열이 존재for문을 돌며 각 숫자를 탐색 leaves 안에 있는 모든 숫자들에 대해서, 현재 숫자를 더하거나 뺀 값을 임시 배열에 저장함 leaves 배열 값을 임시 배열값으로 치환함 #어차피 숫자 순서를 바꾸거나 하는 일은 없으니까 #순서대로 각 숫자를 더하거나 뺐을 때 경우를 다 저장해서 나중에 target 값인지만 확인하면 됨 for문 돌며 leaves안에 있는 값 살펴봄. target값이면 answer +1 def .. 이전 1 ··· 16 17 18 19 20 21 22 다음
