동찬 코드 일지

자료구조와 알고리즘은 무엇인가? 둘 중 무엇이 더 중요할까? 결론적으로는 자료구조가 좀 더 중요하다. # 자료구조 자료를 체계화 및 구조화 하여 관리하며 저장 일정 규칙으로 자료를 나열 (혹은 정리) 하는 것이 자료구조 # 알고리즘 문제 해결에 관한 공식을 코드화 한 것 문제해결 능력, 사고력 문제 파악 알고리즘은 자료구조에 의존적이다. # 자료 구조 종류 2가지 1. 선형 구조 1차원 줄을 세우는 것 2. 비선형 구조 2차원 줄을 세우지 않고 2차원적 구조를 가짐 (트리 구조) 성능 적으로는 2차원인 비선형 구조가 압도한다. 데이터들의 집합체 = 데이터베이스 DataBase - 역할 정보를 구조화 하여 자료를 관리 데이터베이스는 성능이 중요하기 때문에 모두 비선형적 자료구조를 사용 "잘 정리해 놔야(자..

연산자 끼워넣기 https://www.acmicpc.net/problem/14888 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷..

영화감독 숌 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 88031 50128 40505 56.628% 문제 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워즈를 만들 때, 스타워즈 1, 스타워즈 2, 스타워즈 3, 스타워즈 4, 스타워즈 5, 스타워즈 6과 같이 이름을 지었고, 피터 잭슨은 반지의 제왕을 만들 때, 반지의 제왕 1, 반지의 제왕 2, 반지의 제왕 3과 같이 영화 제목을 지었다. 하지만 숌은 자신이 조지 루카스와 피터 잭슨을 뛰어넘는다는 것을 보여주기 위해서 영화 제목을 좀 다르게 만들기로 했다. 종말의 수란 어떤 수에..

https://www.acmicpc.net/problem/1018 체스판 다시 칠하기 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 2 초 128 MB 107791 53374 42690 49.714% 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼..

C++은 개발자가 직접 메모리를 관리해야 하는 언어이다. 이 때문에 타 프로그래밍 언어 보다 로우레벨의 지식과 컴퓨터 구조에 대해 깊은 이해도가 필요하다. 오늘은 C++의 변수와 메모리 관리에 대해 알아보자 변수 - 변수는 메모리에 할당 될 때 stack 메모리에 쌓이면서 할당 된다. std :: cout

# 목표 Cpp 에서 각 변수 마다 메모리를 어떻게 allocation (할당) 되는지 알아보는 시간을 가진다. 시작하기 전, 변수에 대한 내용을 정리하고 시작 하겠다. # 변수 1. 실제 메모리는 Stack 구조로 쌓인다. 2. 변수에 접근하는 방법은 탑 위치 ( Stack의 맨위) 에서 몇 번째 떨어져있는지 확인 하며 변수의 위치 확인 2-1. Low level로 설명하면 격자 같이 메모리에 저장된다. # 변수의 주소값을 확인하는 코드 # 내용 이번 내용에서는 메모리의 크기 (size)가 어떻게 할당 되는지 확인해본다. 일단 1 바이트는 1 byte = 8 bit int = 4 byte Cpp의 sizeof() 함수는 해당되는 변수나 자료형의 크기를 바이트 단위로 반환한다. 다른 자료형의 크기는 해당..

특정한 최단 경로 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 77113 20219 13713 24.717% 문제 방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다. 세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 E가..

완전탐색 개요 정답이 될 가능성이 있는 모든 후보 (candidates)를 체계적(반복문, 재귀, 비트마스크 등)으로 확인하는 알고리즘 다른말로 브루트 포스 ( brute force ) 라고도 한다. 탐색 알고리즘과 완전탐색의 개념을 혼동하는 경우가 있어 각각 정리해보았다. 탐색 알고리즘 과 완전 탐색의 구분 대표적인 탐색 (search) 알고리즘 - 선형 탐색 O(n) 리스트를 처음부터 하나하나 비교해가며 탐색 - 이진 탐색 O(logn) 리스트를 정렬 후 가운데 값을 비교한다. 비교한 값이 찾는 값보다 클 경우 오른쪽 1/2 구간을 탐색한다. 나머지를 배제 이 과정을 반복한다. - 비선형 탐색 (DFS, BFS) 너비 우선 탐색, 깊이 우선 탐색 완전 탐색 구현 방법에 따라 구분 대표적인 3가지 - ..

# 풀이 # 모듈 선언 힙 자료구조 활용과 가중치 그래프를 구현하기 위한 모듈 선언 from collections import defaultdict import heapq # 입력처리 for _ in range((E-1)): a, b, c = map(int, input().split()) roads.append([a,b,c]) - 가중치 그래프를 2중 리스트에 저장 하였다. a : 출발 정점 b : 도착 정점 c : 거리 - 반드시 거쳐야 하는 두 정점 처리 must_a, must_b = map(int, input().split()) - 코드 가독성을 위해 end 변수 추가 end = N # 접근 방법 일단 다익스트라 알고리즘의 기본 형을 정의 한 뒤 수정하는 방법을 고안하기로 하였다. 전 내용에서 코드..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 최단경로 성공 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 256 MB 184977 55260 28080 25.291% 문제 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다. 입력 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ ..