https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 재귀를 이용한 백트래킹 알고리즘 문제다. Queen은 행, 열, 대각선을 공격할 수 있으므로 새 Queen을 놓을때 기존의 Queen의 공격범위와 겹치지 않는지 판단해야 한다. 행에 대해선 무조건 각자 다른 행에 놓도록 한다. i번째 퀸은 i행에 놓도록 함. 이를 통해서 2차원 배열이 아닌 '열'의 정보값만 저장하는 1차원 배열을 사용하여 문제를 해결할 수 있다. 열은 간단하게 배열의 앞부분을 탐색해주면 된다. ..

https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 재귀함수 호출을 이용한 백트래킹 알고리즘이다. 백트래킹은 모든 경우의 수를 탐색함과 동시에 가망이 없는 경우의 수에 대해선 탐색을 미리 끝내버리는 방법이다. N과 M 문제는 1~N 범위의 자연수 중 M개의 자연수를 중복없이 고르는 문제다. M개의 자연수를 고르기 위해선 중복 for문을 돌린 뒤, 중복되는 수가 없는지 판단하면 되겠지만 N과 M 범위가 커질수록 기하급수적인 연산을 요구하게 될 것이..

https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 그래프의 신장트리에서 최장거리를 구해야하는 내용이라 다익스트라라고 생각하기 어려웠다. 다익스트라 알고리즘은 분명 두 버텍스 사이의 최단거리를 구하는 알고리즘이지만. 알고리즘의 내용 자체는 특정 버텍스를 기준으로 연결된 모든 버텍스의 최단거리를 구하게 된다. 즉, 다익스트라 알고리즘을 사용한 뒤, 각 버텍스까지의 거리를 저장한 리스트를 선형탐색하면 탐색한 버텍스의 수와 가장 먼 버텍스까지의 거리도 도출..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 쉬운 동적 프로그래밍 기법인데 너무 빙빙 돌아서 생각했다; i번째 계단에 도착하는 방법은 2가지 1. i-2번째 계단에서 2계단을 한 번에 올라온다. 2. i-3번째 계단에서 2계단을 한 번에 올라와 i-1번째 계단으로 온 후 i번째 계단으로 한 칸 올라온다. 점화식으로 정리하면 이렇게 된다 DP[i] = max(DP[i-2] + Stair[i], DP[i-3] + DP[i-1] + Stair[i]) i-2번..

https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 1. 각 케이스를 날짜대로 오름차순 정렬한다. 2. 현재 날짜를 0일이라고 생각한다. 3. 오름차순 정렬된 케이스를 선형탐색하여 현재 날짜보다 데드라인이 높다면 현재 날짜를 +1, 결과 우선순위 큐(오름차순)에 컵라면 갯수를 삽입해준다. 4. 결과 우선순위 큐의 Top에는 현재 날짜까지의 최적해에서 가장 적은 컵라면을 주는 케이스가 됨 5. 현재 날짜보다 데드라인이 낮거나 같은 케이스가 들어오면 결과 우선..

그리디 알고리즘(탐욕 알고리즘)은 알고리즘을 풀어나갈때 각 순간마다 최적인 답을 선택하여서 최적해의 근사값을 구하는 알고리즘이다. 그리디 알고리즘으로 추론된 답이 최적해임을 보장하기 위해선 문제가 두 가지 조건을 만족하여야 한다. 1. 탐욕적 선택 속성: 탐욕적인 선택이 언제나 최적해를 보장해야 함(특정 선택이 이후의 선택에 영향을 주지 않음). 2. 최적 부분 구조: 문제의 최적해는 부분 문제들의 최적해의 집합과 동일하여햐 함. https://www.acmicpc.net/problem/18185 18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구..

객체 지향의 5원칙 SOLID S 단일 책임 원칙(Single responsibility principle) - 한 클래스가 제공하는 모든 서비스는 하나의 책임을 수행하는데 집중되어야 한다. O 개방 폐쇄 원칙(Open/closed principle) - 소프트웨어의 모든 구성요소는 확장에는 열려있으나, 변경에는 닫혀있어야 한다. - 클래스를 설계할 때 변할 부분과 변하지 않을 부분을 구분해야 한다. L 리스코프 치환 원칙(Liskov substitution principle) - 클래스는 정확성을 깨뜨리지 않으면서 하위 타입의 인스턴스로 바꿀 수 있어야 한다. - 부모 클래스의 포인터에 해당 클래스의 자식 클래스를 할당하더라도 모든 기능이 정상적이어야 한다. I 인터페이스 분리 원칙(Interface ..

우리가 변수를 생성할때 이러한 데이터를 저장하기 위해 메모리에 저장할 공간을 할당받는다. 이 저장할 공간은 각각의 주소가 존재하며, 데이터의 주소값은 해당 데이터가 저장된 메모리의 시작 주소를 의미한다. int는 정수를 저장하는데 사용되는 변수명. char는 문자를 저장하는데 사용되는 변수명. 포인터는 주소값을 저장하는데 사용되는 변수명이다. 포인터에 사용되는 연산자는 주소 연산자(&), 참조 연산자(*) 두 가지가 있다. 주소 연산자(&)는 변수의 이름 앞에 사용되며 해당 변수의 주소값을 반환한다. 참조 연산자(*)는 이름이나 주소 앞에 사용하여, 포인터에 저장된 주소에 저장된 값을 반환한다. 포인터의 선언에도 사용되기도 한다. 포인터는 주소값을 저장하기 때문에 포인터를 참조하여 해당 주소의 데이터를 ..

const constant위 약자로 사전적 의미는 '상수'를 뜻한다. C++에서 const 키워드는 해당 대상을 변경하지 않는 '상수'로 판단한다는 뜻. - const 비멤버 변수 두 선언은 동일하며, num은 const int로 변하지 못하는 상수가 되어서 num을 변경하려고 하면 에러가 발생. - const 멤버 변수 const 키워드를 사용할때는 반드시 초기화를 해주어야 한다. 멤버 변수를 const로 선언할때는 아예 선언과 동시에 초기화를 해주거나, 초기화 리스트를 사용하여야 한다. C 클래스는 const int인 num을 선언한 뒤 이후 생성자에서 num을 변경하려고 하였으므로 에러가 발생한다. - const 포인터 변수 기존 const 변수 선언법과 다르게 const 포인터 변수는 const의..

- BFS를 사용하는 문제지만 매번 BFS를 처음부터 진행하면 TimeLimit 발생. - BFS를 사용하면서 갔던 노드에는 재방문하지 않도록 최적화가 필요한 문제. - 물, 백조 각각 큐를 만들어서 각각 BFS를 진행. - 백조 BFS의 초기값은 두 백조 중 하나의 좌표 - 백조 BFS에서 도달한 X 좌표들은 다음번 백조 BFS를 시작할 위치들임. - 2차원 bool 배열을 만들어서 백조 BFS에서 방문했던 위치에 대해 따로 기록하고 이미 방문한 좌표는 탐색하지 않음. - 백조 BFS에서 백조에 도달하면 반복문을 멈추고 해당 카운트값을 리턴. - 물 BFS의 초기값은 입력받았던 .(물)과 L(백조)의 모든 좌표 - 물 BFS에서 도달한 X 좌표들은 .(물)로 바꿔주고 다음번 물 BFS를 시작할 위치들임..

큐 = Queue - 먼저 집어넣은 데이터가 먼저 나오는 선입선출의 자료구조. - 데이터를 아래에서 위로 쌓아올린다고 했을때 나가는 데이터는 맨 아래에 있는 데이터다. - 큐에 데이터를 삽입하는 것을 Enqueue, 맨 앞의 데이터를 삭제하는 것을 Dequeue라고 한다. - 연결 리스트, 벡터, 배열 등으로 구현 가능하며 STL도 존재함. 우선순위 큐 = Priority Queue - 각 데이터에 우선순위를 두어서 우선순위가 가장 높은 데이터가 먼저 나가는 자료구조. - 일반적으로 배열, 연결 리스트, 힙으로 구현하며 보통 삽입, 삭제 모두 O(logN)을 보장하는 힙으로 구현한다. 힙 = Heap - 가장 크거나 작은 값을 찾기 위한 완전 이진 트리(중간에 빈 공간이 없는 트리) - 데이터 삽입: 트..

ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); 알고리즘을 풀때 실행속도를 빠르게 하기 위하여 작성해주는 코드. 당장 오늘 이 3줄때문에 30분동안 씨름하던 코드가 단박에 정답이라고 나왔다. 도대체 이게 뭐길래 그럴까? ios::sync_with_stdio(false); C++의 iostream과 c의 stdio라는 입출력 stream의 동기화 해제한다는 의미다. 디폴트 상태는 true로 C++과 C의 입출력 스트림이 동기화 되어있어서 C스타일과 C++스타일의 입출력을 혼합사용하여도 사용자의 의도대로 입출력을 받도록 해준다. 해당 구문을 입력하여 동기화를 해제해주면 C++ 입출력 스트림이 독립적인 버퍼를 사용하게 되어 입출력시간을 절약할 수 있다..