be programmer

https://www.acmicpc.net/problem/16947 전형적인 탐색 문제이다.문제를 읽어보면 사이클을 dfs, 재귀 등 방법으로 찾고, 사이클로부터 파생되는 지선의 깊이를 구해서 출력하면 된다.나는 사이클을 dfs로 찾고, 지선의 깊이를 bfs로 찾았다. 사이클을 찾을땐 재귀로 찾는게 편하다 생각했다. 왜냐하면 나한테 익숙했고, 처음 지점을 기억하고 계속 재귀하기에 사이클의 시작점?을 찾는덴 dfs가 가장 적합하다고 여겼기 때문이다. 사이클을 찾으면 true를 반환하여 탐색을 그만 둔다. 아닐 경우 탐색을 해야하기에 사이클 탐색 배열에 false를 준다. 이외 사이클에서 파생된 지선의 깊이는 bfs로 찾았다. 사이클 찾기public static boolean dfs(int prev, int..

https://www.acmicpc.net/problem/2469 구현 문제이다. 구현 문제를 좋아하지는 않는데 왜냐하면 실제 구현해서 굴러가는 프로그램들 마냥 예외처리를 해야하는 부분이 있고, 무턱대고 구현하기보다는 면밀히 생각해야 하는 부분이 존재하기 때문이다. 문제에 나름 친절히 설명된 사다리 타기의 성질을 이용하여 -가 뜰 경우 swap(차피 하나씩 하나, 여러개 하나 반댓쪽으로 이동되는건 똑같으니), *가 떴을경우 keep going 하면 됨이것을 시작지점, 도착지점에서 시행해서 ?가 뜨는지점에서 만난 후 문자열 비교를 해주면 됨.나는 막판 예외처리하고 swap 해줘야하는걸 생각 못해서 한번만에 맞추지는 못했는데, 그렇게 해야함. swap 안하면 ?지역에서는 -가 있어야 하는 지역임에도 사다리타..

목차1. 정규문법과 정규 언어2. 정규 표현 1. 정규 문법과 정규 언어정규 문법이란?노엄 촘스키가 생성 규칙 형태에 분류한 네가지 문법 중 가장 간단한 레벨에 해당하는 문법 형태생성 규칙의 오른쪽에 위치한 논-터미널 심볼의위치에 따라 구분됨.우선형 문법L -> tB, L->t좌선형 문법L ->Bt, L->t where L,B Vn and t Vt*정규문법에서 우선형 문법과 좌선형 문법의 속성- 모든 우선형 문법은 동등한 좌선형 문법을 만들수 있고, 그 역도 가능- 단 한 문법의생성 규칙이 우선형, 좌선형 형태 규칙이 혼합되어 있으면, 정규문법이 아님 정규문법의 활용컴파일러의 어휘 분석 단계에서 입력 프로그램을 구성하는 토큰의 구조를 정의하는데 주로 사용됨1. 토큰의 구조는 간단하므로 정규 문법으로도 ..

목차1. 언어2. 문법3. 문법의 분류 1. 언어언어의 정의1) 알파벳 - 심벌들의 유한 집합 - ex) t1 = {ㄱ, ㄴ, ㄷ ... }, t2 = {auto, break, while, case ...}2) 스트링 - 어느 알파벳에 정의된 하나 이상의 심벌을 나열한 시퀀스 - 위의 t1의 경우 ㄱㄴ, ㄱ, ㄴ, ㄱㄱㄱ 등 t로 만들수 있는 스트링3) 스트링의 길이 - 스트링의 심벌의 갯수, 스트링 t1의 길이는 |t1|로 표시4) 영 스트링 - ε 어떠한 심벌도 포함하지 않는 스트링5) + : 1번이상 등장, * : 0번이상 등장6) 언어 : 모든 스트링들의 집합t3 = {a^nb^n | n >= 1}, {ww^n | w 추가 정의1) 스트링의 교환법칙은 성립하지 않는다.2) 스트링 a의 a^R은 ..

컴퓨터에서 번역기의 정의한 프로그래밍 언어로 작성된 프로그램을 입력으로 받아 그와 동등한 의미를 갖는 다른 프로그래밍 언어로 된 프로그램을 출력하는 시스템 소프트웨어 예시) 컴파일러, 인터프리터, 전처리기(C++에서 #)컴파일러란?프로그래밍 언어를 사용하여 작성된 소스코드를 특정 기계에서 실행 가능한 목적 코드로 변환하는 프로그램기본 구조전단부   소스 언어에 종속적   소스 언어에 관계되는 부분으로 소스 언어를 분석하고 중간 코드를 생성후단부   목적 기계에 종속적   전단부에 생성된 중간 코드를 특정 기계를 위한 목적 코드로 변환크로스 컴파일러정의 : A라는 기계에서 실행 가능한 컴파일러가 B라는 기계에서 실행 가능한 목적 코드를 생성하는 컴파일러주로 새롭게 등장한 기종에 대한 프로그램 개발시 사용e..

https://www.acmicpc.net/problem/9921 영어 해석 이슈로 베낭 문제로 오인하여 풀었다. 전형적인 동전 DP 문제였고, BFS + DP로도 해결 할수도 있다고 한다. 최소의 가짓수를 사용하여 해당 가치를 만들수 있는지를 판별해주고, 된다면 최소의 가짓수를 출력해내면 된다.BFS로도 풀어보겠다. 필자는 베낭문제인줄 알고 헛짓 하느라 금방 푸는걸 1시간이나 넘게 걸려 풀었다. 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp..

https://www.acmicpc.net/problem/11085 UnionFind(분리 집합) 문제이다. 사실 선지만 가지고는 이 문제가 정확히 뭘 말하고 싶은지 이해하기 어려워서 선지 보는데 문제 풀기로 정해둔 시간을 모두 다 날렸다.첫 줄에 Baekjoon World의 국왕이 정한 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 출력합니다. 부분이 이해가 안 가는 부분이었는데, 그냥 정렬 해 둔 후 그에 맞는것을 찾으면 되는 것이었고 실제로 그렇게 풀었다.간선을 w순으로 우선 순위 큐를 통해 정렬하고 w가 큰 간선부터, 시작과 끝점의 find가 같지 않다면 union 연산을 한다. 종료조건은 find(C) == find(V)이다. 가장 최근 연결했던 간선의 w를 출력해서 풀었다.큐를 정렬하는..

바로 이전 글에서 설명한 Future는 함수가 끝나는 순간이 함수의 완료 순간이다.하지만, Stream은 직접적으로 닫히는 순간이 완료 순간이다.데이터를 받아서 앱에 해당 데이터를 노출시켜야 하는 상황에서는 언제 네트워크에서 데이터를 다 받을지 알기 어렵다. 네트워크가 좋을수도 있고, 나쁠수도 있기 때문이다. 이런 문제를 스트림은 데이터를 생성하는곳과 소비하는 곳을 다르게 두어 이 문제를 해결할 수 있다.코드를 통해 설명하면,Future sumStream(Stream stream) async { var sum = 0; await for (var value in stream) { sum += value; } return sum;}Stream countStream(int n) async* { ..