코달

문제https://www.acmicpc.net/problem/1285 1285번: 동전 뒤집기첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위www.acmicpc.net 풀이처음엔 동전의 배열을 노드로 하는 그래프의 DFS 탐색으로 풀었다. 현재 노드는 현재 동전 배열이고, 인접한 노드들은 모든 행, 모든 열을 뒤집는 경우의 동전 배열이다.이런 식으로 풀어도 답은 나오지만, 메모리 초과 혹은 시간초과가 발생한다. 결국 다른 블로그 글을 보고 깨달았다.https://please-amend.tistory.com/175 백준 1285번 동전 뒤집기 - C++ 풀이1..

문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 풀이 보드 자체가 탐색할 노드가 되어야 한다는 생각을 하기 어려웠다. 처음엔 보드에서 0을 움직이고 현재 보드가 정렬된 상태인지 검사하며 탐색할 생각을 했으나, 퍼즐을 가장 빠르게 푸는 방법을 생각해내지 못했다. 이 문제는 보드의 상태마다 0을 움직일 수 있는 경우의 수가 인접한 노드로 존재하는 그래프를 떠올리고, 모든 숫자가 제자리에 위치한 상태의 노드를 탐색해야하는 문제였다. 보드는 vector에 저장했다. 탐색에는 BFS알고리즘을 이용했다. 그 이유는 가장 빠르게..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 무엇보다 트리의 특성을 잘 이용하는 것이 중요한 문제입니다. 트리는 두 점 사이의 경로가 단 1개입니다. 따라서 가장 멀리 떨어진 두 점 (a, b)사이의 길이가 트리의 지름이 됩니다. 그렇다면 문제는 가장 멀리 떨어진 두 점 a와 b를 어떻게 찾을 것인가? 를 고민해야 합니다. 아래는 제가 맘대로 만든 트리입니다. 각 노드에는 번호가 적혀있고, 연결한 선분에는 길이가 ..

이름 숨김이란, 어떤 멤버 A가 있을 때, 중첩된 선언 영역 혹은 파생 클래스에서 같은 이름의 멤버를 선언할 경우, 멤버 A가 무시되는 규칙입니다. https://www.ibm.com/docs/en/i/7.5?topic=scope-name-hiding-c-only Name hiding (C++ only) If a class name or enumeration name is in scope and not hidden, it is visible. A class name or enumeration name can be hidden by an explicit declaration of that same name — as an object, function, or enumerator — in a nested de..

Scanner란? Scanner는 소스코드의 모든 글자들을 읽어(Scan) Token의 형태로 이해하는 것을 말합니다. 소스코드를 Scanner에 넣으면 Token 목록, 즉 TokenList가 출력됩니다. 여기서 말하는 Token이란, 소스 코드 상에서 의미가 있는 단어 혹은 글자를 말합니다. 예를 들어 다음 c++ 소스 코드 상에서 '^'라는 글자는 아무 의미 없지만, 그 외에 int, main, (, ), {, } 와 같은 글자들은 모두 의미가 있고 하는 역할이 있습니다. int main() { ^ } Scanner는 이렇게 의미 있는 글자들을 단어로 묶어 하나의 Token으로 만듭니다. 그리고 모든 글자를 읽어서 Token List를 만듭니다. 반대로 의미 없는 글자를 발견하면 컴파일 에러를 발생..

다형성 다형성이란 하나의 객체가 여러 타입을 가질 수 있는 것을 말합니다. 반대로 하나의 타입이 여러 타입의 객체를 참조할 수 있는 것도 다형성입니다. 다형성은 상속과 오버라이딩을 통해 구현될 수 있습니다. 오버라이딩 클래스의 멤버 함수는 파생 클래스에서 오버라이딩 될 수 있습니다. 즉, 같은 모습의 함수가 여러 개 존재할 수 있습니다. 같은 모습의 함수이지만, 여러 개의 구현이 존재할 수 있습니다. 그런데, 똑같이 생긴 함수를 똑같은 형식으로 호출한다면, 자식과 부모 중 어떤 함수를 호출해야 할까요? class Parent { public: void Func() { m_i = 1; } int m_i; }; class Child : public Parent { public: void Func() { m_..

1. 멤버 객체 선언 시, 원하는 생성자를 호출하는 방법은? Initialize() 함수나 생성자의 블록 내에서 대입 생성 시 생성자가 두 번 호출되어 비효율적이지만, 아래와 같이 생성자의 멤버 이니셜라이저를 사용하거나, 멤버 변수 선언 옆에 대입 생성자를 호출하면 생성자가 한 번만 호출된다. class A { public: A(){} A(int _i){} } class B { public: B() : a(10){} // 이니셜라이저 사용 public: A a = A(10);// 혹은 대입 생성 } 2. 부모에서 멤버로 선언한 객체의 생성을 원하는 생성자로 하는 방법은? 생성자 혹은 다른 함수에서 m_A = A(10); 와 같이 따로 생성해줄 수 있다. 그러나 이 방법은 이미 생성된 m_A에 또 다시 A..

문법 진입점 함수 '본문'() { } 문장 문장은 마침표(.)로 끝난다. 단어와 단어는 띄어쓴다. 조사(은, 는, 이, 가, 을, 를, 보다, 와, 과, 거나)는 띄어쓰지 않는다. 식 식은 평가값을 갖는다. 식은 문장에 포함될 수 있다. 식은 소괄호로 묶일 수 있다. 리터럴 문자열 리터럴 : 쌍따옴표 안에 글자를 입력한다. "이것은 문자열 리터럴 입니다." 숫자 리터럴 : 한글로 된 숫자를 입력한다. 입력 가능한 글자는 일, 둘, 삼, 사, 오, 육, 칠, 팔, 구, 십, 백, 천, 만, 억, 조, 점 이다. 실수와 정수는 구분되지 않는다. 글자 '점' 아래에 숫자를 쓰면 소수점 아래 표현 가능. 이(2)로 끝나는 숫자 뒤에는 조사 '이' 가 올 수 없다. 일조삼억오천만삼천둘백칠십일점일둘삼사오 불 리터럴..

머리말 이 프로젝트는 책 '컴파일러 만들기, 컴퓨터 프로그램의 구조와 원리 ' 를 읽고 참고하여 만들었습니다. 해당 책에서는 C++ 언어를 사용해 저자가 만든 YuLang(유랭) 이라는 프로그래밍 언어를 컴파일하는 컴파일러와 인터프리터를 만듭니다. 하지만 그대로 따라 만들면 공부가 안되기에, 저는 약간 변형해 저만의 프로그래밍 언어를 정의하고 그를 컴파일해서 실행까지 시키는 인터프리터와 컴파일러, 그리고 컴파일된 코드를 실행시키는 가상머신까지 만들어 보겠습니다. 아래는 책 구매 링크입니다. https://www.yes24.com/Product/Goods/103153057 컴파일러란 무엇인가? 컴파일러란 소스코드를 실행가능한 파일로 만들어주는 프로그램을 말합니다. 좁은 의미로는 소스코드를 중간코드로 바꿔주..

문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] 세로길이가 n 가로길이가 m인 격자 모양의 땅 속에서 석유가 발견되었습니다. 석유는 여러 덩어리로 나누어 묻혀있습니다. 당신이 시추관을 수직으로 단 하나만 뚫을 수 있을 때, 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾으려고 합니다. 시추관은 열 하나를 관통하는 형태여야 하며, 열과 열 사이에 시추관을 뚫을 수 없습니다. 예를 들어 가로가 8, 세로가 5인 격자 모양의 땅 속에 위 그림처럼 석유가 발견되었다고 가정하겠습니다. 상, 하, 좌, 우로 연결된 석유는 하나의 덩어리이며, 석유 덩어리의 크기는 덩어리에 포함된 칸의 수입니다. 그림에서 석유 덩어리의 크기는 왼쪽부터 8, 7, 2입니다. 시추관은 위 그림처럼 설치한..