반응형

분류 전체보기 135

백준 1012 - 유기농 배추 (그래프 탐색, 순회)

문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군..

백준 1904번 - 다이나믹 프로그래밍

지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이의 공부를 방해하기 위해 0이 쓰여진 낱장의 타일들을 붙여서 한 쌍으로 이루어진 00 타일들을 만들었다. 결국 현재 1 하나만으로 이루어진 타일 또는 0타일을 두 개 붙인 한 쌍의 00타일들만이 남게 되었다. 그러므로 지원이는 타일로 더 이상 크기가 N인 모든 2진 수열을 만들 수 없게 되었다. 예를 들어, N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수..

[알고리즘]최소신장트리 (MST)구현하기 - C로구현하기

*신장 부 그래프: 그래프 G의 모든 정점들을 포함하는 부그래프. * 신장트리: (자유)트리인 신장 부그래프. 최소신장트리 Minimum spanning tree: G의 신장트리 가운데 간선 무게의 합이 최소인 것. -통신망, 교통망 등의 설계에 자주 응용된다. * 최소신장트리의 속성 * 사이클 속성 (없음) * 분할 속성 * 최소신장트리 구하는 알고리즘 *탐욕법 초기구성으로부터 시작하여 부분적인 향상을 계속함으로써 전체 최적해를 찾을 수 있는 문제들 탐욕적 선택 속성을 가진 경우에만 탐욕해가 최적해가 된다. *prim 알고리즘 해석 : 단순연결 무방향 가중 그래프 G에 대한 최소신장트리를 계산한다. 그래프의 임의의 정점 s를 택하여 s로부터 시작하여 정점들을 배낭에 넣어가며 배낭안에서 MST, 즉 최소..

개발/C,C++ 2022.12.17

C - 인접행렬로 그래프 구현하기 (알고리즘)

#include #include #include //인접 행렬로 그래프 표현하기 /* 함수 기능 명세 [public] Makegraph : 문제에서 요구하는 대로 그래프를 완성한다. makeEdge : 두 노드를 받아, 맞게 vertex 를 표현한다. print_graph : 그래프에서 한 노드에 연결된 인접 행렬을 모두 표시한다. modify_weight : 노드 간의 vertex의 weight를 조정하되, 없으면 만들고 0이면 삭제한다. 0일 때: delete_vertex 0이 아닐 떄: 양쪽으로 modify_weight_utils [private] modify_weight_utils : 한쪽으로 node1에서 node2를 지운다 . */ void makeEdge(int (* graph)[7], in..

개발/C,C++ 2022.12.16

해쉬테이블 구현하기(C, C언어)

// // Created by Eun jung Bang on 2022/12/15. // 해쉬에서 충돌이 일어났을 때 해결하는 방법 해쉬 충돌: 두 개 이상의 원소들이 동일한 셀로 매핑되는 경우. 1. 분리 연쇄법 리스트를 이용해서 해당 셀에 이어서 연결한다. 2. 개방 주소 법 a. 선형 조사법: 바로 비어있는 다음 셀에 저장한다. (h(k) +i) . 1차 군집화의 위험 b. 2차 조사법: 제곱만큼 넘어가서 다음 셀에 저장 (h(k) + i^2),. 절반 이상 차면 버켓이 비어있어도 찾기 어려워짐. c. 이중 해싱: 다른 해싱 함수의 값만큼 넘어가서 다음 셀에 저장. (h(k) + i * h'(k)).h'의 개산 결과가 0이 아니어야 하고 m과 h'가 서로소. 개방주소법 알고리즘 Alg findElem..

개발/C,C++ 2022.12.16

이진트리 메소드 구현하기

중복 키가 없는 이진트리 구현하기 1. 메쏘드 i : key 입력 받은 후 트리에 삽입 d : key 입력 받은 후 해당 노드가 있다면 노드 삭제, 삭제한 키 출력. 없으면 X 출력 s : key 입력 받은 후 해당 노드가 있다면 키를 출력, 없으면 X 출력 p : 트리를 전위 순회로 인쇄. q : 종료 2. 메소드 구현 [public] * findElement(k) : key를 받아서 해당 노드를 찾아 원소를 반환(여기서 원소 = 키) * insertItem(k) : key를 받아서 트리에 해당 키를 가진 노드를 삽입. treesearch , setnode , expandExternal(left), expandExternal(right). * treeSearch(w, k) : (노드, 키) 트리에서 원..

개발/C,C++ 2022.12.15

makefile 오류 - 'linker' input unused [-Werror,-Wunused-command-line-argument]

cc -Wall -Wextra -Werror -c monitoring.o routine_utils.o utils2.o init_routines.o philosopher.o utils1.o -o philo clang: error: monitoring.o: 'linker' input unused [-Werror,-Wunused-command-line-argument] clang: error: routine_utils.o: 'linker' input unused [-Werror,-Wunused-command-line-argument] clang: error: utils2.o: 'linker' input unused [-Werror,-Wunused-command-line-argument] clang: error..

애플리케이션이란? - 백엔드와 프론트엔드 관점에서. 그리고 네트워크

애플리케이션이란 말은 참 많이도 들어보았다. 그냥 사용자들이 편히 쓸 수 있게 만든 '프로그램' , '앱'이라고만 알고 있었는데, 이게 정확히 뭘까에 대한 고민은 해보지 않았었다. 컴퓨터 네트워크를 공부하는데 애플리케이션 계층에서 나타난 설명을 보고 조금 정리해보았다. (교과서 : 컴퓨터 네트워크 하향식 접근) 아직 더 공부를 하고 실습해보아야 알겠지만 여기서 읽고 느낀 애플리케이션을 요약하면 다음과 같다. * 애플리케이션이란? 통신에 대한 걱정은 아래 계층에 맡겨버리고(트랜스포트 계층, 네트워크 계층 ..) 기능적인 것에 집중해서 만든 프로그램. 서비스는 서버에서 제공하되, 그것을 요청할 수 있는 브라우저 혹은 앱이 사용자와 가까이 있어서 서버와 통신하면서 그 서비스를 이용할 수 있다. 서버는 사용자 ..

카테고리 없음 2022.12.04

컴퓨터네트워크 - 애플케이션 계층 (간단 맛보기)

1. 애플리케이션이란 - 컴퓨터 네트워크 계층 측면에서 보면 가장 상위에 있는 계층이다. 인터넷 애플리케이션에는 1970년대에 등장했던 텍스트 전자메일, 컴퓨터로의 원격 접속 등을 포함해서 1990년대 중반에 나온 월드와이드앱(www : 웹서핑, 검색, 전자상거래 등을 포괄한다. ), 그리고 요즘에는 유튜브처럼 사용자가 만든 비디오 분배, 넷플릭스 같은 온디맨드 영화, 또는 구글 행아웃 같은 비디오 콘퍼런싱, 마지막으로 인스타그램, 페이스북과 같은 소설 네트워킹 애플리케이션도 이 계층에 속한다. 2. 애플리케이션 개발. 네트워크 애플리케이션 개발의 중심은 다른 위치의 '종단 시스템'에서 동작하고 네트워크를 통해 서로 통신하는 프로그램을 작성하는 것이다. 예를 들어 웹 애플리케이션에는 서로 통신하는 서버와..

데이터의 표현과 컴퓨터 연산

이번 시간에는 컴퓨터가 어떻게 데이터를 저장하고 처리하는 지 알아볼 것이다. 3.2. 정수의 표현 컴퓨터의 가장 근본이 되는 기능은 수치의 계산이라고 할 수 있다. 이걸 수행하는 가장 핵심적인 장치가 바로 CPU 안에 있는 ALU라고 하는 하드웨어이다. 컴퓨터는 2진수의 체계로 수를 저장하고 표현한다. 모두가 잘 아는 이진수의 체계인데 한번 더 짚고 넘어가자면, 소수점 이하의 이진수는 2^(-1), 2^(-2) .. 를 의미한다. ex) 0.101 = 0.5 + 0.125 = 0.625 컴퓨터는 양수 뿐만 아니라 음수도 처리하기 때문에 음수를 표현하는 방법이 필요하다. 이를 수행하는 데에는 여러가지 방법이 있는데, 공통적인 부분은 2진수의 가장 왼쪽 비트가 부호 비트로 사용된다는 점이다. 맨 왼쪽 비트,..

728x90
728x90