bong-u/til

๐Ÿ  home ๐Ÿˆ repository ๐Ÿ“ก rss
new RAG ์ด๋ก  ์ •๋ฆฌ + OpenSearch
๐Ÿค– ์ธ๊ณต์ง€๋Šฅ
RAG (Retrieval-Augmented Generation) RAG๋Š” ๊ฒ€์ƒ‰๊ณผ ์ƒ์„ฑ์„ ๊ฒฐํ•ฉํ•œ ๋ชจ๋ธ๋กœ, ๊ฒ€์ƒ‰์„ ํ†ตํ•ด ์–ป์€ ์ •๋ณด๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ ์ƒ์„ฑ์„ ์ˆ˜ํ–‰ํ•˜๋Š” ๋ชจ๋ธ LLM์˜ ๋ฌธ์ œ์  ํ• ๋ฃจ์‹œ๋„ค์ด์…˜: ์ƒ์„ฑ ๋ชจ๋ธ์ด ํ›ˆ๋ จ ๋ฐ์ดํ„ฐ์— ์—†๋Š” ๋‚ด์šฉ์„ ์ƒ์„ฑํ•˜๋Š” ํ˜„์ƒ ์ตœ์‹ ์˜ ์‘๋‹ต์„ ๊ธฐ๋Œ€ํ•˜๋Š” ์ƒํ™ฉ์—์„œ ์˜ค๋ž˜๋˜์—ˆ๊ฑฐ๋‚˜ ์ผ๋ฐ˜์ ์ธ ์ •๋ณด๋ฅผ ์ƒ์„ฑํ•˜๋Š” ๋ฌธ์ œ ์‹ ๋ขฐํ•  ์ˆ˜ ์—†๋Š” ์ถœ์ฒ˜๋กœ๋ถ€ํ„ฐ ์ •๋ณด๋ฅผ ์ƒ์„ฑํ•˜๋Š” ๋ฌธ์ œ RAG๋Š” ์œ„์—์„œ ์„œ์ˆ ํ•œ LLM ๋ฌธ์ œ์˜ ์ผ๋ถ€๋ฅผ ํ•ด๊ฒฐํ•˜๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ์ˆ˜๋‹จ์ด๋‹ค. OpenSearch OpenSearch๋Š” ์˜คํ”ˆ์†Œ์Šค ๊ฒ€์ƒ‰ ๋ฐ ๋ถ„์„ ์—”์ง„์œผ๋กœ, ์—˜๋ผ์Šคํ‹ฑ์„œ์น˜์˜ ํฌํฌ ๋ฒ„์ „ ๋ฒกํ„ฐ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค : ๋ฒกํ„ฐ ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ  ์ฟผ๋ฆฌํ•  ์ˆ˜ ์žˆ๋Š” ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค ์ฃผ์š” ๊ธฐ๋Šฅ ๋ถ„์‚ฐ ๊ฒ€์ƒ‰ ๋ฐ ๋ถ„์„ ๋ณด์•ˆ ์‹œ๊ฐํ™”์™€ ๋Œ€์‹œ๋ณด๋“œ ์ง€์› index์™€ document index : ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค document : ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์— ์ €์žฅ๋˜๋Š” ๋ฐ์ดํ„ฐ ๋ถ„์„ ๋ถ„์„๊ธฐ Analyzer (Character Filter + Tokenizer + Token Filter) ํ…์ŠคํŠธ๋ฅผ ํ† ํฐํ™”ํ•˜๊ณ  ํ•„ํ„ฐ๋งํ•˜๋Š” ๊ณผ์ •์„ ์ˆ˜ํ–‰ ๋ถ„์„ ๊ณผ์ • Character Filter ํŠน์ • ๋ฌธ์ž๋ฅผ ์ œ๊ฑฐํ•˜๊ฑฐ๋‚˜ ๋ณ€๊ฒฝํ•˜๋Š” ๋“ฑ์˜ ์ž‘์—…์„ ์ˆ˜ํ–‰ Tokenizer ๊ธฐ๋ณธ์ ์œผ๋กœ ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ํ…์ŠคํŠธ๋ฅผ ๋ถ„๋ฆฌ Token Filter ํ† ํฐ์„ ์ถ”๊ฐ€ํ•˜๊ฑฐ๋‚˜ ์ œ๊ฑฐํ•˜๋Š” ๋“ฑ์˜ ์ž‘์—…์„ ์ˆ˜ํ–‰ OpenSearch์—์„œ ์ง€์›ํ•˜๋Š” ์š”์†Œ Tokenizer Standard Tokenizer : ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ํ…์ŠคํŠธ๋ฅผ ๋ถ„๋ฆฌ, ๋ฌธ์žฅ ๋ถ€ํ˜ธ ์‚ญ์ œ Letter Tokenizer : ๋ฌธ์ž๋ฅผ ๊ธฐ์ค€์œผ๋กœ ํ…์ŠคํŠธ๋ฅผ ๋ถ„๋ฆฌ Whitespace Tokenizer : ๊ณต๋ฐฑ์„ ๊ธฐ์ค€์œผ๋กœ ํ…์ŠคํŠธ๋ฅผ ๋ถ„๋ฆฌ Ngram Tokenizer : ๋ถ€๋ถ„ ๋ฌธ์ž์—ด๋กœ ํ…์ŠคํŠธ๋ฅผ ๋ถ„๋ฆฌ Token Filter Standard Token Filter : ์•„๋ฌด๊ฒƒ๋„ ํ•˜์ง€ ์•Š์Œ Lowercase Token Filter : ํ…์ŠคํŠธ๋ฅผ ์†Œ๋ฌธ์ž๋กœ ๋ณ€ํ™˜ Synonym Token Filter : ๋™์˜์–ด ์ฒ˜๋ฆฌ Analyzer Standard Analyzer : Standard Tokenizer + Standard Token Filter Simple Analyzer : Letter Tokenizer + Lowercase Token Filter Whitespace Analyzer : Whitespace Tokenizer + Lowercase Token Filter OpenSearch ์ ‘๊ทผ์„ ์œ„ํ•œ cURL ๋ช…๋ น์–ด ์ธ๋ฑ์Šค ์กฐํšŒ 1curl -X GET -u {username}:{password} \ 2"http://localhost:9200/_cat/indices" ํŠน์ • ์ธ๋ฑ์Šค ์กฐํšŒ 1curl -X GET -u {username}:{password} \ 2"http://localhost:9200/{index_name}" ์ „์ฒด ๊ฒ€์ƒ‰ ๊ฒฐ๊ณผ ์กฐํšŒ 1curl -X GET -u {username}:{password} \ 2"http://localhost:9200/{index_name}/_search" ํŠน์ • ๊ฒ€์ƒ‰์–ด๋กœ ๊ฒ€์ƒ‰ํ•œ ๊ฒฐ๊ณผ ์กฐํšŒ 1curl -X GET -u {username}:{password} \ 2"http://localhost:9200/{index_name}/_search" \ 3-H "Content-Type: application/json" \ 4-d '{"query": {"match": {"field": "value"}}}' ์ธ๋ฑ์Šค ์‚ญ์ œ 1curl -X DELETE -u {username}:{password} \ 2"http://localhost:9200/{index_name}"
new OpenSearch๋ฅผ ํ™œ์šฉํ•œ RAG ์‹ค์Šต
๐Ÿค– ์ธ๊ณต์ง€๋Šฅ
๋ฐฐ๊ฒฝ ํ…Œ์ปค ๋ถ€ํŠธ์บ ํ”„์—์„œ ํŒ€ํ”„๋กœ์ ํŠธ๋ฅผ ์ง„ํ–‰ ์ค‘์ด๋‹ค. ์šฐ๋ฆฌ ํŒ€์˜ ์ฃผ์ œ๋Š” ํŠน์ • ์ธ๋ฌผ์—๊ฒŒ ์ƒ๋‹ด์„ ๋ฐ›๋Š” ๊ฒƒ ๊ฐ™์€ ๋Œ€ํ™”๋ฅผ ํ•  ์ˆ˜ ์žˆ๋Š” ์ฑ—๋ด‡์„ ๋งŒ๋“œ๋Š” ๊ฒƒ์ด๋‹ค. ์ด๋ฅผ ์œ„ํ•ด ํŠน์ • ์ธ๋ฌผ์ด ํ–ˆ๋˜ ๋ง์„ ๋ชจ์•„ ๋ฐ์ดํ„ฐ์…‹์œผ๋กœ ๋งŒ๋“ค๊ณ  ์ด๋ฅผ RAG ๋ชจ๋ธ์— ์ ์šฉ์‹œํ‚ค๋ ค๊ณ  ํ•œ๋‹ค. ์ˆœ์„œ ์ผ๋ก  ๋จธ์Šคํฌ๊ฐ€ TED์—์„œ ํ•œ ์ธํ„ฐ๋ทฐ๋ฅผ ํ…์ŠคํŠธ๋กœ ๊ฐ€์ ธ์˜จ๋‹ค. OpenSearch ๋„์ปค ์ปจํ…Œ์ด๋„ˆ๋ฅผ ์‹คํ–‰ํ•œ๋‹ค. ํ…์ŠคํŠธ ๋ฐ์ดํ„ฐ๋ฅผ ์ž„๋ฒ ๋”ฉํ•ด์„œ OpenSearch์— ์ €์žฅํ•œ๋‹ค. RAG ๋ชจ๋ธ์ด OpenSearch๋ฅผ ์ฟผ๋ฆฌํ•˜์—ฌ ๋Œ€๋‹ต์„ ์ƒ์„ฑํ•œ๋‹ค. 1. ์ผ๋ก  ๋จธ์Šคํฌ ์ธํ„ฐ๋ทฐ ํ…์ŠคํŠธ ๊ฐ€์ ธ์˜ค๊ธฐ ์œ ํŠœ๋ธŒ์—์„œ “์Šคํฌ๋ฆฝํŠธ ๋ณด๊ธฐ"๋ฅผ ํ†ตํ•ด ์ธํ„ฐ๋ทฐ ์ž๋ง‰์„ ๊ฐ€์ ธ์˜จ๋‹ค. 122:03 2EM: ์ด ํฐ ํŠธ๋Ÿญ์„ ๋ชฐ๋ฉด์„œ ๋ง๋„ ์•ˆ๋˜๋Š” ์›€์ง์ž„์„ ๋ณด์˜€์ฃ . 3CA: ์•„์ฃผ ๋ฉ‹์ง€๋„ค์š”. ์ž, ๊ทธ๋Ÿผ ์ •๋ง ๊ต‰์žฅํ•œ ์‚ฌ์ง„์—์„œ 422:09 5์กฐ๊ธˆ์€ ๋œ ๊ต‰์žฅํ•œ ์‚ฌ์ง„์„ ๋ณด์ฃ . "์œ„๊ธฐ์˜ ์ฃผ๋ถ€๋“ค"์ธ๊ฐ€์—์„œ ๋‚˜์˜ค๋Š” ๊ท€์—ฌ์šด ์ง‘ ์‚ฌ์ง„์ธ๋ฐ์š”. 622:15 7์ด๊ฒŒ ๊ฐ‘์ž๊ธฐ ์™œ ๋‚˜์˜จ๊ฑฐ์ฃ ? 8... ์ผ๋ก  ๋จธ์Šคํฌ๊ฐ€ ํ•œ ๋ง๋งŒ ์†์ˆ˜ ์ •๋ฆฌํ•œ๋‹ค. 1๋„ค. ์ œ ์Šค์Šค๋กœ๋„ ๊ทธ ์งˆ๋ฌธ์„ ์ž์ฃผ ํ•˜๋Š” ํŽธ์ž…๋‹ˆ๋‹ค. 2์ €ํฌ๋Š” LA์˜ ์ง€ํ•˜์— ๊ตฌ๋ฉ์„ ๋‚ด๋ ค๊ณ  ํ•˜๋Š”๋ฐ์š”. ์ด๋Š” ๊ตํ†ต ์ฒด์ฆ์„ ์™„ํ™”์‹œํ‚ค๊ธฐ ์œ„ํ•œ 33์ฐจ์› ๋„คํŠธ์›Œํฌ์˜ ํ„ฐ๋„์ด ๋  ์ˆ˜๋„ ์žˆ๋Š” ์‹œ๋ฐœ์ ์„ ๋งŒ๋“ค๊ธฐ ์œ„ํ•จ์ž…๋‹ˆ๋‹ค. 4๊ตํ†ต ์ฒด์ฆ์€ ์˜ค๋Š˜๋‚  ์šฐ๋ฆฌ์˜ ์˜ํ˜ผ์„ ํƒˆํƒˆ ํ„ฐ๋Š” ๋ฌธ์ œ ์ค‘์˜ ํ•˜๋‚˜์ž…๋‹ˆ๋‹ค. 5์„ธ๊ณ„ ๋ชจ๋“  ์‚ฌ๋žŒ๋“ค์—๊ฒŒ ์˜ํ–ฅ์„ ๋ผ์น˜๊ณ  ์žˆ์ฃ . ์ธ์ƒ์—์„œ ๋„ˆ๋ฌด๋„ ๋งŽ์€ ๋ถ€๋ถ„์„ ๊ฐ€์ ธ๊ฐ‘๋‹ˆ๋‹ค. 6... 2. OpenSearch ๋„์ปค ์ปจํ…Œ์ด๋„ˆ ์‹คํ–‰ 1docker create -it -p 9200:9200 -p 9600:9600 -e OPENSEARCH_INITIAL_ADMIN_PASSWORD={password} -e "discovery.type=single-node" -v opensearch_vol:/usr/share/opensearch/data --name opensearch opensearchproject/opensearch ์„ค๋ช… -p 9200:9200 : OpenSearch HTTP ํฌํŠธ -p 9600:9600 : OpenSearch ๋ชจ๋‹ˆํ„ฐ๋ง ํฌํŠธ -e OPENSEARCH_INITIAL_ADMIN_PASSWORD={password} : ์ดˆ๊ธฐ ๋น„๋ฐ€๋ฒˆํ˜ธ ์„ค์ • -e “discovery.type=single-node” : ๋‹จ์ผ ๋…ธ๋“œ๋กœ ์‹คํ–‰ -v opensearch_vol:/usr/share/opensearch/data : ๋ฐ์ดํ„ฐ ๋ณผ๋ฅจ ๋งˆ์šดํŠธ SSL ์˜ค๋ฅ˜ ๋ฐœ์ƒ๊ณผ ํ•ด๊ฒฐ ํ•˜์ง€๋งŒ ์œ„ ๋ช…๋ น์–ด๋กœ ์‹คํ–‰ํ•˜๋ฉด ์ปจํ…Œ์ด๋„ˆ ๋‚ด๋ถ€์—์„œ ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค 12024-07-05 22:15:12 Caused by: io.netty.handler.ssl.NotSslRecordException: not an SSL/TLS record: ... 22024-07-05 22:15:12 at io.netty.handler.ssl.SslHandler.decodeJdkCompatible(SslHandler.java:1314) ~[netty-handler-4.1.110.Final.jar:4.1.110.Final] 32024-07-05 22:15:12 at io.netty.handler.ssl.SslHandler.decode(SslHandler.java:1387) ~[netty-handler-4.1.110.Final.jar:4.1.110.Final] 42024-07-05 22:15:12 at io.netty.handler.codec.ByteToMessageDecoder.decodeRemovalReentryProtection(ByteToMessageDecoder.java:530) ~[netty-codec-4.1.110.Final.jar:4.1.110.Final] 52024-07-05 22:15:12 at io.netty.handler.codec.ByteToMessageDecoder.callDecode(ByteToMessageDecoder.java:469) ~[netty-codec-4.1.110.Final.jar:4.1.110.Final] 62024-07-05 22:15:12 ... 16 more ํ”„๋กœ์ ํŠธ ๊ธฐ๊ฐ„์ด ๊ธธ์ง€ ์•Š๊ณ , ํ•ด๋‹น ํฌํŠธ๋Š” ์™ธ๋ถ€์— ๋…ธ์ถœํ•  ํ•„์š”๊ฐ€ ์—†์œผ๋ฏ€๋กœ SSL์„ ๋„๊ณ  ์‹คํ–‰ํ•˜๋Š” ๊ฒƒ์œผ๋กœ ํ•ด๊ฒฐํ•˜์˜€๋‹ค. 1/usr/share/opensearch/config/opensearch.yml 2# ๋ณ€๊ฒฝ ์ „ 3plugins.security.ssl.http.enabled: true 4# ๋ณ€๊ฒฝ ํ›„ 5plugins.security.ssl.http.enabled: false 3. ํ…์ŠคํŠธ ๋ฐ์ดํ„ฐ ์ž„๋ฒ ๋”ฉ ๋ฐ OpenSearch์— ์ €์žฅ RAG ์„ธ์…˜์„ ํ•ด์ฃผ์‹  ๋ฉ˜ํ† ๋‹˜์ด ์งœ์ค€ ์ฝ”๋“œ๋ฅผ ์ ๊ทน! ์ฐธ๊ณ ํ•˜์—ฌ ์ž‘์„ฑํ•˜์˜€๋‹ค. OpenSearch ์ธ๋ฑ์Šค ์ƒ์„ฑ 1from opensearchpy import OpenSearch 2import torch 3from transformers import AutoTokenizer, AutoModel 4from langchain.text_splitter import RecursiveCharacterTextSplitter 5from langchain_community.document_loaders import TextLoader 6from langchain_community.vectorstores import OpenSearchVectorSearch 7 8INDEX_NAME = "elon_musk" 9FILE_NAME = "ted_elon_musk_script.txt" 10 11## OpenSearch ์—ฐ๊ฒฐ ์„ค์ • 12client = OpenSearch( 13 hosts=[{"host": "localhost", "port": 9200}], http_auth=("admin", {password}) 14) 15 16## ํ…์ŠคํŠธ ๋ฐ์ดํ„ฐ ๋ถˆ๋Ÿฌ์˜ค๊ธฐ 17loader = TextLoader(file_path=FILE_NAME, encoding="utf-8") 18docs = loader.load() 19 20text_splitter = RecursiveCharacterTextSplitter( 21 chunk_size=100, 22 chunk_overlap=0, 23 separators=["\n"], 24 length_function=len, 25) 26 27documents = text_splitter.split_documents(docs) 28 29# print(documents) 30 31## Embedding ๋ชจ๋ธ ์ •์˜ 32class MyEmbeddingModel: 33 def __init__(self, model_name): 34 self.tokenizer = AutoTokenizer.from_pretrained(model_name) 35 self.model = AutoModel.from_pretrained(model_name) 36 37 def embed_documents(self, doc): 38 inputs = self.tokenizer( 39 doc, return_tensors="pt", padding=True, truncation=True, max_length=512 40 ) 41 42 with torch.no_grad(): 43 outputs = self.model(**inputs) 44 embeddings = outputs.last_hidden_state.mean(dim=1).tolist() 45 46 return embeddings 47 48 def embed_query(self, text): 49 inputs = self.tokenizer( 50 [text], padding=True, truncation=True, return_tensors="pt", max_length=512 51 ) 52 with torch.no_grad(): 53 outputs = self.model(**inputs) 54 embeddings = outputs.last_hidden_state.mean(dim=1).tolist() 55 return embeddings 56 57 58## index ๊ตฌ์กฐ ์ •์˜ 59index_body = { 60 "settings": { 61 "analysis": { 62 "tokenizer": { 63 "nori_user_dict": { 64 "type": "nori_tokenizer", 65 "decompound_mode": "mixed", 66 "user_dictionary": "user_dic.txt", 67 } 68 }, 69 "analyzer": { 70 "korean_anlyzer": { 71 "filter": [ 72 "synonym", "lowercase", 73 ], 74 "tokenizer": "nori_user_dict", 75 } 76 }, 77 "filter": { 78 "synonym" :{ 79 "type": "synonym_graph", 80 "synonyms_path" : "synonyms.txt" 81 } 82 } 83 } 84 } 85} 86 87## Embedding ๋ชจ๋ธ ์ƒ์„ฑ 88my_embedding = MyEmbeddingModel("monologg/kobert") 89 90## OpenSearch์— ๋ฐ์ดํ„ฐ ์‚ฝ์ž… 91vector_db = OpenSearchVectorSearch.from_documents( 92 index_name=INDEX_NAME, 93 body=index_body, 94 documents=documents, 95 embedding=my_embedding, 96 op_type="create", 97 opensearch_url="http://localhost:9200", 98 http_auth=("admin", {password}), 99 use_ssl=False, 100 verify_certs=False, 101 ssl_assert_hostname=False, 102 ssl_show_warn=False, 103 bulk_size=1000000, 104 timeout=360000, 105) 106 107result = vector_db.add_documents(documents, bulk_size=1000000) tokenizer๋Š” ํ•œ๊ตญ์–ด๋ฅผ ์ง€์›ํ•˜๋Š” “nori_tokenizer"๋ฅผ ์‚ฌ์šฉํ•˜์˜€๋‹ค. embedding ๋ชจ๋ธ์€ ์ €๊ฑฐ ๋ง๊ณ ๋„ ์—ฌ๋Ÿฌ๊ฐ€์ง€๊ฐ€ ์กด์žฌํ•˜๋Š”๋ฐ, ์–ด๋–ค ๋ชจ๋ธ์ด ํ”„๋กœ์ ํŠธ์— ๊ฐ€์žฅ ๋ถ€ํ•ฉํ•˜๋Š” ๋ชจ๋ธ์ธ์ง€๋Š” ์‹คํ—˜์„ ํ•ด๋ณผ ๊ฒƒ์ด๋‹ค. curl์„ ํ†ตํ•ด localhost:9200/elon_musk/_search๋กœ ์š”์ฒญ์„ ๋ณด๋‚ด ์ž„๋ฒ ๋”ฉํ•œ ๋ฐ์ดํ„ฐ๊ฐ€ ์ž˜ ๋“ค์–ด๊ฐ”๋Š”์ง€ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค. 4. RAG ๋ชจ๋ธ์ด OpenSearch๋ฅผ ์ฟผ๋ฆฌํ•˜์—ฌ ๋Œ€๋‹ต ์ƒ์„ฑ 1from langchain.prompts import PromptTemplate 2from langchain.chains import LLMChain 3from langchain_openai import ChatOpenAI 4from opensearchpy import OpenSearch 5import os 6 7INDEX_NAME = "elon_musk" 8 9# ํ™˜๊ฒฝ๋ณ€์ˆ˜ ์„ค์ • 10os.environ["OPENAI_API_KEY"] = {api_key} 11 12llm = ChatOpenAI( 13 model_name="gpt-3.5-turbo", 14) 15 16prompt_template = PromptTemplate( 17 input_variables=["context", "question"], 18 template=""" 19Imagine you are {character_name}, 20a wise and experienced advisor. Given the context: "{context}", 21how would you respond to this inquiry: "{question}"?', 22(in korean) 23""", 24) 25 26 27llm_chain = LLMChain(llm=llm, prompt=prompt_template) 28 29client = OpenSearch( 30 hosts=["http://localhost:9200"], 31 http_auth=("admin", {password}), 32 use_ssl=False, 33 verify_certs=False, 34 ssl_assert_hostname=False, 35 ssl_show_warn=False, 36) 37 38def search_documents(query): 39 search_body = {"query": {"match": {"text": query}}} 40 response = client.search(index=INDEX_NAME, body=search_body) 41 hits = response["`its"]["hits"] 42 return [hit["_source"]["text"] for hit in hits] 43 44if __name__ == "__main__": 45 question = input("Enter your question\n") 46 search_results = search_documents(question) 47 48 print(search_results) 49 50 # context = " ".join(search_results) 51 context = "" 52 53 response = llm_chain.invoke({"character_name": INDEX_NAME, "context": context, "question": question}) 54 55 print (response["text"]) OpenSearch์— ์ €์žฅ๋œ ๋ฐ์ดํ„ฐ๋ฅผ ์ฟผ๋ฆฌํ•˜์—ฌ RAG ๋ชจ๋ธ์— ๋„ฃ์–ด ๋Œ€๋‹ต์„ ์ƒ์„ฑํ•œ๋‹ค. search_documents ํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด OpenSearch์— ์ฟผ๋ฆฌ๋ฅผ ๋ณด๋‚ด๊ณ , ๊ทธ ๊ฒฐ๊ณผ๋ฅผ context๋กœ ์‚ฌ์šฉํ•œ๋‹ค. ๊ฒฐ๊ณผ ์งˆ๋ฌธ ํ…Œ์Šฌ๋ผ์— ๋Œ€ํ•ด์„œ ์–ด๋–ป๊ฒŒ ์ƒ๊ฐํ•ด? RAG๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š์•˜์„ ๋•Œ์˜ ๋Œ€๋‹ต ํ…Œ์Šฌ๋ผ๋Š” ํ˜์‹ ์ ์ธ ๊ธฐ์—…์œผ๋กœ์„œ ๋ฏธ๋ž˜๋ฅผ ํ–ฅํ•œ ๋น„์ „์„ ๊ฐ€์ง€๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๊ทธ๋“ค์˜ ์ „๊ธฐ ์ž๋™์ฐจ ๊ธฐ์ˆ ๊ณผ ์—๋„ˆ์ง€ ์†”๋ฃจ์…˜์€ ์ „ ์„ธ๊ณ„์ ์œผ๋กœ ์ฃผ๋ชฉ๋ฐ›๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ํ…Œ์Šฌ๋ผ์˜ ํ˜์‹ ์ ์ธ ์ ‘๊ทผ ๋ฐฉ์‹๊ณผ ์ง€์† ๊ฐ€๋Šฅํ•œ ๋น„์ฆˆ๋‹ˆ์Šค ๋ชจ๋ธ์— ๋Œ€ํ•ด ๋งค์šฐ ๊ธ์ •์ ์œผ๋กœ ์ƒ๊ฐํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. RAG๋ฅผ ์‚ฌ์šฉํ• ๋•Œ ์ ์šฉ๋œ context [‘๊ธธ๊ฒŒ ๊ฐˆ ๊ฒƒ ๊ฐ™์ง€๋Š” ์•Š์•„์š”.\n๊ทธ๋Ÿฌ๋„ค์š”. ์ €๋Š” ์ตœ๋Œ€ํ•œ ์˜ค๋žซ๋™์•ˆ ํ…Œ์Šฌ๋ผ์— ๋จธ๋ฌผ ์ƒ๊ฐ์ด์—์š”.\n๊ทธ๋ฆฌ๊ณ  ์ค€๋น„ ์ค‘์— ์žˆ๋Š” ํฅ๋ฏธ๋กœ์šด ์ผ๋„ ๋งŽ๊ณ ์š”. ์•„์‹œ๋‹ค์‹œํ”ผ, ๋ชจ๋ธ 3์ด ์ถœ์‹œ ์˜ˆ์ •์ด๊ณ ์š”.’, ‘์˜ฌํ•ด ๋ง๊นŒ์ง€ LA์—์„œ ๋‰ด์š•๊นŒ์ง€\n์™„์ „ ์ž์œจ ์ฃผํ–‰์œผ๋กœ ํšก๋‹จํ•˜๋Š” ๊ณ„ํš์— ๋งž์ถฐ์„œ ์ง„ํ–‰ ์ค‘์ด์—์š”.\n์‚ฌ๋žŒ์ด ํ…Œ์Šฌ๋ผ์— ํƒ€์„œ ์šด์ „๋Œ€๋ฅผ ์žก์ง€ ์•Š๊ณ  “๋‰ด์š•"์„ ์ฐ์œผ๋ฉด ๊ทธ๋ฆฌ๋กœ ๊ฐ„๋‹ค๋Š” ๋ง์ด๋„ค์š”.’, ‘๊ธธ๊ฒŒ ๊ฐˆ ๊ฒƒ ๊ฐ™์ง€๋Š” ์•Š์•„์š”.\n๊ทธ๋Ÿฌ๋„ค์š”. ์ €๋Š” ์ตœ๋Œ€ํ•œ ์˜ค๋žซ๋™์•ˆ ํ…Œ์Šฌ๋ผ์— ๋จธ๋ฌผ ์ƒ๊ฐ์ด์—์š”.\n๊ทธ๋ฆฌ๊ณ  ์ค€๋น„ ์ค‘์— ์žˆ๋Š” ํฅ๋ฏธ๋กœ์šด ์ผ๋„ ๋งŽ๊ณ ์š”. ์•„์‹œ๋‹ค์‹œํ”ผ, ๋ชจ๋ธ 3์ด ์ถœ์‹œ ์˜ˆ์ •์ด๊ณ ์š”.’, ‘์˜ฌํ•ด ๋ง๊นŒ์ง€ LA์—์„œ ๋‰ด์š•๊นŒ์ง€\n์™„์ „ ์ž์œจ ์ฃผํ–‰์œผ๋กœ ํšก๋‹จํ•˜๋Š” ๊ณ„ํš์— ๋งž์ถฐ์„œ ์ง„ํ–‰ ์ค‘์ด์—์š”.\n์‚ฌ๋žŒ์ด ํ…Œ์Šฌ๋ผ์— ํƒ€์„œ ์šด์ „๋Œ€๋ฅผ ์žก์ง€ ์•Š๊ณ  “๋‰ด์š•"์„ ์ฐ์œผ๋ฉด ๊ทธ๋ฆฌ๋กœ ๊ฐ„๋‹ค๋Š” ๋ง์ด๋„ค์š”.’] RAG๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ์˜ ๋Œ€๋‹ต ์ €๋Š” ํ…Œ์Šฌ๋ผ๋ฅผ ๋งค์šฐ ๊ธ์ •์ ์œผ๋กœ ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ํ…Œ์Šฌ๋ผ๋Š” ํ˜์‹ ์ ์ธ ๊ธฐ์ˆ ๊ณผ ์ง€์† ๊ฐ€๋Šฅํ•œ ๋ฏธ๋ž˜๋ฅผ ์œ„ํ•œ ๋น„์ „์„ ๊ฐ–์ถ˜ ๊ธฐ์—…์œผ๋กœ์„œ, ์ž์œจ ์ฃผํ–‰ ๊ธฐ์ˆ ์„ ํ†ตํ•ด ์šฐ๋ฆฌ์˜ ์‚ถ์„ ํ˜์‹ ํ•˜๊ณ  ์žˆ์Šต๋‹ˆ๋‹ค. ๋˜ํ•œ, ์ „๊ธฐ์ฐจ ์‹œ์žฅ์„ ์„ ๋„ํ•˜๊ณ  ํ™˜๊ฒฝ์— ์นœํ™”์ ์ธ ์ฐจ๋Ÿ‰์„ ์ œ๊ณตํ•˜๋Š” ๋ฉ‹์ง„ ๊ธฐ์—…์ด๋ผ๊ณ  ์ƒ๊ฐํ•ฉ๋‹ˆ๋‹ค. ํ…Œ์Šฌ๋ผ์˜ ๋ฏธ๋ž˜๊ฐ€ ๋ฐ๊ณ  ํฅ๋ฏธ๋กœ์šด ์ผ๋“ค์ด ๊ณ„์†ํ•ด์„œ ์ผ์–ด๋‚  ๊ฒƒ์ด๋ผ๊ณ  ๋ฏฟ์Šต๋‹ˆ๋‹ค. ๊ณ ์ฐฐ ํ™•์‹คํžˆ RAG๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š์•˜์„ ๋•Œ๋Š” ๊ฐ๊ด€์ ์ด๊ณ  ์ผ๋ฐ˜์ ์ธ ๋Œ€๋‹ต์„ ํ•˜๋Š” ๋ฐ˜๋ฉด, RAG๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ๋Š” ํ…Œ์Šฌ๋ผ์— ๋Œ€ํ•ด ๊ธ์ •์ ์ธ ์ผ๋ก  ๋จธ์Šคํฌ์˜ ๋Œ€๋‹ต๊ณผ, ์ž์œจ์ฃผํ–‰ ๊ธฐ์ˆ ์„ ์–ธ๊ธ‰ํ–ˆ๋‹ค๋Š” ๊ฒƒ์„ ๋ฐ˜์˜ํ•˜์—ฌ ๋Œ€๋‹ต์„ ์ƒ์„ฑํ•˜์˜€๋‹ค.
new ์ปดํŒŒ์ผ๋Ÿฌ๊ฐœ๋ก 
๐Ÿซ ํ•™๊ณผ ๊ณต๋ถ€
๊ฐœ์š” ์ปดํ“จํ„ฐ์™€ ์ธ๊ฐ„์ด ์†Œํ†ตํ•˜๋Š” ๋ฐฉ๋ฒ• ์–ด์…ˆ๋ธ”๋ฆฌ์–ด ์–ด์…ˆ๋ธ”๋ฆฌ์–ด์˜ ๋ฒˆ์—ญ๊ธฐ๋Š” ์–ด์…ˆ๋ธ”๋Ÿฌ(Assembler)๋ผ๊ณ  ํ•œ๋‹ค cpu์นฉ์…‹์ด ๋ฐ”๋€”๋•Œ๋งˆ๋‹ค ์–ด์…ˆ๋ธ”๋ฆฌ์–ด๊ฐ€ ๋ฐ”๋€๋‹ค ๊ณ ๊ธ‰์–ธ์–ด ๊ณ ๊ธ‰์–ธ์–ด์˜ ๋ฒˆ์—ญ๊ธฐ๋Š” ์ปดํŒŒ์ผ๋Ÿฌ(Compiler)๋ผ๊ณ  ํ•œ๋‹ค ์ปดํŒŒ์ผ๋Ÿฌ์˜ ์ •ํ™•ํ•œ ์ •์˜ ์–ด๋–ค ์–ธ์–ด๋กœ ์“ฐ์—ฌ์ง„ ํ”„๋กœ๊ทธ๋žจ์„ ๊ฐ™์€ ์—ญํ• ์˜ ๋‹ค๋ฅธ ์–ธ์–ด๋กœ ๋ฐ”๊ฟ”์ฃผ๋Š” ํ”„๋กœ๊ทธ๋žจ 1952๋…„ ๊ทธ๋ ˆ์ด์Šค ํ˜ธํผ(Grace Hopper)๊ฐ€ UNIVAC์šฉ ํ”„๋กœ๊ทธ๋ž˜๋ฐ์–ธ์–ด A-0 ์ปดํŒŒ์ผ๋Ÿฌ๋ฅผ ์ œ์ž‘ ์ปดํŒŒ์ผ๋Ÿฌ vs ์ธํ„ฐํ”„๋ฆฌํ„ฐ ํ”„๋กœ๊ทธ๋žจ ์ฒ˜๋ฆฌ๊ณผ์ • ์ปดํŒŒ์ผ๋Ÿฌ์˜ ์ฒ˜๋ฆฌ ๊ณผ์ • Lexical analysis (์–ดํœ˜ ๋ถ„์„) token์„ ์ƒ์„ฑํ•˜๋Š”์ผ, token์€ ์–ดํœ˜์˜ ์ตœ์†Œ ๋‹จ์œ„ Syntax analysis (๊ตฌ๋ฌธ ๋ถ„์„) token์„ ์ฝ์–ด์„œ ์˜ค๋ฅ˜๋ฅผ ๊ฒ€์ƒ‰, ๊ตฌ๋ฌธ ๊ตฌ์กฐ๋ฅผ ๋งŒ๋“ ๋‹ค (์ฃผ๋กœ ํŠธ๋ฆฌํ˜•ํƒœ) Semantic analysis (์˜๋ฏธ ๋ถ„์„) type checking Intermediate code generation (์ค‘๊ฐ„ ์ฝ”๋“œ ์ƒ์„ฑ) ์ค‘๊ฐ„ ์ฝ”๋“œ๋กœ ๋ณ€ํ™˜ Code optimization (์ฝ”๋“œ ์ตœ์ ํ™”) ์ค‘๊ฐ„ ์ฝ”๋“œ๋ฅผ ๋” ํšจ์œจ์ ์œผ๋กœ ๋ณ€ํ™˜ Code generation (์ฝ”๋“œ ์ƒ์„ฑ) ๋ชฉ์  ์ฝ”๋“œ ์ƒ์„ฑ Lexical analysis (์–ดํœ˜ ๋ถ„์„) token : ๋ฌธ๋ฒ•์ ์œผ๋กœ ์˜๋ฏธ์žˆ๋Š” ์ตœ์†Œ ๋‹จ์œ„ FSA (Finite State Automata, ์œ ํ•œ ์ƒํƒœ ์˜คํ† ๋งˆํƒ€) token์„ ์ธ์‹ํ•˜๋Š” ๋ฐฉ๋ฒ• ์‹œ์ž‘ ์ƒํƒœ ํ•œ ๊ฐœ์™€ ๋ ์ƒํƒœ ์—ฌ๋Ÿฌ ๊ฐœ๋ฅผ ๊ฐ€์ง DFA (Deterministic Finite Automata) FSA์˜ ํ•œ ์ข…๋ฅ˜ ๊ฐ ์ƒํƒœ์—์„œ ๋ป—์–ด๋‚˜๊ฐ€๋Š” edge๊ฐ€ ํ•˜๋‚˜์”ฉ๋งŒ ์กด์žฌ ฮต๊ฐ€ ๋ถ™์€ edge ์—†์Œ ๋ถ„์„ํ•œ ํ† ํฐ์„ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ• Lexeme = <ํ† ํฐ๋ฒˆํ˜ธ, ํ† ํฐ ๊ฐ’> ์˜ˆ์‹œ if X < Y … (29, 0) (1, X) (18, 0) (1, Y) … ์‹๋ณ„์ž์˜ ํ† ํฐ๋ฒˆํ˜ธ๋Š” 1๋ฒˆ, ์ƒ์ˆ˜๋Š” 2๋ฒˆ ๋“ฑ์œผ๋กœ ๊ณ ์ • Syntax analysis (๊ตฌ๋ฌธ ๋ถ„์„) token์„ ์ฝ์–ด์„œ ์˜ค๋ฅ˜๋ฅผ ๊ฒ€์ƒ‰, parse tree๋ฅผ ๋งŒ๋“ ๋‹ค CFG (Context Free Grammer) ๊ตฌ๋ฌธ์„ ํ‘œํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ• G = (N, T, P, S) N = nonterminal symbol ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋กœ ํ‘œํ˜„ T = terminal symbol (token) ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž+์ˆซ์ž, ์—ฐ์‚ฐ์ž, ๊ตฌ๋ถ„์ž, ํ‚ค์›Œ๋“œ ๋“ฑ P = production rule ์˜ˆ) S -> T+T, T -> ‘0’|‘1’|‘2’ S = start symbol L(G) : ์ด ๋ฌธ๋ฒ•์œผ๋กœ ์ƒ์„ฑ๋˜๋Š” ์–ธ์–ด ์—ฌ๋Ÿฌ๊ฐ€์ง€ CFG ํ‘œํ˜„๋ฒ• BNF (Backus-Naur Form) EBNF (Extended BNF) ์œ ๋„ (derivation) ์ƒ์„ฑ ๊ทœ์น™๋ฅผ ์ ์šฉํ•˜์—ฌ ๋ฌธ์žฅ์„ ์ƒ์„ฑํ•˜๋Š” ๊ณผ์ • ์œ ๋„๋ฅผ ํ•˜๋Š” ๊ณผ์ •์—์„œ ํ•˜๋‚˜์”ฉ ๊ณจ๋ผ์„œ ๋ฐ”๊ฟˆ ์œ ๋„ ํŠธ๋ฆฌ : ์œ ๋„ ๊ฒฝ๋กœ๋ฅผ ์ถ”์ƒํ™” ์‹œ์ผœ ํ‘œํ˜„ํ•œ ๊ฒƒ ์ขŒ์ธก ์œ ๋„(leftmost derivation) ๊ฐ€์žฅ ์™ผ์ชฝ์— ์žˆ๋Š” nonterminal์„ ๋จผ์ € ๋Œ€์น˜ ์šฐ์ธก ์œ ๋„(rightmost derivation) ๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ์— ์žˆ๋Š” nonterminal์„ ๋จผ์ € ๋Œ€์น˜ ๋ชจํ˜ธ์„ฑ (ambiguity) ๋ฌธ๋ฒ• G์— ์˜ํ•ด ์ƒ์„ฑ๋˜๋Š” ์–ด๋–ค ๋ฌธ์žฅ์ด ๋‘๊ฐœ ์ด์ƒ์˜ ์œ ๋„ํŠธ๋ฆฌ๋ฅผ ๊ฐ–๋Š”๋‹ค๋ฉด ๋ฌธ๋ฒ• G๋Š” ๋ชจํ˜ธํ•˜๋‹ค๊ณ  ํ•œ๋‹ค ๋ชจํ˜ธํ•˜์ง€ ์•Š์€ ๋ฌธ๋ฒ•์€ ์ขŒ์ธก ์œ ๋„์™€ ์šฐ์ธก ์œ ๋„๊ฐ€ ๊ฐ™๋‹ค ๋ชจํ˜ธ์„ฑ ํ•ด๊ฒฐ ์—ฐ์‚ฐ์ž ์šฐ์„ ์ˆœ์œ„ ๋„์ž… ๊ฒฐํ•ฉ ๋ฒ•์น™ ๋„์ž… Left Recursion์€ ์ขŒ์ธก ๊ฒฐํ•ฉ์— ์‚ฌ์šฉ ex) A -> A+a | a Right Recursion์€ ์šฐ์ธก ๊ฒฐํ•ฉ์— ์‚ฌ์šฉ ex) A -> a+A | a ๊ตฌ๋ฌธ ๋ถ„์„์˜ 2๊ฐ€์ง€ ๋ฐฉ์‹ top-down, bottom-up Top-down parsing Top-down ๋ฐฉ์‹ ์ขŒ์ธก ์œ ๋„์™€ ๊ฐ™์€ ์ˆœ์„ ์˜ ์ƒ์„ฑ ๊ทœ์น™ ์ ์šฉ backtracking : ์œ ๋„๋œ ๋ฌธ์ž์—ด๊ณผ ์ž…๋ ฅ ๋ฌธ์ž์—ด์ด ๊ฐ™์ง€ ์•Š์œผ๋ฉด ๋‹ค๋ฅธ ์ƒ์„ฑ๊ทœ์น™ ์ ์šฉ Bottom-up ๋ฐฉ์‹ ์šฐ์ธก ์œ ๋„์˜ ์—ญ์ˆœ์˜ ์ƒ์„ฑ ๊ทœ์น™ ์ ์šฉ LL ํŒŒ์‹ฑ ์™ผ์ชฝ->์˜ค๋ฅธ์ชฝ์œผ๋กœ ์ฝ์–ด์„œ ์ขŒํŒŒ์Šค ์ƒ์„ฑ backtracking X, ๋น ๋ฅด๋‹ค ๊ฒฐ์ •์ ์œผ๋กœ ํŒŒ์‹ฑ ์‚ฌ์šฉ๋œ ์ •์˜ ฮต-์ƒ์„ฑ๊ทœ์น™ Nonterminal A๊ฐ€ ฮต๋ฅผ ์œ ๋„ํ•  ์ˆ˜ ์žˆ์œผ๋ฉด A๋ฅผ nullableํ•˜๋‹ค๊ณ  ๋ถ€๋ฅธ๋‹ค lhs, rhs A->XXX์—์„œ lhs๋Š” A, rhs๋Š” XXX โŠ• (Ring Sum) A์— ฮต๊ฐ€ ์žˆ์œผ๋ฉด, AโŠ•B = (A์—์„œ ฮต๋นผ๊ณ  A ํ•ฉ์ง‘ํ•ฉ B) A์— ฮต๊ฐ€ ์—†์œผ๋ฉด, AโŠ•B = A First nonterminal A๋กœ ๋ถ€ํ„ฐ ์œ ๋„๋˜์–ด ์ฒซ๋ฒˆ์งธ๋กœ ๋‚˜ํƒ€๋‚  ์ˆ˜ ์žˆ๋Š” terminal์˜ ์ง‘ํ•ฉ X->Y1Y2Y3์ผ๋•Œ, FIRST(X) = FIRST(X) U FIRST(Y1) โŠ• FIRST(Y2) โŠ• FIRST(Y3) Follow A ๋‹ค์Œ์— ๋‚˜์˜ค๋Š” terminal์˜ ์ง‘ํ•ฉ A->ฮฑBฮฒ, ฮฒ != ฮต ์ผ๋•Œ, FOLLOW(B) = FOLLOW(B) U (FIRST(ฮฒ)-{ฮต}) A->ฮฑB ๋˜๋Š” A->ฮฑBฮฒ, FIRST(ฮฒ)์— ฮต๊ฐ€ ์†ํ•  ๋•Œ, FOLLOW(B) = FOLLOW(B) U FOLLOW(A) LL์กฐ๊ฑด FIRST(ฮฑ)์™€ FIRST(ฮฒ)๊ฐ€ ๊ฒน์น˜๋ฉด ์•ˆ๋œ๋‹ค FIRST(ฮฑ)์— ฮต๊ฐ€ ์žˆ์œผ๋ฉด, FOLLOW(ฮฑ)์™€ FIRST(ฮฒ)๊ฐ€ ๊ฒน์น˜๋ฉด ์•ˆ๋œ๋‹ค LL ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” ๋ฌธ๋ฒ• = LL ํŒŒ์‹ฑ ๋˜๋Š” ๋ฌธ๋ฒ• LL(1) ๋ฌธ๋ฒ• ์ž„์˜์˜ ๋ฌธ๋ฒ•์— ๋Œ€ํ•˜์—ฌ LL ์กฐ๊ฑด์„ ๋งŒ์กฑํ•˜๋Š” CFG 1 : LOOKAHEAD๊ฐ€ 1๊ฐœ๋ผ๋Š” ์˜๋ฏธ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ๊ฒฝ์šฐ LL(1)๋ฌธ๋ฒ•์ด ๋˜์ง€ ์•Š๋Š”๋‹ค ๋ชจํ˜ธํ•œ ๋ฌธ๋ฒ• ์šฐ์„ ์ˆœ์œ„ ์ฃผ๊ธฐ, ๊ฒฐํ•ฉ๋ฒ•์น™ ๋ฐ˜์˜์œผ๋กœ ํ•ด๊ฒฐ left-factoring์ด ๋˜๋Š” ๊ฒฝ์šฐ ๊ณตํ†ต ์•ž๋ถ€๋ถ„์„ ์ƒˆ๋กœ์šด nonterminal๋กœ ๋งŒ๋“ค์–ด ํ•ด๊ฒฐ left-recursiveํ•œ ๊ฒฝ์šฐ ์ง์ ‘ recursion : A -> Aฮต ์ธ๊ฒฝ์šฐ ๊ฐ„์ ‘ recursion : A -> B, B -> A ์ธ๊ฒฝ์šฐ LOOKAHEAD ์–ด๋–ค ๊ทœ์น™์ด ์ ์šฉ๋˜์—ˆ์„๋•Œ ๋งจ ์ฒ˜์Œ ๋‚˜์˜ฌ ์ˆ˜ ์žˆ๋Š” terminal ์ง‘ํ•ฉ A->X1X2X3์ผ๋•Œ, LOOKAHEAD(A) = FIRST(X1) โŠ• FIRST(X2) … โŠ• FOLLOW(A) Strong LL(1) LL(1)๊ณผ ํ•ญ์ƒ ๋™์ผ (1์ด ์•„๋‹๋•Œ๋Š” ๋‹ค๋ฆ„) LOOKAHEAD(A->ฮฑ)์™€ LOOKAHEAD(A->ฮฒ)๊ฐ€ ๊ฒน์น˜์ง€ ์•Š๋Š” ๋ฌธ๋ฒ• LL(1) ํŒŒ์„œ ๊ตฌํ˜„ ๋ฐฉ๋ฒ• Recursive descent parser ์žฅ์  : ์ง๊ด€์  ์‰ฝ๋‹ค ๋‹จ์  : ์ƒ์„ฑ ๊ทœ์น™์ด ๋ฐ”๋€Œ๋ฉด ๊ตฌ๋ฌธ ๋ถ„์„๊ธฐ๋ฅผ ๊ณ ์ณ์•ผ ํ•œ๋‹ค Predictive parser PDA(PushDown Automata)์— ๊ธฐ๋ฐ˜ ์ƒ์„ฑ ๊ทœ์น™์ด ๋ฐ”๋€Œ๋ฉด ํŒŒ์‹ฑ ํ…Œ์ด๋ธ”๋งŒ ์ˆ˜์ • ํŒŒ์‹ฑํ…Œ์ด๋ธ” ์˜ˆ์‹œ (?์—๋Š” ๊ทœ์น™๋ฒˆํ˜ธ๊ฐ€ ๋“ค์–ด๊ฐ„๋‹ค) a b S ? ? A ? ? ํŒŒ์‹ฑํ…Œ์ด๋ธ”์— ๋‘๊ฐœ ์ด์ƒ์˜ ์ƒ์„ฑ ๊ทœ์น™์ด ๋“ค์–ด๊ฐ€๋Š” ๊ฒฝ์šฐ -> NOT LL(1) Stack์˜ ์˜ˆ์‹œ Bottom-up parsing left-recursive ๋ฌธ๋ฒ•๋„ ํŒŒ์‹ฑ ๊ฐ€๋Šฅ LL(k) ์ขŒ์ธก์œ ๋„ ๊ธฐ๋ฐ˜ k๊ฐœ์˜ symbol์„ lookahead Top-down parsing, recursive descent parsing, predictive parsing, LL parser ํŒŒ์ŠคํŠธ๋ฆฌ๋ฅผ pre-roder๋กœ ์ˆœํšŒ ๋ฐ ์ƒ์„ฑ LR(k) ์šฐ์ธก์œ ๋„ ๊ธฐ๋ฐ˜ k๊ฐœ์˜ symbol์„ lookahead Bottom-up parsing, shift-reduce parsing, LR parser ํŒŒ์ŠคํŠธ๋ฆฌ๋ฅผ post-order๋กœ ์ˆœํšŒ ๋ฐ ์ƒ์„ฑ Reduce S=>ฮฑฮฒฯ‰์ด๊ณ  A->ฮฒ์ด๋ฉด ฮฒ๋ฅผ A๋กœ ๋Œ€์น˜ํ•˜๋Š” ๊ฒƒ : S=>ฮฑAฯ‰ ์‹œ์ž‘ symbol์ด ๋‚˜์˜ฌ ๋•Œ๊นŒ์ง€ reduce ํ•œ๋‹ค Handle S=>ฮฑฮฒฯ‰์ด๊ณ  A->ฮฒ์ด๋ฉด ฮฒ๋ฅผ ฮฑฮฒฯ‰์˜ handle์ด๋ผ๊ณ  ํ•œ๋‹ค ๋‘ ๊ฐœ ์ด์ƒ์˜ handle์ด ์กด์žฌํ• ๋•Œ -> ๋ชจํ˜ธํ•˜๋‹ค Shift์™€ Reduce๋กœ Parsing ํ•˜๊ธฐ Stack์˜ ์˜ˆ์‹œ Issue Shift์™€ Reduce ์ค‘ ์–ด๋А ๊ฒƒ์„ ํ• ๊นŒ? Stack์˜ top์—์„œ ์–ผ๋งˆ๋งŒํผ์„ handle๋กœ ๋ณผ ๊ฒƒ์ธ๊ฐ€? ํ•ด๊ฒฐ๋ฐฉ๋ฒ•: LR Parsing Table YACC LALR ํŒŒ์„œ ์ƒ์„ฑ๊ธฐ foo.y –(yacc)–> y.tab.c –(gcc)–> a.out *.y ํŒŒ์ผ ๊ตฌ์กฐ 1<์„ ์–ธ๋ถ€> 2... 3%% 4... 5exp : exp '+' term; 6factor : ident; 7... 8%% 9<์—ฌ๋Ÿฌ ํ•จ์ˆ˜> ๋ชจํ˜ธํ•œ ๋ฌธ๋ฒ•์œผ๋กœ LR Conflict ๋ฐœ์ƒ ์‹œ ์„ ์–ธ๋ถ€์—์„œ ์šฐ์„ ์ˆœ์œ„ ์ง€์ •ํ•˜์—ฌ ํ•ด๊ฒฐ LR Parsing Table Action table : Action + Parser ์ƒํƒœ Goto table : Parser ์ƒํƒœ LR(0) ํŒŒ์‹ฑ ํ…Œ์ด๋ธ” ๋งŒ๋“ค๊ธฐ LR(0) ์•„์ดํ…œ rhs์— ์ (’.’) symbol์„ ๊ฐ€์ง„ ์ƒ์„ฑ ๊ทœ์น™ ex) A->ฮฑ.ฮฒ, A->. closure ์ (’.’)๋’ค์— non-terminal์ด ์˜ค๋ฉด ์žฌ๊ท€์ ์œผ๋กœ ์ถ”๊ฐ€ S’ -> S, S -> (L)|id, L -> S | L,S closure({[S’->.S]}) = {[S’->.S], [S->.(L)], [S->.id]} goto goto(I, X)์ด๋ฉด ์ ์„ X๋’ค๋กœ ์˜ฎ๊ธฐ๊ณ  closure๋ฅผ ์ทจํ•œ๋‹ค X๊ฐ€ ์—†์œผ๋ฉด ๋„ฃ์ง€ ์•Š๋Š”๋‹ค I={[G->E=E], [E->E.+T]} ์ผ๋•Œ, goto(I, +) = closure({E->E+.T}) : ์ ์„ +๋’ค๋กœ ์˜ฎ๊น€ C0 ์ƒ์„ฑ๊ทœ์น™ S’->S์—์„œ๋ถ€ํ„ฐ ์ฐจ๋ก€๋กœ closure์™€ goto๋ฅผ ์ ์šฉํ•˜์—ฌ ์–ป์€ ๋ชจ๋“  ํƒ€๋‹นํ•œ LR(0)์˜ ์•„์ดํ…œ ์ง‘ํ•ฉ๋“ค Item์˜ ์ข…๋ฅ˜ [A->X.Y] : X!=ฮต์ผ๋•Œ kernel item [A->.X] : closure item [A->X.] : reduce item SLR ํŒŒ์‹ฑ ํ…Œ์ด๋ธ” ๋งŒ๋“ค๊ธฐ reduce Item์ด [X->ฮฑ.]์ผ๋•Œ, FOLLOW(X)์˜ ๋ชจ๋“  terminal์—๋งŒ reduce action์„ ๋„ฃ๋Š”๋‹ค ๋‚˜๋จธ์ง€๋Š” LR(0)๊ณผ ๋˜‘๊ฐ™๋‹ค LR(0)๋ณด๋‹ค conflict๊ฐ€ ์ ์–ด, ๋” ์ •๊ตํ•˜๋‹ค๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. LALR Parsing ์ •๊ตํ•œ ์ˆœ์„œ LR(0) < SLR < LALR(1) < LR(1) ํŒŒ์„œ ์ƒํƒœ์˜ ๊ฐœ์ˆ˜ SLR = LALR « LR(1) SDD, AST SDD (Syntax Directed Definition) SDD : semnatic action์„ ์ •์˜ํ•˜๋Š” ์ถ”์ƒ์ ์ธ ๋ช…์„ธ์„œ Semnatic Actions : ๊ทœ์น™์— ๋Œ€ํ•œ Action Yacc/Bison : $$, $1, $2, ... ์‚ฌ์šฉ ANTLR : $<name> ์‚ฌ์šฉ Type declaration Attribute ์ข…๋ฅ˜ synthesized attr. : children์— ์˜ํ•ด ๊ณ„์‚ฐ (terminal) inherited attr. : parent, sibling์— ์˜ํ•ด ๊ณ„์‚ฐ AST (Abstract Syntax Tree) ํŒŒ์ŠคํŠธ๋ฆฌ์—์„œ ๋ถˆํ•„์š”ํ•œ ์ •๋ณด๋ฅผ ์ œ๊ฑฐํ•œ ํ˜•ํƒœ AST๋ฅผ ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ• ํŒŒ์‹ฑ๋‹จ๊ณ„์—์„œ ๋งŒ๋“ค๊ธฐ : LL, LR ํŒŒ์ŠคํŠธ๋ฆฌ๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ๋งŒ๋“ค๊ธฐ : SDD ์‚ฌ์šฉ (Yacc etc.) evaluation : ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ•˜๋ฉด์„œ ์ž‘์—…ํ•˜๋Š” ํ–‰์œ„ On-the-fly evaluation S-attributed SDD: synthesized attribute๋งŒ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” SDD L-attributed SDD: synthesized attribute๋งŒ ๊ฐ€์ง€๋Š” ๊ฒฝ์šฐ + ๊ฐ’์ด ์™ผ์ชฝ์—์„œ ์˜ค๋ฅธ์ชฝ์œผ๋กœ ํ˜๋Ÿฌ ๊ณ„์‚ฐ์ด ์ด๋ฃจ์–ด์ง€๋Š” ๊ฒฝ์šฐ IR (Intermediate Representation) IR์ด๋ž€? Tree๋‚˜ Instruction list ํ˜•ํƒœ instruction(node)๊ฐ€ ์ ์–ด์•ผ ์ตœ์ ํ™”/๋ฒˆ์—ญ์— ์ข‹์Œ High Level IR High์™€ Low๋Š” ์ƒ๋Œ€์ ์ธ ๊ฐœ๋… High level IR: ์—ฌ๊ธฐ์„œ๋Š” AST์˜ ๋ณ€ํ˜•๋งŒ ์ƒ๊ฐ ์ข…๋ฅ˜ : AST, TCOL Low Level IR ๋‹จ์ˆœํ•œ instruction์œผ๋กœ ๊ตฌ์„ฑ ๊ฐ€์ƒ๊ธฐ๊ณ„(์ฃผ๋กœ RISC)๋ฅผ emulate N-tuple ํ‘œ๊ธฐ๋ฒ• (3-address code) a = b OP c ์ผ๋ฐ˜์ ์œผ๋กœ ๊ธฐ๊ณ„์–ด๊ฐ€ ๊ฐ€์ง€๋Š” ํ”ผ์—ฐ์‚ฐ์ž ๊ฐœ์ˆ˜ <= 3 quadruple : (์—ฐ์‚ฐ์ž, ํ”ผ์—ฐ์‚ฐ์ž1, ํ”ผ์—ฐ์‚ฐ์ž2, ๊ฒฐ๊ณผ) Stack machine code Java byte code, U-code : AST๋กœ๋ถ€ํ„ฐ ์ƒ์„ฑ์ด ์šฉ์ด Tree ํ‘œํ˜„ ๊ธฐ๊ณ„์–ด ์ƒ์„ฑ ์šฉ์ด IR ์˜ˆ์‹œ GCC - GIMPLE (3-address code) GCC์˜ ์ค‘๊ฐ„์ฝ”๋“œ : GENERIC -> GIMPLE -> RTL 1D.1954 = x*10 // D.1954๋Š” ์ž„์‹œ๋ณ€์ˆ˜ 2gimple_assign <mult_exprt, D.1954, x, 10> LLVM - bit (3-address code) LLVM IR : ์–ธ์–ด์™€ ๋จธ์‹ ์— ๋…๋ฆฝ์  1@var = global i32 14 ; ์ „์—ญ๋ณ€์ˆ˜ var์— 14 ๋Œ€์ž… 2define i32 @main() nounwind { ; i32(int) ๋ฐ˜ํ™˜ํ˜• 3 entry: 4 %a = alloca i32, align 4 ; ์ง€์—ญ๋ณ€์ˆ˜ a ์„ ์–ธ, int ํ• ๋‹น 5 %1 = load i32 * @var ; %1 ์ž„์‹œ๋ณ€์ˆ˜์— var๊ฐ’ ๋Œ€์ž… 6 ret i32 %1 ; ์ž„์‹œ๋ณ€์ˆ˜ ๊ฐ’ ๋ฐ˜ํ™˜ 7} JVM - byte code (stack machine code) ๊ฐ€์ƒ ๊ธฐ๊ณ„ ์ฝ”๋“œ (Bytecode, MSIL) ๊ฐ€์ƒ ๊ธฐ๊ณ„์—์„œ ๋™์ž‘ํ•˜๋„๋ก ํ•จ ์ด์‹์„ฑ, ํ˜ธํ™˜์„ฑ์ด ๋ชฉ์  : java bytecode๋Š” machine ํ˜ธํ™˜์„ฑ, c# msil์€ language ํ˜ธํ™˜์„ฑ 1public Employee(String strName, int num) 2{name = strName; idNumber = num; storeData(strName, num);} 3Method Employee(java.lang.String, int) 4 50 aload_0 ; 0๋ฒˆ์งธ ๋กœ์ปฌ๋ณ€์ˆ˜(this)๋ฅผ ์Šคํƒ์— push 61 invokespecial #3 <Method java.lang.Object()> ; ํ•จ์ˆ˜ ํ˜ธ์ถœ 7--- 84 aload_0 95 aload_1 ; strName์„ ์Šคํƒ์— push 106 putfield #5 <Field java.lang.String name> ; name์— strName ๋Œ€์ž… 11--- 129 aload_0 1310 iload_2 ; num์„ ์Šคํƒ์— push 1411 putfield #7 <Field int idNumber> ; idNumber์— num ๋Œ€์ž… 15--- 1614 aload_0 1715 aload_1 ; strName์„ ์Šคํƒ์— push 1816 iload_2 ; num์„ ์Šคํƒ์— push 1917 invokespecial #9 <Method void storeData(java.lang.String, int)> ; ํ•จ์ˆ˜ ํ˜ธ์ถœ 2020 return line number : ๋ช…๋ น์ด ์‹œ์ž‘ํ•˜๋Š” ๋ฐ”์ดํŠธ ์ฃผ์†Œ aload : ๊ฐ์ฒด๋ฅผ push, iload : ์ •์ˆ˜๋ฅผ push ์›๋ž˜๋Š” aload๊ฐ€ ๋ช…๋ น, ์ž์ฃผ ์“ฐ๋Š” ๋ช…๋ น aload 0์„ ๋ฌถ์–ด์„œ bind -> aload_0 CIL (Common Intermediate Language) (stack machine code) C#, VB.NET, J# ๋“ฑ์—์„œ ์‚ฌ์šฉ MSIL์€ ์˜›๋‚  ์ด๋ฆ„ 1.assembly Hello {} ; .assembly: ์–ด์…ˆ๋ธ”๋ฆฌ ์„ ์–ธ 2.assembly extern mscorlib {} 3.method static void Main() { 4 .entrypoint 5 .maxstack 1 6 ldstr "Hello, world!" ; stack์— ์ €์žฅ 7 call void [mscorlib]System.Console::WriteLine(string) 8 ret 9} GCC RTL(Register Transfer Language) (Tree๊ตฌ์กฐ ์ฝ”๋“œ) Lisp S-expression ์‚ฌ์šฉ 1(set (reg:SI 140) 2 (plus:SI (reg:SI 138) 3 (reg:SI 139))) => reg140 = reg138+reg139 IR generation 3-address Translation ๊ทœ์น™ Binary operations: t = [[el OP e2]] Unary operations: t = [[OP el]] Array access: t = [[ v[e] ]] Structure access: t = [[ v.f ]] Short-circuit OR: t = [[ el SC-OR e2]] Statement sequence: [[s1; s2; ...; sN]] Variable assignment: [[ v = e ]] Array assignment: [[ v[e1] = e2 ]] If: [[ if(e) then s ]], [[ if(e) then s1 else s2]] While: [[ while (e) s ]] Switch: [[ switch (e) case v1:s1, ..., case vN:sN ]] Function Call: [[ call f(e1, e2, ..., eN) ]] Fucntion Return: [[ return e ]] Statement Expression Statement๋„ expression ์ฒ˜๋Ÿผ ๊ฐ’์„ ๊ฐ€์ง€๋„๋ก ํ™•์žฅ t = [[ S ]]๋ฅผ ์ถ”๊ฐ€ํ•˜์—ฌ ๊ฒฐ๊ณผ๊ฐ’์„ ์ €์žฅํ•˜์ž Nested Expressions t = [[ (a - b) * (c + d) ]] t = [[ if c then if d then a = b ]] ๊ฐ€์žฅ ํฐ ๋ฉ์–ด๋ฆฌ๋ถ€ํ„ฐ ๋ฐ”๊พผ๋‹ค Storage Management 2๊ฐ€์ง€ Storage Register : ๋น ๋ฅธ ์ ‘๊ทผ, ๊ฐ„์ ‘ ์ ‘๊ทผ ๋ถˆ๊ฐ€ Memory : ์ƒ๋Œ€์ ์œผ๋กœ ๋А๋ฆฐ ์ ‘๊ทผ, ๊ฐ„์ ‘ ์ ‘๊ทผ ๊ฐ€๋Šฅ 2๊ฐ€์ง€ ์ ‘๊ทผ ๋ฐฉ์‹ All memory approach ๋ชจ๋“  ๋ณ€์ˆ˜๋ฅผ memory์— ์ €์žฅ, ๊ฐ€๋Šฅํ•œ๊ฒƒ๋งŒ register Standard approach Global, Statics, Local(composite)๋Š” memory์— ์ €์žฅ Local(scalar)๋Š” memory ๋˜๋Š” virtual register์— ์ €์žฅ Memory์˜ 4๋Œ€ ์˜์—ญ Code space : ๋ช…๋ น์–ด๋ฅผ ์ €์žฅ read-only์ผ๋•Œ ๋น ๋ฆ„ Static data : ํ”„๋กœ๊ทธ๋žจ๊ณผ lifetime์„ ํ•จ๊ป˜ํ•˜๋Š” ๋ฐ์ดํ„ฐ Stack : Local ๋ณ€์ˆ˜๋“ค Heap : ๋™์ ์œผ๋กœ ํ• ๋‹น๋˜๋Š” ๋ฐ์ดํ„ฐ File Format Windows : PE (Portable Executable) Unix : ELF (Executable and Linkable Format) ๋ณ€์ˆ˜ ๋ฐ”์ธ๋”ฉ environment : <๋ณ€์ˆ˜, storage location> ์ •๋ณด state: <๋ณ€์ˆ˜, ๊ฐ’> ์ •๋ณด ์–ด๋–ค ๋ณ€์ˆ˜ N์ด storage location S์— ์ง€์ •๋˜๋ฉด ๋ฐ”์ธ๋”ฉ ๋œ๋‹ค๊ณ  ํ•œ๋‹ค Static Allocation ํ”„๋กœ๊ทธ๋žจ ์ˆ˜ํ–‰ํ•˜๋Š” ๋™์•ˆ ๋ณ€ํ•˜์ง€ ์•Š๋Š” location์œผ๋กœ ๋ฐ”์ธ๋”ฉ Heap Allocation ์—ฐ์†์ ์ธ global ์˜์—ญ์˜ ์ผ๋ถ€๋ฅผ OS๋กœ๋ถ€ํ„ฐ ๋ฐ›์€ ๊ฒƒ ํ”„๋กœ๊ทธ๋žจ ์ˆ˜ํ–‰ ์ค‘ ์š”์ฒญ๊ณผ ๋ฐ˜ํ™˜ Stack Management Run-time stack : ํ•œ ํ•จ์ˆ˜ call๋งˆ๋‹ค ํ•˜๋‚˜์”ฉ๋‘๋Š” frames Activation record : ํ•จ์ˆ˜ ์ˆ˜ํ–‰์„ ์œ„ํ•œ execution env(local var, parameter, return address, etc.) Top frame : ํ˜„์žฌ ์ˆ˜ํ–‰์ค‘์ธ ํ•จ์ˆ˜์˜ frame Stack pointers SP : Frame top FP : Frame base ๋‘ ๊ฐœ๋ฅผ ์“ฐ๋Š” ์ด์œ  ๊ฐ€๊นŒ์šด ๊ฑฐ ๊ธฐ์ค€์œผ๋กœ offset ๊ณ„์‚ฐ -> small offset ์œ ์ง€ ์ˆ˜ํ–‰ ์ค‘ top frame์˜ ์œ„์น˜๋ฅผ ์•Œ ์ˆ˜ ์—†์Œ Semantic Analysis - Symbol Tables Scope Identifier: ์‹๋ณ„์ž Lexical Scope: ํŠน์ • ๋ฒ”์œ„ ์‹๋ณ„์ž์˜ Scope: ๊ทธ ์‹๋ณ„์ž์˜ ์„ ์–ธ์ด ์ฐธ์กฐ๋˜๋Š” lexical scope Symbol Table Name Kind Type Attribute foo func int, int -> int extern m arg int tmp var char const ํ•˜๋‚˜์˜ lexical๋งˆ๋‹ค ํ•˜๋‚˜์˜ symbol table symbol table์€ ๊ณ„์ธต์ ์ด๋‹ค ํ˜„์žฌ scope์— ์—†์œผ๋ฉด ์ƒ์œ„ scope๋กœ ์˜ฌ๋ผ๊ฐ€๋ฉด์„œ ์ฐพ๋Š”๋‹ค Symbol Table Implementation AST๊ฐ€ ๋งŒ๋“ค์–ด์ ธ์•ผ ๊ฐ€๋Šฅ Local Table์€ hash table ์‚ฌ์šฉ Global Table์€ N-array tree ๊ตฌ์กฐ ์‚ฌ์šฉ ์ฝ”๋“œ๋ฅผ ์ˆœ์ฐจ๋Œ€๋กœ ์ฝ์œผ๋ฉด์„œ ๋งŒ๋“ฌ (scope ์Šคํƒ์„ ์‚ฌ์šฉ) Type Checking Type Expressions Array types: T[], T[10] Structure types : {id1: T1, id2: T2 …} Pointer types: T* Function types: T1 X T2 X … X Tn -> T_return Type Judgement A โ”œ E : T A ์ƒํ™ฉ์—์„œ E๋Š” Tํƒ€์ž…์„ ๋งŒ์กฑํ•œ๋‹ค A โ”œ if(E) S1 else S2 : T ์œ„ ์กฐ๊ฑด์€ ๋ชจ๋“  E, S1, S2, A, T์— ๋Œ€ํ•œ ๊ฐ€์ •์ด ์„ฑ๋ฆฝํ•  ๋•Œ ๊ฒฐ๋ก  T๊ฐ€ ์„ฑ๋ฆฝํ•œ๋‹ค Proof Tree (ํƒ€์ž… ์œ ๋„ ํŠธ๋ฆฌ) ์—ญ์‚ผ๊ฐํ˜• ๋ชจ์–‘ ๋งŒ์กฑํ•˜๋Š” proof tree๊ฐ€ ์žˆ๋‹ค -> ํƒ€์ž… ์˜ค๋ฅ˜๊ฐ€ ์—†๋‹ค ๊ทธ ์™ธ Semantic Analyses break, continue, goto ๋ฌธ์ด ์˜ฌ๋ฐ”๋ฅธ ์œ„์น˜์— ์žˆ๋Š” ์ง€ ๋“ฑ ์ปดํŒŒ์ผ๋Ÿฌ ํ›„๋ฐ˜๋ถ€ (๋น ๋ฅด๊ณ , ์‹ค์ œ ๋Œ์•„๊ฐ€๋Š” ์ฝ”๋“œ๋กœ ๋ฐ”๊พธ๊ธฐ) Instruction Selection Tree ๊ธฐ๋ฐ˜ Intermediate Representation MEM(e) : ์ฃผ์†Œ e๋กœ ์‹œ์ž‘ํ•˜๋Š” ๋ฉ”๋ชจ๋ฆฌ ํ•œ word์˜ ๋‚ด์šฉ TEMP(t) : ๋ ˆ์ง€์Šคํ„ฐ t SEQ(s1, s2): ๋ฌธ์žฅ s1 ์ˆ˜ํ–‰ ํ›„ s2 ์ˆ˜ํ–‰ ESEQ(s, e): ๋ฌธ์žฅ s ์ˆ˜ํ–‰ ํ›„ (๊ฒฐ๊ณผ ์—†์Œ) e๊ฐ€ ์ถ”๊ฐ€ ์ˆ˜ํ–‰ BINOP(o, e1, e2) : ์—ฐ์‚ฐ์ž o, ํ”ผ์—ฐ์‚ฐ์ž e1, e2, ๊ฒฐ๊ณผ ์ €์žฅ๋œ ์ฃผ์†Œ ๋ฐ˜ํ™˜ const(i): ์ •์ˆ˜ ์ƒ์ˆ˜ i Register Allocation ์ตœ์ ํ™” ํ•˜๊ธฐ ์œ„ํ•ด ์ตœ๋Œ€ํ•œ ์ž์ฃผ ์‚ฌ์šฉ๋˜๋Š” ๊ฒƒ์„ Register์— ์ €์žฅ Interference ์„œ๋กœ ๋‹ค๋ฅธ ๋‘ definition์ด live range ์—์„œ ๊ณตํ†ต operation์„ ๊ฐ€์ง€๊ณ ์žˆ๋Š” ๊ฒฝ์šฐ Interference Graph : ์„œ๋กœ interfere ํ•˜๋ฉด ์—ฐ๊ฒฐํ•˜๋Š” ๊ทธ๋ž˜ํ”„ Graph coloring : ์—ฐ๊ฒฐ๋œ ๋…ธ๋“œ๋Š” ๋‹ค๋ฅธ ์ƒ‰์œผ๋กœ ์น ํ•˜๊ธฐ Instruction Scheduling instruction์˜ ์ˆœ์„œ๋ฅผ ๋ฐ”๊พธ์–ด stall ๊ฐœ์ˆ˜ ๋“ฑ์„ ์ค„์—ฌ์„œ ์ˆ˜ํ–‰์†๋„๋ฅผ ๋†’์ด๋Š” ๊ฒƒ stall : ๋‹ค๋ฅธ ๋ช…๋ น์–ด ์ˆ˜ํ–‰์„ ๊ธฐ๋‹ค๋ฆฌ๋А๋ผ CPU๋ฅผ ๋‚ญ๋น„ํ•˜๋Š” ๊ฒƒ ๋ชฉํ‘œ Wasting time์„ ์ค„์ธ๋‹ค ๋™์ผํ•œ ์ฝ”๋“œ๊ฐ€ ๋‚˜์™€์•ผํ•œ๋‹ค register spilling์„ ํ”ผํ•ด์•ผํ•œ๋‹ค Static scheduling ๋‹จ๊ณ„ Local basic scheduling, Loop scheduling, global scheduling Local basic scheduling List scheduling : greedy, heuristic, local technique ์‚ฌ์šฉ precedence graph๋ฅผ ๋งŒ๋“ ๋‹ค ๊ฐ ๋…ธ๋“œ์— priority function์„ ์ ์šฉํ•œ๋‹ค “ready-operation queue"๋ฅผ ์—์„œ ready operation์„ ํ•˜๋‚˜ ์„ ํƒ ํ›„ scheduling, ready operation queue๋ฅผ ์—…๋ฐ์ดํŠธํ•œ๋‹ค. Longest latency-weighted path๋ฅผ ์ด์šฉํ•ด์„œ ์šฐ์„ ์ˆœ์œ„๋ฅผ ์ •ํ•œ๋‹ค ๊ธฐํƒ€ Optimization ๋ฐฉ๋ฒ• addr r1 1 -> inc r1 ํŠน์ˆ˜ ์„ฑ์งˆ์˜ ๋ ˆ์ง€์Šคํ„ฐ ํ™œ์šฉ ํŠน์ˆ˜ ๋ชฉ์ ์˜ ๋ช…๋ น์–ด ํ™œ์šฉ Register ๊ฐ„ mov ์ œ๊ฑฐ ์ค‘๋ณต๋œ load ์ œ๊ฑฐ Control Flow Optimizations(์ตœ์ ํ™”) ์ฃผ์–ด์ง„ ์ž…๋ ฅ ํ”„๋กœ๊ทธ๋žจ์„ ์ข€ ๋” ํšจ์œจ์ ์ธ ์ฝ”๋“œ๋กœ ๋ฐ”๊พธ๋Š” ๊ฒƒ ์—ฌ๋Ÿฌ๊ฐ€์ง€ ๋ถ„๋ฅ˜ ๋ฐฉ๋ฒ• ๋ถ„์„ : Control Flow Analysis vs Data Flow Analysis ์ตœ์ ํ™” Inner basic block(local) vs Inter basic block(global) Cyclic code opt vs Acyclic code opt Control Flow Analysis Control Flow ํ”„๋กœ๊ทธ๋žจ์˜ ๊ฐ€๋Šฅํ•œ ์ˆ˜ํ–‰์ˆœ์„œ (๋ถ„๊ธฐ) Branch Execution -> dynamic control flow : ์‹คํ–‰ ํ•ด๋ด์•ผ ํ™•์ธ ๊ฐ€๋Šฅ Compiler -> static control flow : ์ปดํŒŒ์ผ๋Ÿฌ๊ฐ€ ๋ถ„์„ํ•ด์„œ ์•Œ ์ˆ˜ ์žˆ์Œ Analysis ์ •์  ์„ฑ์งˆ (static property): ํ”„๋กœ๊ทธ๋žจ ์ˆ˜ํ–‰ ์—†์ด ๋„์ถœ ๋˜๋Š” ์„ฑ์งˆ CFA(Control Flow Analysis) : ์ฝ”๋“œ์˜ ๋ถ„๊ธฐ ๊ตฌ์กฐ๋ฅผ CFG ํ˜•ํƒœ๋กœ ํ‘œํ˜„ Basic Block ๋™์ผํ•œ execution condition์„ ์ ์šฉ๋ฐ›๋Š” instruction ๋ฌถ์Œ instruction ์™ธ์—๋Š” branch๊ฐ€ ์—†์Œ Maximal basic block ๊ตฌํ•˜๊ธฐ BB์˜ leader(์ฒซ๋ฒˆ์งธ instruction)๋ฅผ ์ฐพ๋Š”๋‹ค ๋‹ค์Œ leader ์ด์ „๊นŒ์ง€์˜ instruction์„ ๊ตฌํ•œ๋‹ค Weighted CFG Profiling: ๋ฐ˜๋ณตํ•ด์„œ ์ˆ˜ํ–‰ํ•ด๋ณด๋ฉด์„œ ์‹คํ–‰ํšŸ์ˆ˜๋ฅผ ์–ป์Œ ์–ป์€ weight๋ฅผ edge์— ํ‘œ์‹œ Control Flow Optimization Acyclic Code Loop๊ฐ€ ์—†๋Š” ์ฝ”๋“œ ๋ถ„์„ ๋ฐ ์ตœ์ ํ™”๊ฐ€ ์ƒ๋Œ€์ ์œผ๋กœ ์‰ฌ์›€ ์ข…๋ฅ˜ Inner basic block opt. = Intra opt. = Local opt. Inter basic block opt. = Global opt. Inner Basic Block Optimization Commn subexpression elimination ๊ณตํ†ต๋œ ๋ถ€๋ถ„์ด ์žˆ์œผ๋ฉด ํ•œ๋ฒˆ๋งŒ ๊ณ„์‚ฐ Algebraic simplification ๋Œ€์ˆ˜๋ฒ•์น™์„ ์ด์šฉํ•˜์—ฌ ์‹์„ ๊ฐ„์†Œํ™” ex) x=1*y; -> x=y; Strength reduction ์—ฐ์‚ฐ์ž์˜ ๋น„์šฉ์ด ์ ์€ ๊ฒƒ์œผ๋กœ ๋ฐ”๊พธ๊ธฐ ex) x=x*2; -> x=x+x; ex) y=a/4; -> y=a>>2; Constant folding / propagation folding: ์ปดํŒŒ์ผ ์‹œ๊ฐ„์— ์ƒ์ˆ˜์‹์„ ์ง์ ‘์‹œ๊ฐ„ propagation : ๊ณ ์ •๋œ ๊ฐ’์„ ๊ฐ€์ง€๋Š” ๋ณ€์ˆ˜๋ฅผ ์ƒ์ˆ˜๋กœ ๋Œ€์ฒด Inter Basic Block Optimization Global application of inner basic block optimization Global common subexpression elimination basic block ๊ฐ„์˜ ๊ณตํ†ต ๋ถ€๋ถ„์‹์— ๋Œ€ํ•ด ํ•œ๋ฒˆ๋งŒ ๊ณ„์‚ฐ Global constant folding / propagation basic block ๊ฐ„์˜ ์ƒ์ˆ˜๋ฅผ ์ธ์‹ํ•˜์—ฌ ํ•œ๋ฒˆ๋งŒ ๊ณ„์‚ฐ Other transformation Branch to unconditional branch ๋ถˆํ•„์š”ํ•œ ๋ถ„๊ธฐ ์ œ๊ฑฐ Unconditional branch to branch ๋ถ„๊ธฐ ํ›„ ๋ฐ”๋กœ ๋ถ„๊ธฐ -> ๋ถ„๊ธฐ ํ•œ๋ฒˆ์œผ๋กœ ๋ณ€๊ฒฝ Branch to next basic block (next instr) ๋ถ„๊ธฐ ํ›„ ๋ฐ”๋กœ ๋‹ค์Œ basic block์œผ๋กœ ๋ถ„๊ธฐ ์ œ๊ฑฐ Basic block merging ๋‘ basic block์„ ํ•ฉ์นจ Branch to same target ๊ฐ™์€ basic block์œผ๋กœ ๋ถ„๊ธฐํ•˜๋Š” ๊ฒƒ์„ ์ œ๊ฑฐ Branch target expansion ๋ถ„๊ธฐ ๋Œ€์ƒ์ด ๋˜๋Š” basic block์„ ํ•ฉ์นจ Unreachable code elimination Entry์—์„œ ๋„๋‹ฌํ•  ์ˆ˜ ์—†๋Š” ‘unreachable’ block ์ œ๊ฑฐ Loop Optimization Loop๋Š” ํ•œ๋ฒˆ optimizeํ•˜๋ฉด ํšจ๊ณผ๊ฐ€ ํฌ๋‹ค Loop unrolling : ๋ฐ˜๋ณต๋ฌธ์„ ํ’€์–ด์„œ ๋ฐ˜๋ณต ํšŸ์ˆ˜๋ฅผ ์ค„์ž„ Loop invarient : ๋งค๋ฒˆ ๋™์ผํ•œ ๊ฐ’์„ ๋‚ด๋Š” ๋ฌธ์žฅ์„ ๋ฐ˜๋ณต๋ฌธ ๋ฐ–์œผ๋กœ ๋นผ๋ƒ„ Count up to zero : i๋ฅผ ๊ฐ์†Œํ•˜๋Š” ๋ฐ˜๋ณต๋ฌธ์œผ๋กœ ๋ณ€๊ฒฝ (i๋ฅผ 0๊ณผ ๋น„๊ตํ•˜๋Š” ๊ฒƒ์ด n๊ณผ ๋น„๊ตํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋น ๋ฆ„) Dataflow Analysis + Optimization Dataflow Analysis ํ”„๋กœ๊ทธ๋žจ ๋‚ด์— ๊ฐ data ๊ฐ’๋“ค์ด ์ƒ์„ฑ/์†Œ๋ฉธ๋˜๋Š” ์ •๋ณด๋ฅผ ๋ชจ์œผ๋Š” ๊ฒƒ Reaching Definition Analysis definition : ํ•ด๋‹น ๋ณ€์ˆ˜๊ฐ€ assign๋˜๋Š” ๊ฒƒ reach : definition d๊ฐ€ ํŠน์ • ์œ„์น˜ p์— ๋„๋‹ฌํ•œ๋‹ค kill : definition d์˜ ๋‘๊ฐœ์˜ ํฌ์ธํŠธ์‚ฌ์ด์—์„œ ๋‹ค๋ฅธ definition์ด ์กด์žฌํ•œ๋‹ค GEN/KILL GEN: ๋ธ”๋ก ๋‚ด์—์„œ ์ƒ์„ฑ๋œ definition KILL: ๋ธ”๋ก ๋‚ด์—์„œ ์†Œ๋ฉธ๋œ definition IN/OUT IN : ์ด์ „ ๋ธ”๋ก์˜ OUT์˜ ํ•ฉ์ง‘ํ•ฉ OUT : IN์—์„œ GEN์„ ๋”ํ•˜๊ณ  KILL์„ ๋บ€ ๊ฒƒ
new Nginx์—์„œ HTTPS ์„ค์ •ํ•˜๊ธฐ
๐Ÿ”จ ๊ฐœ๋ฐœ ๋„๊ตฌ
๋ฐฐ๊ฒฝ ํ…Œ์ปค ๋ถ€ํŠธ์บ ํ”„๋ฅผ ์ง„ํ–‰์ค‘์ด๋‹ค. ๋ชจ๋“  ํ”„๋กœ๊ทธ๋žจ์€ docker-compose๋กœ ๊ตฌ์„ฑ๋˜์–ด ์žˆ๋‹ค. AWS EC2์— ๊ตฌ๋™ ์ค‘์ธ ์„œ๋ฒ„์— HTTPS๋ฅผ ์ ์šฉํ•˜๋ ค๊ณ  ํ•œ๋‹ค. ๋„๋ฉ”์ธ ๊ตฌ๋งค ์—†์ด ์‹œ๋„๋ฅผ ํ–ˆ์œผ๋‚˜, AWS์—์„œ ์ œ๊ณตํ•˜๋Š” ๋„๋ฉ”์ธ์œผ๋กœ SSL ์ธ์ฆ์„œ๋ฅผ ๋ฐœ๊ธ‰๋ฐ›์„ ์ˆ˜ ์—†์—ˆ๋‹ค. ๋”ฐ๋ผ์„œ, ๋„๋ฉ”์ธ์„ ๊ตฌ๋งคํ•˜๊ณ , Route 53์„ ํ†ตํ•ด ๋„๋ฉ”์ธ์„ ์—ฐ๊ฒฐํ–ˆ๋‹ค. ๋ชฉํ‘œ Nginx๋ฅผ ์ด์šฉํ•˜์—ฌ HTTPS๋ฅผ ์ ์šฉํ•œ๋‹ค. ๋ฐฉ๋ฒ• 1. docker-compose.yml์— certbot ์ปจํ…Œ์ด๋„ˆ๋ฅผ ์ถ”๊ฐ€ํ•œ๋‹ค. 1certbot: 2 image: certbot/certbot 3 container_name: certbot 4 volumes: 5 - ./certbot/conf:/etc/letsencrypt 6 - ./certbot/www:/var/www/certbot 7 depends_on: 8 - nginx 9 10 # certbot์„ ๋ฌดํ•œ๋ฃจํ”„๋กœ ๋Œ๋ฆฌ๊ธฐ ์œ„ํ•ด ์‚ฌ์šฉ 11 entrypoint: "/bin/sh -c 'trap exit TERM; while :; do sleep 6h & wait $${!}; done;'" 2. nginx.conf๋ฅผ ์ˆ˜์ •ํ•œ๋‹ค. # certbot์„ ์‚ฌ์šฉํ•˜๊ธฐ ์œ„ํ•œ ์„ค์ • location /.well-known/acme-challenge/ { allow all; root /var/www/certbot; } 3. certbot ์ปจํ…Œ์ด๋„ˆ๋ฅผ ํ™œ์šฉํ•ด์„œ SSL ์ธ์ฆ์„œ๋ฅผ ๋ฐœ๊ธ‰๋ฐ›๋Š”๋‹ค. 1docker exec -it certbot certbot certonly \ 2 # ์›น ๋ฃจํŠธ ๋ฐฉ์‹์œผ๋กœ ์ธ์ฆ์„œ๋ฅผ ์ƒ์„ฑ 3 --webroot \ 4 # ์›น ์„œ๋ฒ„์˜ ์›น ๋ฃจํŠธ ๋””๋ ‰ํ„ฐ๋ฆฌ ๊ฒฝ๋กœ๋ฅผ ์ง€์ • 5 --webroot-path=/var/www/certbot \ 6 # ์ธ์ฆ์„œ ๊ฐฑ์‹  ๋ฐ ์ค‘์š”ํ•œ ์•Œ๋ฆผ์„ ๋ฐ›์„ ์ด๋ฉ”์ผ ์ฃผ์†Œ๋ฅผ ์ง€์ • 7 --email {์ด๋ฉ”์ผ ์ฃผ์†Œ} \ 8 # Let's Encrypt ์„œ๋น„์Šค ์•ฝ๊ด€์— ๋™์˜ 9 --agree-tos \ 10 # EFF(Electronic Frontier Foundation) ๋‰ด์Šค๋ ˆํ„ฐ๋ฅผ ๋ฐ›์ง€ ์•Š๋„๋ก ์„ค์ • 11 --no-eff-email \ 12 # SSL ์ธ์ฆ์„œ๋ฅผ ์ƒ์„ฑํ•  ๋„๋ฉ”์ธ ์ด๋ฆ„์„ ์ง€์ • 13 -d {๋„๋ฉ”์ธ ์ด๋ฆ„} 4. Nginx ์›น ์„œ๋ฒ„์™€ ํ•จ๊ป˜ ์‚ฌ์šฉํ•  SSL ์„ค์ • ํŒŒ์ผ์„ ๋‹ค์šด๋กœ๋“œ ๋‹ค์šด ๋ฐ›์€ ํ›„ ํŒŒ์ผ์„ ์•Œ๋งž์€ ์œ„์น˜๋กœ ์ด๋™์‹œํ‚จ๋‹ค. ํ•ด๋‹น ํ”„๋กœ์ ํŠธ์—์„œ๋Š” /etc/letsencrypt/๋กœ ์ด๋™์‹œ์ผฐ๋‹ค. 1sudo curl -s https://raw.githubusercontent.com/certbot/certbot/master/certbot-nginx/certbot_nginx/_internal/tls_configs/options-ssl-nginx.conf > "./options-ssl-nginx.conf" 2 3sudo curl -s https://raw.githubusercontent.com/certbot/certbot/master/certbot/certbot/ssl-dhparams.pem > "./ssl-dhparams.pem" 5. nginx.conf๋ฅผ ์ˆ˜์ •ํ•œ๋‹ค. ํ•„์š”ํ•œ ๋ถ€๋ถ„๋งŒ ์ถ”๊ฐ€ํ•˜์˜€๋‹ค. server { listen 80; charset utf-8; server_name {๋„๋ฉ”์ธ ์ด๋ฆ„}; # HTTP ์š”์ฒญ์„ HTTPS๋กœ ๋ฆฌ๋‹ค์ด๋ ‰ํŠธ location / { return 301 https://$host$request_uri; } } server { listen 443 ssl; charset utf-8; server_name { ๋„๋ฉ”์ธ ์ด๋ฆ„ }; # SSL ์ธ์ฆ์„œ ์„ค์ • ssl_certificate /etc/letsencrypt/live/api.forest-of-thoughts.site/fullchain.pem; # SSL ์ธ์ฆ์„œ ํ‚ค ์„ค์ • ssl_certificate_key /etc/letsencrypt/live/api.forest-of-thoughts.site/privkey.pem; # SSL ์„ค์ • ํŒŒ์ผ ํฌํ•จ include /etc/letsencrypt/options-ssl-nginx.conf; # Diffie-Hellman ํ‚ค ์„ค์ • ssl_dhparam /etc/letsencrypt/ssl-dhparams.pem; } 6. nginx ์ปจํ…Œ์ด๋„ˆ ์„ค์ •์„ ์ˆ˜์ •ํ•œ๋‹ค. 1nginx: 2 image: nginx:stable 3 ports: 4 - "80:80" 5 - "443:443" 6 volumes: 7 - ./nginx.conf:/etc/nginx/nginx.conf 8 - ./certbot/conf:/etc/letsencrypt 9 - ./certbot/www:/var/www/certbot ํ•ด ํšŒ๊ณ  ๋ณดํ†ต crontab์„ ํ™œ์šฉํ•ด์„œ ์ž๋™์œผ๋กœ ์ธ์ฆ์„œ ๊ฐฑ์‹ ์„ ๋ฐ›๋Š”๋‹ค. ์ด๋ฒˆ์—๋Š” ํ”„๋กœ์ ํŠธ ๊ธฐ๊ฐ„์ด ๊ธธ์ง€ ์•Š์•„์„œ, ์ˆ˜๋™์œผ๋กœ ์ง„ํ–‰ํ–ˆ๋‹ค. ๋‹ค์Œ์—๋Š” ์ž๋™์œผ๋กœ ์ธ์ฆ์„œ ๊ฐฑ์‹ ์„ ๋ฐ›๋Š” ๊ฒƒ๋„ ๋„์ „ํ•ด๋ณด์ž.
new Issue - yaml ๋ฌธ์ž์—ด ์† colon(์ฝœ๋ก )
๐ŸŽธ ๊ธฐํƒ€
๋ฌธ์ œ์ƒํ™ฉ TIL ๋ธ”๋กœ๊ทธ ์ž๋™ ๋ฐฐํฌ github action ์ฝ”๋“œ์— yaml ํŒŒ์ผ์— ๋‚ด์šฉ์„ ์ถ”๊ฐ€ํ•˜๋Š” ๋ถ€๋ถ„์ด ์žˆ๋‹ค ์ถ”๊ฐ€ํ•˜๋Š” ๋ฌธ์ž์—ด์— ์ฝœ๋ก ์ด ํฌํ•จ๋˜์–ด ์žˆ์–ด์„œ action์—์„œ ์—๋Ÿฌ๋ฅผ ๋„์› ๋‹ค ๋ฌธ์ œ์˜ ์ฝ”๋“œ 1- name: Add google analytics id 2 run: echo -e "\nparams:\n googleAnalytics : \"$GA_TRACKING_ID\"" >> config.yaml ์—๋Ÿฌ ๋ฉ”์‹œ์ง€ ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ์šฐ์—ฌ๊ณก์ ˆ ๋์— ์œ„์™€ ๊ฐ™์ด 2์ค„๋กœ ๋‚˜๋ˆ„์–ด์„œ ํ•ด๊ฒฐํ–ˆ๋‹ค 1 - name: Add google analytics id 2 run: | 3 echo -e "\nparams:" >> config.yaml 4 echo -e " googleAnalytics: \"$GA_TRACKING_ID\"" >> config.yaml
new [๋ชจ๊ฐ์ฝ”24ํ•˜๊ณ„] 01 : ๊ฒฐ๊ณผ
๐Ÿ‘จโ€๐Ÿ’ป ๋ชจ๊ฐ์ฝ”
django์—์„œ swagger ๋ฌธ์„œํ™” ๊ตฌํ˜„ํ•˜๊ธฐ ๊ฐœ์š” ์žฅ๊ณ  ํ”„๋ ˆ์ž„์›Œํฌ๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๊ธฐ๋ณธ์ ์ธ CRUD ๊ธฐ๋Šฅ๊ณผ, REST API๋ฅผ ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์•Œ์•„๋ณด์ž. ํ”„๋กœ์ ํŠธ ๊ตฌ์กฐ 1. 2โ”œโ”€โ”€ db.sqlite3 3โ”œโ”€โ”€ djtest (๋ฉ”์ธ ์•ฑ) 4โ”‚ โ”œโ”€โ”€ __init__.py 5โ”‚ โ”œโ”€โ”€ asgi.py 6โ”‚ โ”œโ”€โ”€ settings.py 7โ”‚ โ”œโ”€โ”€ urls.py 8โ”‚ โ”œโ”€โ”€ views.py 9โ”‚ โ””โ”€โ”€ wsgi.py 10โ”œโ”€โ”€ manage.py 11โ”œโ”€โ”€ paste (์ƒ์„ฑํ•œ ์•ฑ) 12โ”‚ โ”œโ”€โ”€ __init__.py 13โ”‚ โ”œโ”€โ”€ admin.py 14โ”‚ โ”œโ”€โ”€ apps.py 15โ”‚ โ”œโ”€โ”€ migrations 16โ”‚ โ”œโ”€โ”€ models.py 17โ”‚ โ”œโ”€โ”€ serializers.py 18โ”‚ โ”œโ”€โ”€ tests.py 19โ”‚ โ”œโ”€โ”€ urls.py 20โ”‚ โ””โ”€โ”€ views.py 21โ””โ”€โ”€ requirements.txt ์ž์ฃผ ์‚ฌ์šฉํ•˜๋Š” Django ๋ช…๋ น์ž 1# ์ƒˆ๋กœ์šด Django ํ”„๋กœ์ ํŠธ๋ฅผ ์ƒ์„ฑ 2python manage.py startproject 3# ์ƒˆ๋กœ์šด Django ์•ฑ์„ ์ƒ์„ฑ 4python manage.py startapp 5# ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์— ์ ์šฉํ•  ๋งˆ์ด๊ทธ๋ ˆ์ด์…˜ ํŒŒ์ผ์„ ์ƒ์„ฑ 6python manage.py makemigrations 7# ๋งˆ์ด๊ทธ๋ ˆ์ด์…˜ ํŒŒ์ผ์„ ์‹ค์ œ ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค์— ์ ์šฉ 8python manage.py migrate 9# ๊ด€๋ฆฌ์ž(superuser) ๊ณ„์ •์„ ์ƒ์„ฑ 10python manage.py createsuperuser 11# ํ”„๋กœ์ ํŠธ์˜ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค๋ฅผ ์‹คํ–‰ 12python manage.py test 13# ํ…Œ์ŠคํŠธ์šฉ ์„œ๋ฒ„๋ฅผ ํŠน์ • ์„ค์ •์œผ๋กœ ์‹คํ–‰ 14python manage.py testserver CRUD ๊ตฌํ˜„ Paste ๋ชจ๋ธ ์ •์˜ 1from django.db import models 2 3class Paste(models.Model): 4 title = models.CharField(max_length=100) 5 content = models.TextField() 6 # auto_now_add : ๊ฐ์ฒด๊ฐ€ ์ฒ˜์Œ ์ƒ์„ฑ๋  ๋•Œ๋งŒ ํ˜„์žฌ ๋‚ ์งœ์™€ ์‹œ๊ฐ„์„ ์ž๋™์œผ๋กœ ์„ค์ • 7 created_at = models.DateTimeField(auto_now_add=True) 8 # auto_now : ๊ฐ์ฒด๊ฐ€ ์ €์žฅ๋  ๋•Œ๋งˆ๋‹ค ํ˜„์žฌ ๋‚ ์งœ์™€ ์‹œ๊ฐ„์„ ์ž๋™์œผ๋กœ ์„ค์ • 9 updated_at = models.DateTimeField(auto_now=True) 10 class Meta: 11 ordering = ['-created_at'] 12 def __str__(self): 13 return self.title Serializer ์ •์˜ 1from rest_framework import serializers 2from .models import Paste 3 4class PasteSerializer(serializers.ModelSerializer): 5 class Meta: 6 model = Paste 7 fields = '__all__' 8 # ์ง์ ‘ ์ง€์ •ํ•˜๋Š” ๋ฐฉ๋ฒ• 9 # fields = ['title', 'content'] View ๊ตฌํ˜„ PasteView 1class PasteView(APIView): 2 def get(self, _): 3 pastes = Paste.objects.all() 4 serializer = PasteSerializer(pastes, many=True) 5 return Response(serializer.data, status=status.HTTP_200_OK) 6 7 def post(self, request): 8 serializer = PasteSerializer(data=request.data) 9 if serializer.is_valid(): 10 serializer.save(user=request.user) 11 return Response(serializer.data, status=status.HTTP_201_CREATED) 12 return Response(serializer.errors, status=status.HTTP_400_BAD_REQUEST) PasteDetailView 1class PasteDetailView(APIView): 2 def get(self, _, pk): 3 try: 4 paste = Paste.objects.get(pk=pk) 5 serializer = PasteSerializer(paste) 6 return Response(serializer.data, status=status.HTTP_200_OK) 7 except Paste.DoesNotExist: 8 return Response(status=status.HTTP_404_NOT_FOUND) 9 10 def put(self, request, pk): 11 try: 12 paste = Paste.objects.get(pk=pk) 13 except Paste.DoesNotExist: 14 return Response(status=status.HTTP_404_NOT_FOUND) 15 16 if paste.user != request.user: 17 return Response(status=status.HTTP_403_FORBIDDEN) 18 19 serializer = PasteSerializer(paste, data=request.data) 20 if serializer.is_valid(): 21 serializer.save() 22 return Response(serializer.data, status=status.HTTP_200_OK) 23 return Response(serializer.errors, status=status.HTTP_400_BAD_REQUEST) 24 25 def delete(self, request, pk): 26 try: 27 paste = Paste.objects.get(pk=pk) 28 except Paste.DoesNotExist: 29 return Response(status=status.HTTP_404_NOT_FOUND) 30 31 paste.delete() 32 return Response(status=status.HTTP_204_NO_CONTENT) urls.py 1from django.urls import path 2from paste.views import * 3 4urlpatterns = [ 5 path('', PasteView.as_view(), name='paste_list_create'), 6 path('<int:pk>', PasteDetailView.as_view(), name='paste_get_update_delete'), 7] Swagger ์ ์šฉ PasteView PasteView 1class PasteView(APIView): 2 @swagger_auto_schema( 3 operation_description="Get list of pastes", 4 operation_summary="Get list of pastes", 5 responses={200: PasteSerializer(many=True)}, 6 ) 7 def get(self, _): 8 ... 9 10 @swagger_auto_schema( 11 operation_description="Create a new paste", 12 operation_summary="Create a new paste", 13 request_body=PasteSerializer, 14 responses={201: PasteSerializer, 400: "Bad Request"}, 15 ) 16 def post(self, request): 17 ... PasteDetailView 1class PasteDetailView(APIView): 2 @swagger_auto_schema( 3 operation_description="Get a paste by ID", 4 operation_summary="Get a paste by ID", 5 responses={200: PasteSerializer, 404: "Not Found"}, 6 ) 7 def get(self, _, pk): 8 ... 9 10 @swagger_auto_schema( 11 operation_description="Update a paste by ID", 12 operation_summary="Update a paste by ID", 13 request_body=PasteSerializer, 14 responses={ 15 200: PasteSerializer, 16 400: "Bad Request", 17 403: "Forbidden", 18 404: "Not Found", 19 }, 20 ) 21 def put(self, request, pk): 22 ... 23 24 @swagger_auto_schema( 25 operation_description="Delete a paste by ID", 26 operation_summary="Delete a paste by ID", 27 responses={204: "No Content", 404: "Not Found"}, 28 ) 29 def delete(self, request, pk): 30 ... swagger ์ ์šฉ ๊ฒฐ๊ณผ django์—์„œ JWT ์ธ์ฆ ๊ตฌํ˜„ํ•˜๊ธฐ ์žฅ๊ณ ์—์„œ๋Š” djangorestframework-simplejwt ํŒจํ‚ค์ง€๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ JWT ์ธ์ฆ์„ ๊ตฌํ˜„ํ•  ์ˆ˜ ์žˆ๋‹ค. requirements 1pip install djangorestframework-simplejwt settings.py 1INSTALLED_APPS = [ 2 ... 3 'rest_framework', 4 'rest_framework_simplejwt', 5] 1REST_FRAMEWORK = { 2 # ๊ธฐ๋ณธ ์ธ์ฆ ํด๋ž˜์Šค๋ฅผ ์„ค์ • 3 'DEFAULT_AUTHENTICATION_CLASSES': ( 4 'rest_framework_simplejwt.authentication.JWTAuthentication', 5 ), 6 # ๊ธฐ๋ณธ ์Šคํ‚ค๋งˆ ํด๋ž˜์Šค๋ฅผ ์„ค์ •, CoreAPI๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ์ž๋™์œผ๋กœ API ๋ฌธ์„œํ™”๋ฅผ ์ƒ์„ฑ 7 'DEFAULT_SCHEMA_CLASS': 'rest_framework.schemas.coreapi.AutoSchema', 8 # ๊ธฐ๋ณธ ๊ถŒํ•œ ํด๋ž˜์Šค๋ฅผ ์„ค์ •, AllowAny๋ฅผ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ์š”์ฒญ์„ ํ—ˆ์šฉ 9 'DEFAULT_PERMISSION_CLASSES': ( 10 'rest_framework.permissions.AllowAny', 11 ), 12} 1from datetime import timedelta 2 3SIMPLE_JWT = { 4 # ์•ก์„ธ์Šค ํ† ํฐ์˜ ์œ ํšจ ๊ธฐ๊ฐ„์„ ์„ค์ • 5 'ACCESS_TOKEN_LIFETIME': timedelta(minutes=30), 6 # ๋ฆฌํ”„๋ ˆ์‹œ ํ† ํฐ์˜ ์œ ํšจ ๊ธฐ๊ฐ„์„ ์„ค์ • 7 'REFRESH_TOKEN_LIFETIME': timedelta(days=1), 8 # ๋ฆฌํ”„๋ ˆ์‹œ ํ† ํฐ์ด ๊ฐฑ์‹ ๋  ๋•Œ๋งˆ๋‹ค ์ƒˆ๋กœ์šด ๋ฆฌํ”„๋ ˆ์‹œ ํ† ํฐ์„ ๋ฐœ๊ธ‰ํ• ์ง€ ์—ฌ๋ถ€๋ฅผ ์„ค์ • 9 'ROTATE_REFRESH_TOKENS': False, 10 # ๋ฆฌํ”„๋ ˆ์‹œ ํ† ํฐ์ด ๊ฐฑ์‹ ๋œ ํ›„ ์ด์ „ ํ† ํฐ์„ ๋ธ”๋ž™๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€ํ• ์ง€ ์—ฌ๋ถ€๋ฅผ ์„ค์ • 11 'BLACKLIST_AFTER_ROTATION': True, 12 13 # JWT ํ† ํฐ์˜ ์•”ํ˜ธํ™” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ์„ค์ • 14 'ALGORITHM': 'HS256', 15 # JWT ํ† ํฐ์„ ์„œ๋ช…ํ•  ๋•Œ ์‚ฌ์šฉํ•  ํ‚ค๋ฅผ ์„ค์ • 16 'SIGNING_KEY': SECRET_KEY, 17 # ํ† ํฐ ๊ฒ€์ฆ์— ์‚ฌ์šฉํ•  ๊ณต๊ฐœ ํ‚ค๋ฅผ ์„ค์ • 18 'VERIFYING_KEY': None, 19 # ํ† ํฐ์˜ ๋Œ€์ƒ์ž(aud) ํด๋ ˆ์ž„์„ ์„ค์ • 20 'AUDIENCE': None, 21 # ํ† ํฐ์˜ ๋ฐœ๊ธ‰์ž(iss) ํด๋ ˆ์ž„์„ ์„ค์ • 22 'ISSUER': None, 23 24 # ์ธ์ฆ ํ—ค๋” ํƒ€์ž…์„ ์„ค์ • 25 'AUTH_HEADER_TYPES': ('Bearer',), 26 # ์ธ์ฆ ํ—ค๋”์˜ ์ด๋ฆ„์„ ์„ค์ • 27 'AUTH_HEADER_NAME': 'HTTP_AUTHORIZATION', 28 # ์‚ฌ์šฉ์ž ๋ชจ๋ธ์—์„œ ์‚ฌ์šฉ์ž ID ํ•„๋“œ๋ฅผ ์„ค์ • 29 'USER_ID_FIELD': 'id', 30 # JWT ํ† ํฐ์—์„œ ์‚ฌ์šฉ์ž ID๋ฅผ ์ €์žฅํ•  ํด๋ ˆ์ž„์„ ์„ค์ • 31 'USER_ID_CLAIM': 'user_id', 32 33 # ์ธ์ฆ์— ์‚ฌ์šฉํ•  ํ† ํฐ ํด๋ž˜์Šค๋“ค์„ ์„ค์ • 34 'AUTH_TOKEN_CLASSES': ('rest_framework_simplejwt.tokens.AccessToken',), 35 # ํ† ํฐ์˜ ์œ ํ˜•์„ ์ €์žฅํ•  ํด๋ ˆ์ž„์„ ์„ค์ • 36 'TOKEN_TYPE_CLAIM': 'token_type', 37} urls.py 1from django.urls import path 2from rest_framework_simplejwt.views import TokenObtainPairView, TokenRefreshView 3from rest_framework_simplejwt.authentication import JWTAuthentication 4 5urlpatterns = [ 6 # JWT ํ† ํฐ์„ ๋ฐœ๊ธ‰ํ•˜๋Š” ๋ทฐ 7 path("token/", TokenObtainPairView.as_view(), name="token_obtain_pair"), 8 # JWT ํ† ํฐ์„ ๊ฐฑ์‹ ํ•˜๋Š” ๋ทฐ 9 path("token/refresh/", TokenRefreshView.as_view(), name="token_refresh"), 10] views.py 1from rest_framework import permissions 2from rest_framework_simplejwt.authentication import JWTAuthentication 3from drf_yasg.utils import swagger_auto_schema 4 5 6class PasteView(APIView): 7 8 def get(self, request): 9 ... 10 11 def post(self, request): 12 ... 13 14 def get_permissions(self): 15 # SAFE_METHODS : GET, HEAD, OPTIONS 16 if self.request.method in permissions.SAFE_METHODS: 17 self.permission_classes = [permissions.AllowAny] 18 else: 19 self.authentication_classes = [JWTAuthentication] 20 self.permission_classes = [permissions.IsAuthenticated] 21 return super().get_permissions() 22 23 24class PasteDetailView(APIView): 25 26 def get(self, request, pk): 27 ... 28 29 def put(self, request, pk): 30 ... 31 32 def delete(self, request, pk): 33 ... 34 35 def get_permissions(self): 36 # SAFE_METHODS : GET, HEAD, OPTIONS 37 if self.request.method in permissions.SAFE_METHODS: 38 self.permission_classes = [permissions.AllowAny] 39 else: 40 self.authentication_classes = [JWTAuthentication] 41 self.permission_classes = [permissions.IsAuthenticated] 42 return super().get_permissions() ๊ฒฐ๊ณผ TokenObtainPairView๋ฅผ ํ†ตํ•ด access token๊ณผ refresh token์„ ๋ฐœ๊ธ‰๋ฐ›์„ ์ˆ˜ ์žˆ๋‹ค. TokenRefreshView๋ฅผ ํ†ตํ•ด refresh token์„ ์‚ฌ์šฉํ•˜์—ฌ access token์„ ๊ฐฑ์‹ ํ•  ์ˆ˜ ์žˆ๋‹ค. access token๊ณผ refresh token์€ settings.py์—์„œ ์„ค์ •ํ•œ ์œ ํšจ ๊ธฐ๊ฐ„์— ๋”ฐ๋ผ ๋งŒ๋ฃŒ๋œ๋‹ค. Blacklist ์ ์šฉ settings.py 1INSTALLED_APPS = [ 2 ... 3 'rest_framework_simplejwt.token_blacklist', 4] 1SIMPLE_JWT = { 2 ... 3 # ๋ธ”๋ž™๋ฆฌ์ŠคํŠธ์— ํ† ํฐ์„ ์ถ”๊ฐ€ํ•  ๋•Œ ์‚ฌ์šฉํ•  ๋ชจ๋ธ์„ ์„ค์ • 4 'BLACKLIST_AFTER_ROTATION': True, 5} ๊ฒฐ๊ณผ TokenRefreshView๋ฅผ ํ†ตํ•ด ํ† ํฐ์ด ์žฌ๋ฐœ๊ธ‰๋  ๋•Œ, ์ด์ „ refresh token์„ ๋ธ”๋ž™๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€ํ•œ๋‹ค.
new Fastapi - ํ†ตํ•ฉํ…Œ์ŠคํŠธ In-Memory DB์—์„œ ํ…Œ์ด๋ธ”์ด ์—†๋‹ค๋Š” ๋ฌธ์ œ
๐Ÿ Python
์ƒํ™ฉ ํ…Œ์ปค ๋ถ€ํŠธ์บ ํ”„์—์„œ ํŒ€ํ”„๋กœ์ ํŠธ๋ฅผ ์ง„ํ–‰ ์ค‘์ด๋‹ค. ๋‹จ์œ„ํ…Œ์ŠคํŠธ ์ฝ”๋“œ๋Š” ์ž‘์„ฑ์ด ์™„๋ฃŒ๋˜์—ˆ๊ณ , ํ†ตํ•ฉํ…Œ์ŠคํŠธ ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑ ์ค‘์ด๋‹ค. sqlite in-memory db๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ…Œ์ŠคํŠธ ์ค‘์ธ๋ฐ, ํ…Œ์ด๋ธ”์ด ์—†๋‹ค๋Š” ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค. ํ…Œ์ŠคํŠธ ์ „์— ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ•˜๋Š” ์ฝ”๋“œ๊ฐ€ ์‹คํ–‰๋จ์—๋„ ๋ถˆ๊ตฌํ•˜๊ณ , ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค. ์ธ๋ฉ”๋ชจ๋ฆฌ๊ฐ€ ์•„๋‹Œ ํŒŒ์ผ๋กœ ์ €์žฅํ•˜๋Š” ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋ฉด ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š๋Š” ๊ฒƒ์„ ๋ณด๊ณ  ๋ฌธ์ œ์˜ ์›์ธ์„ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ์ฝ”๋“œ 1from database import Base, engine 2from fastapi.testclient import TestClient 3 4from main import app 5from models import * 6 7# ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ•˜๋Š” ์ฝ”๋“œ์ด๋‹ค 8Base.metadata.create_all(bind=engine) 9 10client = TestClient(app) 11 12 13class TestUserApi: 14 15 def test_create_user(self): 16 test_nickname = "test_nickname" 17 # ์•„๋ž˜ ์š”์ฒญ์„ ์ฒ˜๋ฆฌํ•˜๋Š” ์ฝ”๋“œ์—์„œ ์˜ค๋ฅ˜๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค 18 response = client.post( 19 "/api/users", 20 json={"nickname": test_nickname}, 21 ) 22 assert response.status_code == 200 23 assert response.json()["nickname"] == test_nickname ์›์ธ ํ…Œ์ด๋ธ”์„ ์ƒ์„ฑํ• ๋•Œ ๋งŒ๋“ค์–ด์ง€๋Š” ์„ธ์…˜๊ณผ TestClient๊ฐ€ ์š”์ฒญ์„ ์ฒ˜๋ฆฌํ•  ๋•Œ ์‚ฌ์šฉํ•˜๋Š” ์„ธ์…˜์ด ๋‹ค๋ฅด๋‹ค. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• TestClient๋‚ด์— get_db() ํ•จ์ˆ˜๋ฅผ ์ž„์˜๋กœ ์ฃผ์ž…ํ•œ๋‹ค ๋ฐ์ดํ„ฐ๋ฒ ์ด์Šค๋ฅผ ์—ฐ๊ฒฐํ• ๋•Œ, ๋‹จ์ผ ์„ธ์…˜์„ ์‚ฌ์šฉํ•˜๋„๋ก ํ•œ๋‹ค. 1from database import Base, engine, get_db 2from sqlalchemy.orm import sessionmaker 3from fastapi.testclient import TestClient 4 5from main import app 6from models import * 7 8Base.metadata.create_all(bind=engine) 9 10client = TestClient(app) 11 12# ํ…Œ์ŠคํŠธ์—์„œ ์‚ฌ์šฉํ•  ์„ธ์…˜์„ ์ƒ์„ฑํ•œ๋‹ค 13TestingSessionLocal = sessionmaker(autocommit=False, autoflush=False, bind=engine) 14 15 16Base.metadata.create_all(bind=engine) 17 18# get_db() ํ•จ์ˆ˜๋ฅผ ์žฌ์ •์˜ํ•œ๋‹ค 19def override_get_db(): 20 try: 21 db = TestingSessionLocal() 22 yield db 23 finally: 24 db.close() 25 26# get_db() ํ•จ์ˆ˜๋ฅผ ์žฌ์ •์˜ํ•œ ํ•จ์ˆ˜๋ฅผ ์ฃผ์ž…ํ•œ๋‹ค 27app.dependency_overrides[get_db] = override_get_db 28 29 30class TestUserApi: 31 32 def test_create_user(self): 33 test_nickname = "test_nickname" 34 response = client.post( 35 "/api/users", 36 json={"nickname": test_nickname}, 37 ) 38 assert response.status_code == 201 39 assert response.json()["nickname"] == test_nickname 1engine = create_engine( 2 os.getenv("DATABASE_URL"), 3 # sqlite๋ฅผ ์‚ฌ์šฉํ•  ๋•Œ, ์—ฌ๋Ÿฌ ์Šค๋ ˆ๋“œ์—์„œ ์—ฐ๊ฒฐ์ด ๊ฐ€๋Šฅํ•˜๋„๋ก ์„ค์ •ํ•œ๋‹ค 4 connect_args={"check_same_thread": False}, 5 # ๋‹จ์ผ ์„ธ์…˜์„ ์‚ฌ์šฉํ•˜๋„๋ก ์„ค์ •ํ•œ๋‹ค 6 poolclass=StaticPool, 7)
new Issue - fastapi์—์„œ websocket 404 ๋ฌธ์ œ
๐Ÿ Python
๋ฐฐ๊ฒฝ ํ…Œ์ปค ๋ถ€ํŠธ์บ ํ”„ ์ตœ์ข…๋ฐœํ‘œ ์ „๋‚ ์ด๋‹ค. gpt ํ”„๋กฌํ”„ํŠธ ๋ถ€๋ถ„ ์ˆ˜์ •์„ main ๋ธŒ๋žœ์น˜์— ๋ฐ˜์˜ํ•˜๊ณ , EC2 ์„œ๋ฒ„์— ๋ฐฐํฌํ–ˆ๋‹ค. ๋ฌธ์ œ ๋ฐฐํฌํ•œ ์„œ๋ฒ„์—์„œ websocket ์—ฐ๊ฒฐ์ด 404 ์—๋Ÿฌ๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค. (๋‚ด์ผ์ด ์ตœ์ข… ๋ฐœํ‘œ์ธ๋ฐ,,,) ๋‹ค๋ฅธ http ์š”์ฒญ์€ ์ •์ƒ์ ์œผ๋กœ ์ฒ˜๋ฆฌ๋˜์ง€๋งŒ ์›น์†Œ์ผ“๋งŒ ์ฒ˜๋ฆฌ๋˜์ง€ ์•Š๋Š” ๊ฒƒ์„ ํ™•์ธํ–ˆ๋‹ค. nginx์˜ log 1{IP์ฃผ์†Œ} - - [02/Aug/2024:10:59:04 +0000] "GET /ws/chatrooms/294?user_id=296 HTTP/1.1" 404 22 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.5 Safari/605.1.15" 2{IP์ฃผ์†Œ} - - [02/Aug/2024:10:59:05 +0000] "GET /ws/chatrooms/294?user_id=296 HTTP/1.1" 404 22 "-" "Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/605.1.15 (KHTML, like Gecko) Version/17.5 Safari/605.1.15" ์‚ฌ๊ณ ํ๋ฆ„ nginx ์„ค์ • ๋ฌธ์ œ์ธ๊ฐ€? X nginx ์„ค์ •์€ ๋ณ€๊ฒฝ๋˜์ง€ ์•Š์•˜๋‹ค. ๋ฐฐํฌํ™˜๊ฒฝ์˜ ๋ฌธ์ œ์ธ๊ฐ€? X ๋กœ์ปฌ์—์„œ ์‹คํ–‰ํ•œ ์„œ๋ฒ„์—์„œ๋„ ๋™์ผํ•œ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•˜์˜€๋‹ค. ์ด๋ฒˆ ๋ฐฐํฌ์—์„œ ๋ณ€๊ฒฝ๋œ ์†Œ์Šค์ฝ”๋“œ๊ฐ€ ๋ฌธ์ œ์ธ๊ฐ€? X ์œก์•ˆ์œผ๋กœ ํ™•์ธํ–ˆ์„ ๋•Œ๋Š”, ๋ณ€๊ฒฝ๋œ ๋ถ€๋ถ„์ด ์›น์†Œ์ผ“๊ณผ ๊ด€๋ จ์ด ์—†๋‹ค. ๋กœ์ปฌ์—์„œ ์ด์ „ ๋ฒ„์ „์œผ๋กœ reset ํ›„ ์‹œ๋„ ํ•ด๋ณด์•˜์ง€๋งŒ ๋ฌธ์ œ๊ฐ€ ํ•ด๊ฒฐ๋˜์ง€ ์•Š์•˜๋‹ค. Docker image ๋ฌธ์ œ์ธ๊ฐ€? X ๋ฐฑ์—”๋“œ ์„œ๋ฒ„๋Š” python:slim ์ด๋ฏธ์ง€๋ฅผ ์‚ฌ์šฉํ•˜๊ณ  ์žˆ์œผ๋ฉฐ, ํ•ด๋‹น ์ด๋ฏธ์ง€๊ฐ€ ๋ณ€๊ฒฝ๋˜์–ด์„œ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•  ๊ฐ€๋Šฅ์„ฑ์ด ์žˆ๋‹ค๊ณ  ์ƒ๊ฐํ–ˆ๋‹ค. ๋กœ์ปฌ์—์„œ docker image๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ์•Š๊ณ  ์‹คํ–‰ํ•ด๋ณด์•˜์ง€๋งŒ ๋ฌธ์ œ๊ฐ€ ํ•ด๊ฒฐ๋˜์ง€ ์•Š์•˜๋‹ค. ์ด๋•Œ, ๋กœ๊ทธ์—์„œ warning ๋ฉ”์‹œ์ง€๋ฅผ ํ™•์ธํ–ˆ๋‹ค. WARNING: No supported WebSocket library detected. Please use "pip install 'uvicorn[standard]'", or install 'websockets' or 'wsproto' manually. ์›์ธ ๋ชจ์ข…์˜ ์ด์œ ๋กœ, ์ด์ „์— ๊ฐœ๋ฐœ/๋ฐฐํฌํ• ๋•Œ์—๋Š” ์กด์žฌํ–ˆ๋˜ ์›น์†Œ์ผ“ ๊ด€๋ จ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์‚ฌ๋ผ์ง„ ๊ฒƒ์ด๋‹ค. ์˜ค๋ฅ˜๋ฅผ ํ•ด๊ฒฐํ•˜๊ณ  ์กฐ์‚ฌํ•ด๋ณธ ๊ฒฐ๊ณผ fastapi ๋ ˆํฌ์ง€ํ† ๋ฆฌ์— 6์‹œ๊ฐ„ ์ „ merge๋œ PR์„ ํ™•์ธํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. (https://github.com/fastapi/fastapi/pull/11935) ํ•ด๋‹น PR์—์„œ๋Š” pip install fastapi[standard] ๋ฅผ ํ†ตํ•ด ํ‘œ์ค€ ์ข…์† ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์„ค์น˜ํ•˜๋Š” ๊ธฐ๋Šฅ์ด ์ถ”๊ฐ€๋˜์—ˆ๋‹ค. ์ด๋กœ ์ธํ•ด, uvicorn[standard] ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์„ค์น˜ํ•˜์ง€ ์•Š์•˜์„ ๋•Œ, ์›น์†Œ์ผ“ ๊ด€๋ จ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์„ค์น˜๋˜์ง€ ์•Š์•„ ๋ฐœ์ƒํ•œ ๋ฌธ์ œ์˜€๋‹ค. ํ•ด๊ฒฐ requirements.txt์— websockets๋ฅผ ์ถ”๊ฐ€ํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค. ๋ฐฐ์šด ์  ์ค‘์š”ํ•œ ํ”„๋กœ์ ํŠธ๋ฅผ ํ•  ๋•Œ requirements.txt์— ํ•ญ์ƒ ๊ฐ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ์— ๋ฒ„์ „์„ ๋ช…์‹œํ•ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค. ์ด๋ฒˆ์—๋„ ๋ฒ„์ „์„ ๋ช…์‹œํ–ˆ๋‹ค๋ฉด, ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๊ฐ€ ์—…๋ฐ์ดํŠธ ๋˜๋”๋ผ๋„ ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒํ•˜์ง€ ์•Š์•˜์„ ๊ฒƒ์ด๋‹ค. ๋˜ํ•œ, ๋กœ๊ทธ๋ฅผ ์ž˜ ํ™•์ธํ•˜๊ณ , warning ๋ฉ”์‹œ์ง€๋ฅผ ๋†“์น˜์ง€ ์•Š๋„๋ก ์ฃผ์˜ํ•ด์•ผ๊ฒ ๋‹ค.
new Spring ๊ฐœ๋… - DI (Dependency Injection)
๐Ÿƒ Spring
์˜์กด ์ฃผ์ž… (DI : Dependency Injection)์„ ํ•˜๋Š” ๋ฐฉ๋ฒ• Assembler๋ผ๋Š” ๋ณ„๋„์˜ ํด๋ž˜์Šค ์ƒ์„ฑ 1public class Assembler { 2 private MemberDao memberDao; 3 private MemberRegisterService regSvc; 4 5 public Assembler() { 6 memberDao = new MemberDao(); 7 regSvc = new MemberRegisterService(memberDao); 8 } 9 10 public MemberDao getMemberDao() { 11 return memberDao; 12 } 13 14 public MemberRegisterService getMemberRegisterService() { 15 return regSvc; 16 } 17} Spring์—์„œ ์ง€์›ํ•˜๋Š” DI ์‚ฌ์šฉ 1@Configuration 2public class AppCtx { 3 @Bean 4 public MemberDao memberDao() { 5 return new MemberDao(); 6 } 7 @Bean 8 public MemberRegisterService memberRegSvc() { 9 return new MemberRegisterService(memberDao()); 10 } 11} DI ๋ฐฉ์‹ Constructor ๋ฐฉ์‹ 1@Bean 2 public MemberListPrinter listPrinter() { 3 return new MemberListPrinter(memberDao(), memberPrinter()); 4 } Setter method ๋ฐฉ์‹ 1@Bean 2public MemberInfoPrinter infoPrinter() { 3 MemberInfoPrinter infoPrinter = new MemberInfoPrinter(); 4 infoPrinter.setMemberDao(memberDao()); 5 infoPrinter.setPrinter(memberPrinter()); 6 return infoPrinter; 7} constructor ๋ฐฉ์‹์ด ํ›จ์”ฌ ๊น”๋”ํ•ด๋ณด์ธ๋‹ค. java bean์—์„œ๋Š” getter์™€ setter๋ฅผ ์ด์šฉํ•ด์„œ property๋ฅผ ์ •์˜ํ•œ๋‹ค๊ณ  ํ•œ๋‹ค. ๋‘ ๊ฐœ ์ด์ƒ์˜ Configuration ํŒŒ์ผ ์‚ฌ์šฉ : @Autowired ํ™œ์šฉ AppConf1.java 1@Configuration 2public class AppConf1 { 3 ... 4} AppConf2.java 1import org.springframework.beans.factory.annotation.Autowired; 2 3@Configuration 4public class AppConf2 { 5 @Autowired 6 private MemberDao memberDao; 7 @Autowired 8 private MemberPrinter memberPrinter; 9 10 ... 11} MainForSpring.java 1ctx = new AnnotationConfigApplicationContext(AppConf1.class, AppConf2.class); Autowired annotation์„ ํ†ตํ•ด ๋‹ค๋ฅธ ์„ค์ • ํŒŒ์ผ์˜ ๊ฐ์ฒด๋ฅผ ๊ฐ€์ ธ์˜ฌ ์ˆ˜ ์žˆ๋‹ค. ๋‘ ๊ฐœ ์ด์ƒ์˜ Configuration ํŒŒ์ผ ์‚ฌ์šฉ : @Import ํ™œ์šฉ AppConfImport.java 1import org.springframework.context.annotation.Import; 2 3@Configuration 4@Import(AppConf2.class) 5public class AppConfImport { MainForSpring.java 1ctx = new AnnotationConfigApplicationContext(AppConfImport.class); 2// ํด๋ž˜์Šค ํ•œ ๊ฐœ๋งŒ ๋ช…์‹œํ•ด์ค˜๋„ ๊ฐ€๋Šฅ ํƒ€์ž…๋งŒ์œผ๋กœ ๋นˆ์„ ๊ตฌํ•  ์ˆ˜ ์žˆ๋‹ค 1VersionPrinter versionPrinter = ctx.getBean(MemberPrinter.class); ๋‹ค๋งŒ, ๊ฐ™์€ ํƒ€์ž…์˜ ๋นˆ ๊ฐ์ฒด๊ฐ€ 2๊ฐœ ์ด์ƒ ์กด์žฌํ•œ๋‹ค๋ฉด ์—๋Ÿฌ ๋ฐœ์ƒ
new Spring ๊ฐœ๋… - Testing
๐Ÿƒ Spring
Unit Test (๋‹จ์œ„ ํ…Œ์ŠคํŠธ) ๊ฐ€์žฅ ์ž‘์€ ๋‹จ์œ„ (ํด๋ž˜์Šค ๋˜๋Š” ๋ฉ”์†Œ๋“œ)๋ฅผ ๊ณ ๋ฆฝ์‹œ์ผœ์„œ ํ…Œ์ŠคํŠธํ•˜๋Š” ๋ฐฉ์‹ ๊ด€๋ จ ์šฉ์–ด SUT (Sytem Under Test) ํ…Œ์ŠคํŠธํ•˜๊ณ ์žํ•˜๋Š” ์ฃผ์š” ๋Œ€์ƒ์ด ๋˜๋Š” Unit DOC (Depended On Component) SUT๊ฐ€ ์˜์กดํ•˜๋Š” ๊ฐ์ฒด Test double DOC๋ฅผ ๋Œ€์‹ ํ•ด ์ค„ ์ˆ˜ ์žˆ๋Š” ๊ฐ์ฒด Test double์˜ ์ข…๋ฅ˜ : Mock, Stub Mock ํ–‰์œ„ ๊ฒ€์ฆ (๊ฐ์ฒด๊ฐ€ ํŠน์ • ๋™์ž‘์„ ์ˆ˜ํ–‰ํ•˜๋Š”์ง€ ๊ฒ€์ฆ) ์‚ฌ์šฉ test framework : Mockito, JMock, EasyMock Stub ์ƒํƒœ ๊ฒ€์ฆ (๊ฐ์ฒด์˜ ์ƒํƒœ๋ฅผ ํ™•์ธํ•˜์—ฌ ๊ฒ€์ •) ์‚ฌ์šฉ Integration Test (ํ†ตํ•ฉ ํ…Œ์ŠคํŠธ) ์—ฌ๋Ÿฌ ๊ฐœ์˜ Unit์„ ํ†ตํ•ฉํ•ด์„œ ํ…Œ์ŠคํŠธํ•˜๋Š” ๋ฐฉ์‹ JUnit ๋งค ๋‹จ์œ„ ํ…Œ์ŠคํŠธ๋งˆ๋‹ค ํ…Œ์ŠคํŠธ ํด๋ž˜์Šค๊ฐ€ ์ƒ์„ฑ -> ๋…๋ฆฝ์ ์ธ ํ…Œ์ŠคํŠธ ๊ฐ€๋Šฅ Annotation ์ œ๊ณต -> ํ…Œ์ŠคํŠธ life cycle ๊ด€๋ฆฌ assert ๋ฉ”์†Œ๋“œ ์ œ๊ณต -> ํ…Œ์ŠคํŠธ ๊ฒฐ๊ณผ ํŒ๋ณ„ JUnit5 = JUnit Platform + JUnit Jupiter + JUnit Vintage JUnit Platform : JVM ๊ธฐ๋ฐ˜ ํ…Œ์ŠคํŒ… ํ”„๋ ˆ์ž„์›Œํฌ๋ฅผ ์‹คํ–‰์‹œํ‚ค๊ธฐ ์œ„ํ•œ ๊ธฐ๋ฐ˜ ๋ชจ๋“ˆ JUnit Jupiter : JUnit5๋ฅผ ์œ„ํ•œ Test Engine API ์ œ๊ณต JUnit Vintage : JUnit3, JUnit4๋ฅผ ์œ„ํ•œ Test Engine API ์ œ๊ณต org.junit.jupiter.api.Assertions.* assertEquals 1assertEquals(0, 1+1); assertThrows, assertAll org.hamcrest.MatcherAssert.* assertThat 1// assertEquals ๋ณด๋‹ค ๊ฐ€๋…์„ฑ์ด ์ข‹๋‹ค 2assertThat(1+1, equalTo(2)); org.hamcrest.Matchers.* equalTo, is, not anyOf, everyItem hasSize, containsInAnyOrder, hasItem (collection์— ๋Œ€ํ•ด ๊ฐ•๋ ฅํ•˜๊ฒŒ ์ง€์›ํ•œ๋‹ค)
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - n^2 ๋ฐฐ์—ด ์ž๋ฅด๊ธฐ (L2)
๐Ÿง  Algorithm
1def solution(n, left, right): 2 answer = [] 3 start = (left//n, left%n) 4 end = (right//n, right%n) 5 6 for i in range(start[0], end[0]+1): 7 line = [i+1]*(i+1) + [i for i in range(i+2, n+1)] 8 answer += line 9 10 return answer[start[1]:right-(start[0]*n)+1] ๋ฌธ์ œ ์ •์ˆ˜ n, left, right๊ฐ€ ์ฃผ์–ด์ง„๋‹ค n X n ํฌ๊ธฐ์˜ 2์ฐจ์› ๋ฐฐ์—ด์„ ๋งŒ๋“ ๋‹ค i=1,2,3..n์— ๋Œ€ํ•ด์„œ, 1ํ–‰ 1์—ด๋ถ€ํ„ฐ iํ˜• iํ–‰๊นŒ์ง€ ์ˆซ์ž i๋กœ ์ฑ„์šด๋‹ค 1ํ–‰, 2ํ–‰.. nํ–‰์„ ๋ชจ๋‘ ์ด์–ด๋ถ™์ธ ์ƒˆ๋กœ์šด 1์ฐจ์› ๋ฐฐ์—ด์„ ๋งŒ๋“ ๋‹ค ์ƒˆ๋กœ์šด 1์ฐจ์› ๋ฐฐ์—ด์—์„œ left๋ฒˆ์งธ ์ˆซ์ž๋ถ€ํ„ฐ right๋ฒˆ์งธ ์ˆซ์ž๊นŒ์ง€๋ฅผ ๋ฐฐ์—ด๋กœ ๋ฐ˜ํ™˜ํ•˜๋ผ TC input n : 3, left : 2, right : 5 ouput [3, 2, 2, 3] ํ•ด๊ฒฐ๋ฐฉ๋ฒ• answer์— ํ•„์š”ํ•œ ํ–‰๋งŒ ๊ณ„์‚ฐํ•˜์—ฌ ๋ถ™์ธ๋‹ค ๋ฐ˜ํ™˜ํ• ๋•Œ offset์„ ๊ณ„์‚ฐํ•˜์—ฌ slicingํ•œ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋ฐ˜ํ™˜ํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ”ผ๋กœ๋„ (L2)
๐Ÿง  Algorithm
1def solution(k, dungeons): 2 result = 0 3 length = len(dungeons) 4 def dfs(cur, visited, cnt): 5 nonlocal result 6 visit = False 7 for i in range(length): 8 if not visited[i] and cur >= dungeons[i][0]: 9 visit = True 10 visited[i] = True 11 dfs(cur-dungeons[i][1], visited, cnt+1) 12 visited[i] = False 13 14 if not visit: 15 result = max(result, cnt) 16 17 dfs(k, [False]*length, 0) 18 19 return result ๋ฌธ์ œ ์œ ์ €์˜ ํ˜„์žฌ ํ”ผ๋กœ๋„ k, ๋˜์ „๋ณ„ [“์ตœ์†Œ ํ•„์š” ํ”ผ๋กœ๋„”, “์†Œ๋ชจ ํ”ผ๋กœ๋„”]๋ฅผ ๋‹ด์€ 2์ฐจ์› ๋ฐฐ์—ด dungeons๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ๋˜์ „์„ ํƒํ—˜ํ•˜๊ธฐ ์œ„ํ•ด์„œ๋Š” ์œ ์ €์˜ ํ˜„์žฌ ๋‚จ์€ ํ”ผ๋กœ๋„๊ฐ€ ์ตœ์†Œ ํ•„์š” ํ”ผ๋กœ๋„ ์ด์ƒ์ด์–ด์•ผ ํ•œ๋‹ค ๋˜์ „์„ ํด๋ฆฌ์–ดํ•˜๋ฉด “์†Œ๋ชจ ํ”ผ๋กœ๋„"๋งŒํผ ํ”ผ๋กœ๋„๊ฐ€ ์†Œ๋ชจ๋œ๋‹ค ๋˜์ „์„ ํƒํ—˜ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋˜์ „ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ผ TC input k:80, dungeons:[[80,20],[50,40],[30,10]] ouput 3 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• visited์— ๋ฐฉ๋ฌธํ•œ ๋˜์ „์„ ์ฒดํฌํ•˜๋ฉด์„œ DFS ํƒ์ƒ‰ํ•˜์˜€๋‹ค ๋ฐฐ์šด ์  nonlocal ํ‚ค์›Œ๋“œ๋ฅผ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - k์ง„์ˆ˜์—์„œ ์†Œ์ˆ˜ ๊ฐœ์ˆ˜ ๊ตฌํ•˜๊ธฐ (L2)
๐Ÿง  Algorithm
1def convert10toN(n, k): 2 result = '' 3 while n > 1: 4 result = str(n%k)+ result 5 n = n // k 6 return (str(n)+result).lstrip('0') 7 8def is_prime(n): 9 if n <= 1: 10 return False 11 12 end = int(n**(1/2))+1 13 for i in range(2, end): 14 if n%i == 0: 15 return False 16 return True 17 18 19def solution(n, k): 20 A = convert10toN(n, k) 21 answer = 0 22 for i in A.split('0'): 23 if i == '': continue 24 if is_prime(int(i)): 25 answer += 1 26 27 return answer ๋ฌธ์ œ ์–‘์˜ ์ •์ˆ˜ n๊ณผ k๊ฐ€ ์ฃผ์–ด์ง„๋‹ค n์„ k์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ–ˆ์„ ๋•Œ, ์•„๋ž˜ ์กฐ๊ฑด์— ๋งž๋Š” ์†Œ์ˆ˜๊ฐ€ ๋ช‡ ๊ฐœ์ธ์ง€ ๊ตฌํ•˜๋ผ 0P0, P0, 0P, P TC input n: 437674, k: 3 ouput 3 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• 10์ง„์ˆ˜๋ฅผ k์ง„์ˆ˜๋กœ ๋ณ€ํ™˜ํ•˜๋Š” ํ•จ์ˆ˜, ์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜๋Š” ํ•จ์ˆ˜๋ฅผ ์ •์˜ํ•ด์„œ ํ•ด๊ฒฐํ•˜์˜€๋‹ค ์†Œ์ˆ˜๋ฅผ ํŒ๋ณ„ํ•  ๋•Œ, ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ฅผ ์‚ฌ์šฉํ–ˆ๋‹ค๊ฐ€, ๋Ÿฐํƒ€์ž„์—๋Ÿฌ๋ฅผ ๋ณด๊ณ , ์ œ๊ณฑ๊ทผ๊นŒ์ง€ ๋‚˜๋ˆ„์–ด๋ณด๋Š” ๋ฐฉ์‹์œผ๋กœ ๋ฐ”๊ฟจ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ฃผ์ฐจ ์š”๊ธˆ ๊ณ„์‚ฐ (L2)
๐Ÿง  Algorithm
1import math 2 3def diff(start, end): 4 sh, sm = map(int, start.split(':')) 5 eh, em = map(int, end.split(':')) 6 7 return (eh*60+em) - (sh*60+sm) 8 9def calc(time, baseTime, baseFee, unitTime, unitFee): 10 if time < baseTime: 11 return baseFee 12 time -= baseTime 13 return baseFee + math.ceil(time/unitTime)*unitFee 14 15def solution(fees, records): 16 cars = {} 17 for i in records: 18 time, car_num, _ = i.split(' ') 19 # ์ƒˆ๋กœ ์ž…์ฐจ ํ•œ ๊ฒฝ์šฐ 20 if not car_num in cars: 21 cars[car_num] = [0, time] 22 else: 23 # ์ถœ์ฐจ ํ›„ ๋‹ค์‹œ ์ž…์ฐจํ•œ ๊ฒฝ์šฐ 24 if cars[car_num][1] == '': 25 cars[car_num][1] = time 26 # ์ถœ์ฐจํ•œ ๊ฒฝ์šฐ 27 else: 28 cars[car_num][0] += diff(cars[car_num][1], time) 29 cars[car_num][1] = '' 30 31 # ์•„์ง ์ถœ์ฐจํ•˜์ง€ ์•Š์€ ์ฐจ๋Ÿ‰๋“ค์— ๋Œ€ํ•ด 23:59์— ์ถœ์ฐจํ•œ ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผ 32 for num in cars: 33 if cars[num][1] != '': 34 cars[num][0] += diff(cars[num][1], '23:59') 35 cars[num][1] = '' 36 37 # ์š”๊ธˆ ๊ณ„์‚ฐ 38 for num in cars: 39 cars[num] = calc(cars[num][0], fees[0], fees[1], fees[2], fees[3]) 40 41 # ์ฐจ๋Ÿ‰ ๋ฒˆํ˜ธ ์ˆœ์œผ๋กœ ์ •๋ ฌ 42 sorted_keys = sorted(cars.keys()) 43 # ์š”๊ธˆ๋งŒ ์ถ”์ถœํ•ด์„œ ๋ฐ˜ํ™˜ 44 return [cars[key] for key in sorted_keys] ๋ฌธ์ œ ๊ธฐ๋ณธ ์‹œ๊ฐ„, ๊ธฐ๋ณธ ์š”๊ธˆ, ๋‹จ์œ„ ์‹œ๊ฐ„, ๋‹จ์œ„ ์š”๊ธˆ ์ฐจ๋Ÿ‰์˜ ์ž…์ถœ์ฐจ ๊ธฐ๋ก (์‹œ๊ฐ(HH:MM), ์ฐจ๋Ÿ‰๋ฒˆํ˜ธ(XXXX), ๋‚ด์—ญ(์ž…์ฐจ/์ถœ์ฐจ)) ์œ„ ์ •๋ณด๊ฐ€ ์ฃผ์–ด์งˆ๋•Œ, ๊ฐ ์ฐจ๋Ÿ‰๋ณ„ ์ฃผ์ฐจ ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•ด์„œ ์ฐจ๋Ÿ‰๋ฒˆํ˜ธ ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์—ฌ ๋ฐ˜ํ™˜ํ•˜๋ผ ์ž…์ฐจ๋งŒ ํ•˜๊ณ  ์ถœ์ฐจํ•˜์ง€ ์•Š์€ ์ฐจ๋Ÿ‰์€, 23:59์— ์ถœ์ฐจํ•œ ๊ฒƒ์œผ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค TC input fees: [180, 5000, 10, 600] records: [“05:34 5961 IN”, “06:00 0000 IN”, “06:34 0000 OUT”, “07:59 5961 OUT”, “07:59 0148 IN”, “18:59 0000 IN”, “19:09 0148 OUT”, “22:59 5961 IN”, “23:00 5961 OUT”] ouput [14600, 34400, 5000] ํ•ด๊ฒฐ๋ฐฉ๋ฒ• cars๋ผ๋Š” dictionary์— ์ฐจ๋Ÿ‰๋ฒˆํ˜ธ๋ฅผ key๋กœ, [์ฃผ์ฐจ์‹œ๊ฐ„, ์ž…์ฐจ์‹œ๊ฐ„]์„ value๋กœ ์ €์žฅํ•œ๋‹ค ๋งˆ์ง€๋ง‰์— ํ•œ๋ฒˆ์— ์š”๊ธˆ์„ ๊ณ„์‚ฐํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์–‘๊ถ๋Œ€ํšŒ (L2)
๐Ÿง  Algorithm
1def solution(n, info): 2 # ๊ฐ๊ฐ ๋ช‡ ๋ฒˆ ๋งž์ถฐ์•ผ ์ ์ˆ˜๋ฅผ ์–ป๋Š”์ง€ ์ €์žฅํ•˜์˜€๋‹ค 3 goal_list = [i+1 for i in info] 4 5 cases = [] 6 7 def dfs(score, cnt, case): 8 # ๋ช‡ ๋ฒˆ์งธ ์ ์ˆ˜์ธ์ง€ ๋‚˜ํƒ€๋‚ธ๋‹ค (0:10์ , 1:9์ , ...) 9 length = len(case) 10 if length == 11: 11 # ํ™”์‚ด ๊ฐœ์ˆ˜๊ฐ€ ๋‚จ์•˜๋‹ค๋ฉด 0์ ์— ์ฑ„์›Œ์ค€๋‹ค 12 if cnt != n: 13 case[-1] += n-cnt 14 cases.append((score, case)) 15 return 16 # ํ˜„์žฌ ๋‹จ๊ณ„์—์„œ ๋ช‡ ์  ๋งž์•„์•ผ ์ ์ˆ˜๋ฅผ ๋”ฐ๋Š”์ง€๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค 17 goal = goal_list[length] 18 19 # ์ ์ˆ˜๋ฅผ ๋”ฐ๋Š” ๊ฒฝ์šฐ 20 if cnt + goal <= n: 21 # ๋”ด ์ ์ˆ˜๋ฅผ ๋”ํ•ด์ค€๋‹ค 22 dfs(score+(10-length), cnt+goal, case+[goal]) 23 # ์ƒ๋Œ€๊ฐ€ ์ ์ˆ˜๋ฅผ ๋”ฐ๋Š” ๊ฒฝ์šฐ 24 if goal != 1: 25 # ์ƒ๋Œ€๊ฐ€ ๋”ด ์ ์ˆ˜๋ฅผ ๋นผ์ค€๋‹ค 26 dfs(score-(10-length), cnt, case+[0]) 27 # ์•„๋ฌด๋„ ๋ชป ๋งž์ถ”๋Š” ๊ฒฝ์šฐ 28 else: 29 dfs(score, cnt, case+[0]) 30 31 dfs(0, 0, []) 32 # ์ ์ˆ˜๊ฐ€ ๊ฐ™๋‹ค๋ฉด, ๋‚ฎ์€ ์ ์ˆ˜๋ฅผ ๋” ๋งŽ์ด ๋งž์ถ˜ ๊ฒฝ์šฐ๋ฅผ ๋ฐ˜ํ™˜ํ•˜๊ธฐ ์œ„ํ•ด ์—ญ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜์˜€๋‹ค 33 cases.sort(key= lambda x: (x[0], x[1][::-1])) 34 35 if cases[-1][0] > 0: 36 return cases[-1][1] 37 # ๊ฐ€์žฅ ์šฐ์„ ์ˆœ์œ„๊ฐ€ ๋†’์€ case์˜ ์ ์ˆ˜๊ฐ€ ์Œ์ˆ˜์ธ ๊ฒฝ์šฐ, ๋ฌด์กฐ๊ฑด ์ง€๋Š” ๊ฒฝ์šฐ๋กœ ๊ฐ„์ฃผํ•œ๋‹ค 38 return [-1] ๋ฌธ์ œ 1๋Œ€1๋กœ ์–‘๊ถ ๊ฒฝ๊ธฐ๋ฅผ ํ•œ๋‹ค, ์ ์ˆ˜๋Š” 10์ ~0์ ๊นŒ์ง€ ์žˆ๋‹ค ์ƒ๋Œ€๋ณด๋‹ค ๊ฐ™์€ ์ ์ˆ˜๋ฅผ ๋งŽ์ด ๋งž์ถฐ์•ผ ์ ์ˆ˜๋ฅผ ์–ป๋Š”๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ์ƒ๋Œ€๊ฐ€ 10์ ์„ 3๋ฒˆ ๋งž์ท„๋‹ค๊ณ ํ•˜์ž, ์ด๋•Œ 10์ ์„ 4๋ฒˆ ๋งž์ถ”๋ฉด 10์ ์„ ์–ป์„ ์ˆ˜ ์žˆ๊ณ , 2๋ฒˆ ๋งž์ถ”๋ฉด ์ƒ๋Œ€๊ฐ€ 10์ ์„ ์–ป๋Š”๋‹ค ํ™”์‚ด์˜ ๊ฐœ์ˆ˜ n, ์ƒ๋Œ€ ์„ ์ˆ˜๊ฐ€ ๋งžํžŒ ๊ณผ๋… ์ ์ˆ˜์˜ ๊ฐœ์ˆ˜๋ฅผ 10์ ๋ถ€ํ„ฐ 0๊นŒ์ง€ ๋‹ด์€ ์ •์ˆ˜๋ฐฐ์—ด info๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ๊ฐ€์žฅ ํฐ ์ ์ˆ˜ ์ฐจ์ด๋กœ ์ด๊ธฐ๊ธฐ ์œ„ํ•ด ์–ด๋–ค ์ ์ˆ˜๋ฅผ ๋ช‡ ๋ฒˆ ๋งžํ˜€์•ผ ํ•˜๋Š”์ง€ ์ •์ˆ˜ ๋ฐฐ์—ด๋กœ ๊ตฌํ•˜๋ผ ๋งŒ์•ฝ ๋ฌด์กฐ๊ฑด ์ง€๋Š” ๊ฒฝ์šฐ -1์„ ๋ฐ˜ํ™˜ํ•˜๋ผ ๋งŒ์•ฝ ์ ์ˆ˜ ์ฐจ์ด๊ฐ€ ๊ฐ™๋‹ค๋ฉด, ๊ฐ€์žฅ ๋‚ฎ์€ ์ ์ˆ˜๋ฅผ ๋” ๋งŽ์ด ๋งžํžŒ ๊ฒฝ์šฐ๋ฅผ return ํ•˜๋ผ TC input 5, [2,1,1,1,0,0,0,0,0,0,0] ouput [0,2,2,0,1,0,0,0,0,0,0] ํ•ด๊ฒฐ๋ฐฉ๋ฒ• DFS๋ฅผ ์ด์šฉํ•˜์—ฌ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜์—ฌ ํ•ด๊ฒฐํ•˜์˜€๋‹ค ์ž์„ธํ•œ ์„ค๋ช…์€ ์ฃผ์„์œผ๋กœ ๋Œ€์ฒดํ•˜์˜€๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋‘ ํ ํ•ฉ ๊ฐ™๊ฒŒ ๋งŒ๋“ค๊ธฐ (L2)
๐Ÿง  Algorithm
1from collections import deque 2 3def solution(queue1, queue2): 4 sum1, sum2 = sum(queue1), sum(queue2) 5 dq1 = deque(queue1) 6 dq2 = deque(queue2) 7 cnt = 0 8 9 while cnt <= len(queue1)*2+1 and sum1 != sum2: 10 if sum1 > sum2: 11 tmp = dq1.popleft() 12 dq2.append(tmp) 13 sum1 -= tmp 14 sum2 += tmp 15 elif sum1 < sum2: 16 tmp = dq2.popleft() 17 dq1.append(tmp) 18 sum1 += tmp 19 sum2 -= tmp 20 cnt += 1 21 22 return cnt if sum1 == sum2 else -1 ๋ฌธ์ œ ๊ธธ์ด๊ฐ€ ๊ฐ™์€ ๋‘ ํ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ๋‘ ํ์˜ ํ•ฉ์ด ๊ฐ™์•„์ง€๋„๋ก ํ์˜ ์›์†Œ๋ฅผ ๊ตํ™˜ํ•  ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ํšŸ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ผ ํ์˜ pop์€ ์™ผ์ชฝ์—์„œ, push๋Š” ์˜ค๋ฅธ์ชฝ์—์„œ ์ด๋ฃจ์–ด์ง„๋‹ค TC input queue1 : [3, 2, 7, 2], queue2 : [4 ,6, 5, 1] ouput 2 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• deque๋ฅผ ์ด์š”ํ•ด์„œ ํ๋ฅผ ๊ตฌํ˜„ํ•˜์˜€๋‹ค ๋‘ ํ์˜ ํ•ฉ์ด ๊ฐ™์•„์งˆ๋•Œ๊นŒ์ง€, ํ•ฉ์ด ํฐ ํ์—์„œ ์ž‘์€ ํ๋กœ ์›์†Œ๋ฅผ ์ด๋™์‹œํ‚จ๋‹ค ๋ฐฉ๋ฒ•์ด ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๊ฒฝ์šฐ ๋ฌดํ•œ๋ฃจํ”„๊ฐ€ ๋ฐœ์ƒํ•˜๊ธฐ ๋•Œ๋ฌธ์—, (ํ์˜ ๊ธธ์ด)*2+1 ๋งŒํผ๋งŒ ๋ฐ˜๋ณตํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ• ์ธ ํ–‰์‚ฌ (L2)
๐Ÿง  Algorithm
1from collections import deque 2 3def solution(want, number, discount): 4 want_dict = dict() 5 answer = 0 6 7 for i in range(len(want)): 8 want_dict[want[i]] = number[i] 9 10 for i in discount[:10]: 11 if i in want_dict: 12 want_dict[i] -= 1 13 14 for i in range(0, len(discount)-9): 15 if all(map(lambda x: x <= 0, want_dict.values())): 16 answer += 1 17 18 if discount[i] in want_dict: 19 want_dict[discount[i]] += 1 20 if i+10 < len(discount) and discount[i+10] in want_dict: 21 want_dict[discount[i+10]] -= 1 22 23 return answer ๋ฌธ์ œ XYZ๋งˆํŠธ์—์„œ๋Š” ํšŒ์›์— ๊ฐ€์ž…ํ•˜๋ฉด 10์ผ๋™์•ˆ ํ• ์ธํ˜œํƒ์„ ๋ฐ›๋Š”๋‹ค ํ• ์ธํ•˜๋Š” ์ œํ’ˆ์€ ํ•˜๋ฃจ์— ํ•˜๋‚˜์”ฉ๋งŒ ๊ตฌ๋งคํ•  ์ˆ˜ ์žˆ๋‹ค ์ •ํ˜„์ด๊ฐ€ ์›ํ•˜๋Š” ์ œํ’ˆ ๋ฆฌ์ŠคํŠธ, ์›ํ•˜๋Š” ์ œํ’ˆ์˜ ์ˆ˜๋Ÿ‰ ๋ฆฌ์ŠคํŠธ, ๋งˆํŠธ์—์„œ ํ• ์ธํ•˜๋Š” ์ œํ’ˆ ๋ฆฌ์ŠคํŠธ๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ์ •ํ˜„์ด๊ฐ€ ์›ํ•˜๋Š” ์ œํ’ˆ์„ ๋ชจ๋‘ ํ• ์ธ ๋ฐ›์„ ์ˆ˜ ์žˆ๋Š” ํšŒ์› ๋“ฑ๋ก ๋‚ ์งœ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ผ TC input want: [“banana”, “apple”, “rice”, “pork”, “pot”] number: [3, 2, 2, 2, 1] discount: [“chicken”, “apple”, “apple”, “banana”, “rice”, “apple”, “pork”, “banana”, “pork”, “rice”, “pot”, “banana”, “apple”, “banana”] ouput 5 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ์›ํ•˜๋Š” ์ œํ’ˆ์„ dict๋กœ ๋งŒ๋“ ๋‹ค (key: ์ œํ’ˆ์ด๋ฆ„, value: ์ˆ˜๋Ÿ‰) ์›ํ•˜๋Š” ์ œํ’ˆ - ์ฒซ๋‚ ์— ๊ฐ€์ž…ํ–ˆ์„ ๋•Œ ํ• ์ธํ•˜๋Š” ์ œํ’ˆ์„ ๊ณ„์‚ฐํ•œ๋‹ค ๋ฐ˜๋ณต๋ฌธ์„ ์ˆœํšŒํ•˜๋ฉด์„œ ํ• ์ธํ•˜๋Š” ์ œํ’ˆ์„ ๋นผ๊ณ , ํ• ์ธํ•˜๋Š” ์ œํ’ˆ์„ ๋”ํ•œ๋‹ค (์ œํ’ˆ์ด ๋” ํ•„์š”ํ•˜๋ฉด ์–‘์ˆ˜, ๋œ ํ•„์š”ํ•˜๋ฉด ์Œ์ˆ˜) 0๋ณด๋‹ค ํฐ ์ˆ˜๊ฐ€ ์žˆ์œผ๋ฉด answer์— 1์„ ๋”ํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ˜ผ์ž ๋†€๊ธฐ์˜ ๋‹ฌ์ธ (L2)
๐Ÿง  Algorithm
1def solution(cards): 2 length = len(cards) 3 visited = [False] * length 4 answer = [] 5 6 for i in range(length): 7 cnt = 0 8 cur = i 9 while not visited[cur-1]: 10 visited[cur-1] = True 11 cur = cards[cur-1] 12 cnt += 1 13 if cnt != 0: 14 answer.append(cnt) 15 16 if len(answer) <= 1: 17 return 0 18 answer.sort(reverse=True) 19 return answer[0]*answer[1] ๋ฌธ์ œ ์ฃผ์–ด์ง„ ๋ฐฐ์—ด cards๋ฅผ ์ˆœํšŒํ•œ๋‹ค cards[i]๋ฒˆ์งธ ์›์†Œ๋ฅผ ๋ฐฉ๋ฌธํ•œ๋‹ค, ์ด๋ฏธ ๋ฐฉ๋ฌธํ•œ ์›์†Œ์ธ ๊ฒฝ์šฐ ๊ทธ๋งŒํ•œ๋‹ค ํ•œ๋ฒˆ ์ด์–ด์„œ ๋ฐฉ๋ฌธํ•œ ์›์†Œ๋ฅผ ๊ทธ๋ฃนํ™”ํ•œ๋‹ค๊ณ  ํ•  ๋•Œ, ๋‘ ๊ทธ๋ฃน์˜ ์›์†Œ๊ฐœ์ˆ˜์˜ ๊ณฑ์˜ ์ตœ๋Œ€๊ฐ’์„ ๊ตฌํ•˜๋ผ TC input [8,6,3,7,2,5,1,4] ouput 12 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• while๋ฌธ์„ ํ•œ๋ฒˆ ๋Œ๋ฉด์„œ, ์›์†Œ์˜ ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ์ฒดํฌํ•˜๊ณ , ๋ฐฉ๋ฌธํ•œ ์›์†Œ์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ผ๋‹ค ๊ทธ๋ฃนํ™”๋œ ์›์†Œ๋ฅผ answer์— ์ถ”๊ฐ€ํ•œ๋‹ค answer๋ฅผ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๊ณ , ์ฒซ๋ฒˆ์งธ ๋‘๋ฒˆ์งธ ์›์†Œ์˜ ๊ณฑ์„ ๋ฐ˜ํ™˜ํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์—ฐ์† ์ˆ˜์—ด ํ•ฉ์˜ ๊ฐœ์ˆ˜ (L2)
๐Ÿง  Algorithm
์ฒซ๋ฒˆ์งธ ํ’€์ด 1def solution(elements): 2 result = set() 3 length = len(elements) 4 elements = elements*2 5 for i in range(length): 6 temp = 0 7 for j in range(length): 8 temp += elements[i+j] 9 result.add(temp) 10 11 return len(result) ๊ฐœ์„ ํ•œ ํ’€์ด 1def solution(elements): 2result = set() 3length = len(elements) 4for i in range(length): 5 temp = 0 6 for j in range(length): 7 temp += elements[(i+j)%length] 8 result.add(temp) 9 10return len(result) ๋ฌธ์ œ ์ฃผ์–ด์ง„ ์ •์ˆ˜ ๋ฐฐ์—ด๋กœ ์›ํ˜• ์ˆ˜์—ด์„ ๋งŒ๋“ ๋‹ค ์›ํ˜• ์ˆ˜์—ด์˜ ์—ฐ์†๋œ ๋ถ€๋ถ„ ์ˆ˜์—ด์˜ ํ•ฉ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜์—ฌ๋ผ TC input [7,9,1,1,4] ouput 18 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ์ฒซ๋ฒˆ์งธ ํ’€์ด์—์„œ๋Š” ๋ฐฐ์—ด์„ 2๋ฐฐ๋กœ ๋Š˜๋ ค์„œ ์›ํ˜• ์ˆ˜์—ด์„ ๋งŒ๋“ค์—ˆ๋‹ค ๊ฐœ์„ ํ•œ ํ’€์ด์—์„œ๋Š” mod ์—ฐ์‚ฐ์„ ์ด์šฉํ•ด์„œ ์›ํ˜• ์ˆ˜์—ด์„ ๋งŒ๋“ค์—ˆ๋‹ค set๋ฅผ ์ด์šฉํ•ด์„œ ์ค‘๋ณต์„ ์ œ๊ฑฐํ•˜๊ณ  ์›์†Œ ๊ฐœ์ˆ˜๋ฅผ ๋ฐ˜ํ™˜ํ•˜์˜€๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํƒ๋ฐฐ์ƒ์ž (L2)
๐Ÿง  Algorithm
1def solution(order): 2 answer = 0 3 length = len(order) 4 stackA = [i for i in range(length, 0, -1)] 5 stackB = [] 6 7 for i in order: 8 while True: 9 if stackA and stackA[-1] == i: 10 stackA.pop() 11 break 12 if stackB and stackB[-1] == i: 13 stackB.pop() 14 break 15 16 if stackB and stackB[-1] > i: 17 return answer 18 19 stackB.append(stackA.pop()) 20 answer += 1 21 22 return answer ๋ฌธ์ œ ์›ํ•˜๋Š” ์ƒ์ž ์ˆœ์„œ๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜๋ฐฐ์—ด order๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ์— [N… 3, 2, 1]์™€ ๊ฐ™์ด ๋ฐ•์Šค๊ฐ€ ๋†“์—ฌ์žˆ๋‹ค ๋ฐ•์Šค๋Š” 1๋ฒˆ ์ƒ์ž๋ถ€ํ„ฐ ์ˆœ์ฐจ์ ์œผ๋กœ ๋บ„ ์ˆ˜ ์žˆ๋‹ค ๋บ€ ์ƒ์ž๋ฅผ ์ž ๊น ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ์— ๋ณด๊ด€ํ•  ์ˆ˜ ์žˆ๋‹ค ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ๋Š” ์Šคํƒ๊ณผ ๊ฐ™์ด FILO๊ฐ€ ์ ์šฉ๋œ๋‹ค ์ˆœ์„œ๋Œ€๋กœ ์ƒ์ž๋ฅผ ์‹ฃ์ง€ ๋ชปํ•˜๋ฉด, ๊ทธ๋งŒ๋‘”๋‹ค ๋ฐ•์Šค๋ฅผ order์— ๋งž๊ฒŒ ๋ช‡ ๊ฐœ๊นŒ์ง€ ์‹ค์„ ์ˆ˜ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋ผ TC input [4, 3, 1, 2, 5] ouput 2 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ์ง๊ด€์ ์œผ๋กœ stackA, stackB๋ฅผ ์„ ์–ธํ•˜์˜€๋‹ค stackA๊ฐ€ ์ฃผ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ, stackB๊ฐ€ ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ ์—ญํ• ์„ ํ•œ๋‹ค order๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ์ˆœ์„œ์— ๋งž๋Š” ์ƒ์ž๊ฐ€ ๋‚˜์˜ฌ ๋•Œ ๊นŒ์ง€, ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ๋กœ ๋ณด๋‚ด๊ธฐ๋ฅผ ๋ฐ˜๋ณตํ•œ๋‹ค ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋ฒจํŠธ์˜ top์ด ๊บผ๋‚ด์•ผ ํ•  ์š”์†Œ๋ณด๋‹ค ํฐ ๊ฒฝ์šฐ, ๊บผ๋‚ผ ์ƒ์ž๊ฐ€ ๋ณด์กฐ ์ปจ๋ฒ ์ด์–ด ๋’ค์ชฝ์— ์žˆ๋‹ค๋Š” ์˜๋ฏธ์ด๋ฏ€๋กœ ๋ฐ˜๋ณต๋ฌธ์„ ๋น ์ ธ๋‚˜์˜จ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋กค์ผ€์ดํฌ ์ž๋ฅด๊ธฐ (L2)
๐Ÿง  Algorithm
1def solution(topping): 2 answer = 0 3 length = len(topping) 4 toppingA = [] 5 toppingB = [] 6 setA = set() 7 setB = set() 8 9 for i in range(length-1): 10 setA.add(topping[i]) 11 setB.add(topping[length-i-1]) 12 toppingA.append(len(setA)) 13 toppingB.append(len(setB)) 14 15 toppingB = toppingB[::-1] 16 for i in range(length-1): 17 if toppingA[i] == toppingB[i]: 18 answer+=1 19 return answer ๋ฌธ์ œ ๋กค์ผ€์ดํฌ ์œ„์— ์˜ฌ๋ ค์ง„ ํ† ํ•‘๋ฒˆํ˜ธ์˜ ์ •์ˆ˜ ๋ฐฐ์—ด topping์ด ์ฃผ์–ด์ง„๋‹ค ๋กค์ผ€์ดํฌ๋ฅผ ์ž˜๋ž์„ ๋•Œ, ๋‘ ์กฐ๊ฐ์˜ ํ† ํ•‘ ์ข…๋ฅ˜๋ฅผ ๋˜‘๊ฐ™์ด ๋งŒ๋“œ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ผ TC input [1, 2, 1, 3, 1, 4, 1, 2] ouput 2 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• toppingA์—๋Š” ์™ผ์ชฝ์—์„œ๋ถ€ํ„ฐ ํ† ํ•‘ ์ข…๋ฅ˜์˜ ๋ˆ„์ ํ•ฉ์„, toppingB์—๋Š” ์˜ค๋ฅธ์ชฝ์—์„œ๋ถ€ํ„ฐ ํ† ํ•‘ ์ข…๋ฅ˜์˜ ๋ˆ„์ ํ•ฉ์„ ์ €์žฅํ•œ๋‹ค toppingB๋ฅผ ์—ญ์ˆœ์œผ๋กœ ๋งŒ๋“ ๋‹ค toppingA,B๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ๋‘ ๋ฆฌ์ŠคํŠธ์˜ ๊ฐ’์„๋•Œ ์–‘์ชฝ์˜ ํ† ํ•‘ ์ข…๋ฅ˜ ๊ฐœ์ˆ˜๊ฐ€ ๊ฐ™์œผ๋ฏ€๋กœ, answer๋ฅผ 1 ์ฆ๊ฐ€์‹œํ‚จ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์šฐ๋ฐ•์ˆ˜์—ด ์ •์ ๋ถ„ (L2)
๐Ÿง  Algorithm
1def solution(k, ranges): 2 answer = [] 3 seq = [k] 4 section = [0] 5 while k > 1: 6 if k%2 == 0: 7 k = k//2 8 else: 9 k = k*3+1 10 seq.append(k) 11 12 for i in range(0, len(seq)-1): 13 a, b = seq[i], seq[i+1] 14 if a > b: 15 a, b = b, a 16 17 section.append((b-a)/2+a) 18 if len(section) != 0: 19 section[-1] += section[-2] 20 21 for i in ranges: 22 a, b = i[0], len(seq)+i[1]-1 23 if a > b: 24 answer.append(-1.0) 25 else: 26 answer.append(section[b]-section[a]) 27 return answer ๋ฌธ์ œ ์–ด๋–ค ์ˆ˜ K์— ๋Œ€ํ•ด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ž‘์—…์„ ๋ฐ˜๋ณตํ•˜๋ฉด ํ•ญ์ƒ 1์„ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. ์ž…๋ ฅ๋œ ์ˆ˜๊ฐ€ ์ง์ˆ˜๋ผ๋ฉด 2๋กœ ๋‚˜๋ˆ„๊ณ , ํ™€์ˆ˜๋ผ๋ฉด 3์„ ๊ณฑํ•˜๊ณ  1์„ ๋”ํ•ฉ๋‹ˆ๋‹ค. ๊ฒฐ๊ณผ๋กœ ๋‚˜์˜จ ์ˆ˜๊ฐ€ 1๋ณด๋‹ค ํฌ๋‹ค๋ฉด 1๋ฒˆ ์ž‘์—…์„ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. ์ฃผ์–ด์ง„ ์ˆ˜๊ฐ€ 5๋ผ๋ฉด 5 => 16 => 8 => 4 => 2 => 1 ๊ณผ ๊ฐ™์ด ๋งŒ๋“ค ์ˆ˜ ์žˆ๋‹ค. ์ด๋Ÿฌํ•œ ์ˆ˜์—ด์„ ์šฐ๋ฐ•์ˆ˜์—ด์ด๋ผ๊ณ  ํ•˜๋Š”๋ฐ, ์ด ์ˆ˜์—ด์„ ์ขŒํ‘œํ‰๋ฉด์œผ๋กœ ์˜ฎ๊ฒจ์„œ ์ ์„ ์ฐ๋Š”๋‹ค ์ฃผ์–ด์ง„ ์ˆ˜๊ฐ€ 5๋ผ๋ฉด (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1)์— ์ ์„ ์ฐ๋Š”๋‹ค [์‹œ์ž‘ํ•˜๋Š” x์ขŒํ‘œ, ๋๋‚˜๋Š” ์ ์˜ x์— ๋Œ€ํ•œ ์˜คํ”„์…‹]์ด ์ฃผ์–ด์งˆ ๋•Œ, ํ•ด๋‹น ๊ตฌ๊ฐ„์˜ ์ •์ ๋ถ„์„ ๊ตฌํ•˜๋ผ ์‹œ์ž‘์ ๋ณด๋‹ค ๋์ ์ด ํฐ ๊ฒฝ์šฐ ์ •์ ๋ถ„ ๊ฒฐ๊ณผ๋Š” -1๋กœ ์ •์˜ํ•œ๋‹ค TC input k:5, ranges:[[0,0],[0,-1],[2,-3],[3,-3]] ouput [33.0,31.5,0.0,-1.0] ํ•ด๊ฒฐ๋ฐฉ๋ฒ• seq์—๋Š” ์ฃผ์–ด์ง„ k์— ๋Œ€ํ•œ ์šฐ๋ฐ• ์ˆ˜์—ด์„ ์ €์žฅํ•œ๋‹ค section์—๋Š” seq์˜ ๊ฐ ๊ตฌ๊ฐ„์˜ ์ •์ ๋ถ„์„ ๋ˆ„์ ํ•ฉ์œผ๋กœ ์ €์žฅํ•œ๋‹ค ranges๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ๋ˆ„์ ํ•ฉ ๋ฐฐ์—ด์—์„œ ํ•ด๋‹น ๊ตฌ๊ฐ„์˜ ์ •์ ๋ถ„์„ ๊ตฌํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ˆซ์ž ์นด๋“œ ๋‚˜๋ˆ„๊ธฐ (L2)
๐Ÿง  Algorithm
์ฒซ๋ฒˆ์งธ ํ†ต๊ณผํ•œ ํ’€์ด 1import math 2 3def gcd(a, b): 4 while b > 0: 5 a, b = b, a%b 6 return a 7 8def gcdOfArr(l): 9 result = l[0] 10 for i in range(1, len(l)): 11 result = gcd(result, l[i]) 12 return result 13 14def solution(arrayA, arrayB): 15 a1 = gcdOfArr(arrayA) 16 for i in arrayB: 17 if i % a1 == 0: 18 a1 = 0 19 break 20 a2 = gcdOfArr(arrayB) 21 for i in arrayA: 22 if i % a2 == 0: 23 a2 = 0 24 break 25 return max(a1, a2) ๊ฐœ์„ ํ•œ ํ’€์ด 1import math 2from functools import reduce 3 4def gcd(a, b): 5 while b > 0: 6 a, b = b, a%b 7 return a 8 9def solution(arrayA, arrayB): 10 a1 = reduce(gcd, arrayA) 11 a1 = 0 if any(i % a1 == 0 for i in arrayB) else a1 12 a2 = reduce(gcd, arrayB) 13 a2 = 0 if any(i % a2 == 0 for i in arrayA) else a2 14 return max(a1, a2) ๋ฌธ์ œ ์ฒ ์ˆ˜๊ฐ€ ๊ฐ€์ง„ ์ˆซ์ž์˜ ๋ฐฐ์—ด arrayA, ์˜ํฌ๊ฐ€ ๊ฐ€์ง„ ์ˆซ์ž์˜ ๋ฐฐ์—ด arrayB๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ์ฒ ์ˆ˜๊ฐ€ ๊ฐ€์ง„ ์นด๋“œ๋“ค์˜ ๋ชจ๋“  ์ˆซ์ž๋ฅผ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๊ณ , ์˜ํฌ๊ฐ€ ๊ฐ€์ง„ ์ˆซ์ž๋Š” ํ•˜๋‚˜๋„ ๋‚˜๋ˆŒ ์ˆ˜ ์—†๋Š” ์–‘์˜ ์ •์ˆ˜ a ์˜ํฌ๊ฐ€ ๊ฐ€์ง„ ์นด๋“œ๋“ค์˜ ๋ชจ๋“  ์ˆซ์ž๋ฅผ ๋‚˜๋ˆŒ ์ˆ˜ ์žˆ๊ณ , ์ฒ ์ˆ˜๊ฐ€ ๊ฐ€์ง„ ์ˆซ์ž๋Š” ํ•˜๋‚˜๋„ ๋‚˜๋ˆŒ ์ˆ˜ ์—†๋Š” ์–‘์˜ ์ •์ˆ˜ a ๊ฐ€์žฅ ํฐ ์–‘์˜ ์ •์ˆ˜ a๋ฅผ ๊ตฌํ•˜๋ผ, ์—†๋‹ค๋ฉด 0์„ ๋ฐ˜ํ™˜ํ•˜๋ผ TC input [14, 35, 119] ouput 7 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค์—์„œ ์ง€์›ํ•˜๋Š” ํŒŒ์ด์ฌ์ด 3.8์ด๋ผ์„œ ๋‚ด์žฅํ•จ์ˆ˜ math.gcd(3.9๋ถ€ํ„ฐ ์ง€์›)๋ฅผ ์‚ฌ์šฉํ•˜์ง€ ๋ชปํ–ˆ๋‹ค ์œ ํด๋ฆฌ๋“œ ํ˜ธ์ œ๋ฒ• ๊ธฐ์–ต์ด ๋‚˜์ง€ ์•Š์•„์„œ ์•ฝ๊ฐ„์˜ ๊ตฌ๊ธ€๋ง์„ ํ†ตํ•ด ํ•ด๊ฒฐํ•˜์˜€๋‹ค reduce์™€ anyํ•จ์ˆ˜๋ฅผ ํ†ตํ•ด ์ฝ”๋“œ์˜ ๊ธธ์ด๋ฅผ ๋Œ€ํญ ๊ฐ์†Œ ์‹œํ‚ฌ ์ˆ˜ ์žˆ์—ˆ๋‹ค, ์ž์ฃผ ํ™œ์šฉํ•˜์ž
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๊ทค ๊ณ ๋ฅด๊ธฐ (L2)
๐Ÿง  Algorithm
1def solution(k, tangerine): 2 D = {} 3 for i in tangerine: 4 if i in D: 5 D[i] += 1 6 else: 7 D[i] = 1 8 D = sorted(D.items(), key=lambda x: -x[1]) 9 answer = 0 10 for _, num in D: 11 k -= num 12 answer += 1 13 if k <= 0: 14 break 15 16 return answer ๋ฌธ์ œ ๊ทค์˜ ๊ฐœ์ˆ˜ k์™€ ๊ทค์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด tangerine์ด ์ฃผ์–ด์ง„๋‹ค ๊ทค k๊ฐœ๋ฅผ ๊ณ ๋ฅผ ๋•Œ, ํฌ๊ธฐ๊ฐ€ ์„œ๋กœ ๋‹ค๋ฅธ ์ข…๋ฅ˜์˜ ์ˆ˜์˜ ์ตœ์†Œ๊ฐ’์„ ๊ตฌํ•˜๋ผ TC input k: 6, tangerine: [1, 3, 2, 5, 4, 5, 2, 3] ouput 3 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ๋”•์…”๋„ˆ๋ฆฌ์— ๊ทค์˜ ์ข…๋ฅ˜์™€ ๊ฐœ์ˆ˜๋ฅผ ์ €์žฅํ•œ๋‹ค ๋”•์…”๋„ˆ๋ฆฌ๋ฅผ ๊ทค์˜ ๊ฐœ์ˆ˜ ๊ธฐ์ค€์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌํ•œ๋‹ค ๊ฐ€์žฅ ๋งŽ์€ ๊ทค์˜ ์ข…๋ฅ˜๋ถ€ํ„ฐ ์ˆœํšŒํ•˜๋ฉด์„œ k๋ฅผ ๊ทค์˜ ๊ฐœ์ˆ˜๋งŒํผ ๊ฐ์†Œ์‹œํ‚ค๊ณ , answer์— 1์„ ๋”ํ•œ๋‹ค k๊ฐ€ 0 ์ดํ•˜๊ฐ€ ๋˜๋ฉด ์ˆœํšŒ๋ฅผ ์ข…๋ฃŒํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์  ์ฐ๊ธฐ (L2)
๐Ÿง  Algorithm
1import math 2 3def solution(k, d): 4 answer = 0 5 6 for x in range(0, d+1, k): 7 a = math.floor((d**2-x**2)**0.5) // k + 1 8 answer += a 9 10 return answer ๋ฌธ์ œ 2์ฐจ์› ์ขŒํ‘œ ํ‰๋ฉด์—์„œ (xk (x=0,1,2,3…), yk (y=0,1,2,3…)) ์ง€์ ์— ์ ์„ ์ฐ๋Š”๋‹ค ์›์ ๊ณผ์˜ ๊ฑฐ๋ฆฌ๊ฐ€ d๊ฐ€ ๋„˜์œผ๋ฉด ์ ์„ ์ฐ์ง€ ์•Š๋Š”๋‹ค k์™€ d๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์ ์ด ์ด ๋ช‡ ๊ฐœ ์ฐํžˆ๋Š”์ง€ ๊ตฌํ•˜๋ผ TC input k:2, d:4 ouput 6 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ๋ฐ˜์ง€๋ฆ„์ด d์ธ ์›์•ˆ์— (k์˜ ๋ฐฐ์ˆ˜, k์˜ ๋ฐฐ์ˆ˜)์ ์„ ๋ช‡ ๊ฐœ ์ฐ์„ ์ˆ˜ ์žˆ๋Š”์ง€ ๊ตฌํ–ˆ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋””ํŽœ์Šค ๊ฒŒ์ž„ (L2)
๐Ÿง  Algorithm
1import heapq 2 3def solution(n, k, enemy): 4 heap = [] 5 cnt = 0 6 for i in enemy: 7 n -= i 8 heapq.heappush(heap, -i) 9 while n < 0: 10 k -= 1 11 if not heap or k < 0: 12 return cnt 13 tmp = -heapq.heappop(heap) 14 n += tmp 15 cnt += 1 16 return cnt ๋ฌธ์ œ n: ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ณ‘์‚ฌ ์ˆ˜ k: ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๋ฌด์ ๊ถŒ ์Šคํ‚ฌ ์ˆ˜ enemy: ๋ผ์šด๋“œ๋งˆ๋‹ค ์กด์žฌํ•˜๋Š” ์  ์ˆ˜์˜ ๋ฐฐ์—ด ๋ผ์šด๋“œ๋งˆ๋‹ค enemy[i]๋ช… ๋งŒํผ ์†Œ๋ชจํ•˜์—ฌ enemy[i]๋งˆ๋ฆฌ์˜ ์ ์„ ๋ง‰์„ ์ˆ˜ ์žˆ๋‹ค ๋ฌด์ ๊ถŒ์„ ์ ์ ˆํžˆ ์‚ฌ์šฉํ•˜์—ฌ ๋ฒ„ํ‹ธ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๋ผ์šด๋“œ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ผ TC input n: 7, k: 3, enemy: [4, 2, 4, 5, 3, 3, 1] ouput 5 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• enemy๋ฅผ ์ˆœํšŒํ•˜๋ฉด์„œ ํž™์— ๋ณ‘์‚ฌ ์ˆ˜๋ฅผ ์ €์žฅํ•˜๋ฉด์„œ, ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ณ‘์‚ฌ๋ฅผ ์†Œ๋ชจํ•œ๋‹ค ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ๋ณ‘์‚ฌ ์ˆ˜๊ฐ€ ์Œ์ˆ˜๊ฐ€ ๋˜๋ฉด ๊ฐ€์žฅ ๋ณ‘์‚ฌ๊ฐ€ ๋งŽ์€ ๋ผ์šด๋“œ์—์„œ ๋ฌด์ ๊ถŒ์„ ์‚ฌ์šฉํ•œ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํ…Œ์ด๋ธ” ํ•ด์‹œ ํ•จ์ˆ˜ (L2)
๐Ÿง  Algorithm
1def solution(data, col, row_begin, row_end): 2 answer = 0 3 data.sort(key=lambda x: (x[col-1], -x[0])) 4 s = [] 5 for i in range(row_begin-1, row_end): 6 s.append(sum(map(lambda x: x%(i+1), data[i]))) 7 8 for i in s: 9 answer ^= i 10 return answer ๋ฌธ์ œ ํ•ด์‹œ ํ•จ์ˆ˜๋Š” col, row_begin, row_end์„ ์ž…๋ ฅ์œผ๋กœ ๋ฐ›๋Š”๋‹ค ํ…Œ์ด๋ธ”์˜ ํŠœํ”Œ์„ col๋ฒˆ์งธ ์ปฌ๋Ÿผ์˜ ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ์˜ค๋ฆ„์ฐจ์ˆœ ์ •๋ ฌ์„ ํ•˜๋˜, ๋งŒ์•ฝ ๊ทธ ๊ฐ’์ด ๋™์ผํ•˜๋ฉด ๊ธฐ๋ณธํ‚ค์ธ ์ฒซ ๋ฒˆ์งธ ์ปฌ๋Ÿผ์˜ ๊ฐ’์„ ๊ธฐ์ค€์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ ์ •๋ ฌํ•œ๋‹ค ์ •๋ ฌ๋œ ๋ฐ์ดํ„ฐ์—์„œ S_i๋ฅผ i ๋ฒˆ์งธ ํ–‰์˜ ํŠœํ”Œ์— ๋Œ€ํ•ด ๊ฐ ์ปฌ๋Ÿผ์˜ ๊ฐ’์„ i ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋“ค์˜ ํ•ฉ์œผ๋กœ ์ •์˜ํ•œ๋‹ค row_begin โ‰ค i โ‰ค row_end ์ธ ๋ชจ๋“  S_i๋ฅผ ๋ˆ„์ ํ•˜์—ฌ bitwise XOR ํ•œ ๊ฐ’์„ ํ•ด์‹œ ๊ฐ’์œผ๋กœ์„œ ๋ฐ˜ํ™˜ํ•˜๋ผ TC input data: [[2,2,6],[1,5,10],[4,2,9],[3,8,3]] col: 2, row_begin: 2, row_end: 3 ouput 4 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ๊ตฌํ˜„ํ•ด์„œ ํ•ด๊ฒฐํ•˜์˜€๋‹ค lambda๋ฌธ์ด ๋งŽ์€ ์ฝ”๋“œ๋ฅผ ์ค„์—ฌ์ฃผ์—ˆ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋งˆ๋ฒ•์˜ ์—˜๋ฆฌ๋ฒ ์ดํ„ฐ (L2)
๐Ÿง  Algorithm
์ฒซ๋ฒˆ์งธ BFS ํ’€์ด 1from collections import deque 2 3def solution(storey): 4 answer = 0 5 q = deque() 6 q.append((storey, 0)) 7 visited = [False] * (10**8+1) 8 9 while q: 10 cur, cnt = q.popleft() 11 12 13 visited[cur] = True 14 while cur != 0 and cur%10 == 0: 15 cur = cur // 10 16 if cur == 0: 17 answer = cnt 18 break 19 for j in [-1, 1]: 20 dest = cur + j 21 if 0 <= dest <= 10**8 and not visited[dest]: 22 q.append((dest, cnt+1)) 23 24 return answer ๊ฐœ์„ ํ•œ DFS ํ’€์ด 1answer = 10**8 2def dfs(cur, cnt): 3 global answer 4 if cur == 0: 5 answer = min(answer, cnt) 6 return 7 while cur % 10 == 0: 8 cur /= 10 9 10 if cur%10 < 5: 11 dfs(cur//10, cnt+(cur%10)) 12 elif cur%10 > 5: 13 dfs(cur//10+1, cnt+(10-cur%10)) 14 else: 15 dfs(cur//10, cnt+(cur%10)) 16 dfs(cur//10+1, cnt+(10-cur%10)) 17 18def solution(storey): 19 dfs(storey, 0) 20 return answer ๋ฌธ์ œ ์ฃผ์ธ๊ณต ๋ฏผ์ˆ˜๋Š” ํ•œ๋ฒˆ ์—˜๋ ˆ๋ฒ ์ดํ„ฐ๋ฅผ ํƒ€๋ฉด -1, +1, -10, +10 ๋“ฑ ์ ˆ๋Œ“๊ฐ’์ด $10^c$ (c>=0์ธ ์ •์ˆ˜) ๋งŒํผ ์ด๋™ ํ•  ์ˆ˜ ์žˆ๋‹ค 0์ธต๊นŒ์ง€ ๊ฐˆ๋ ค๋ฉด ์ตœ์†Œ ๋ช‡ ๋ฒˆ ๋งŒ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š”์ง€ ๊ตฌํ•˜๋ผ 1 <= storey <= 100,000,000 TC input 16 ouput 6 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ์ฒ˜์Œ์—๋Š” bfs๋ฅผ ์ด์šฉํ•ด์„œ +1, -1 ํ•œ๋ฒˆ์”ฉํ•˜๋ฉฐ ๋น„ํšจ์œจ์ ์œผ๋กœ ํ•ด๊ฒฐํ•˜์˜€๋‹ค ๋‘๋ฒˆ์งธ dfsํ’€์ด์—์„œ๋Š” ์ผ์˜ ์ž๋ฆฌ์— ๋”ฐ๋ผ ์ž๋ฆฟ์ˆ˜๋ฅผ ์˜ฌ๋ฆฌ๊ฑฐ๋‚˜ ๋‚ด๋ฆฌ๊ณ , ์ผ์˜ ์ž๋ฆฌ๋ฅผ ํ•œ๋ฒˆ์— ๊ณ„์‚ฐํ•˜์—ฌ ๋” ๋‚˜์€ ํ’€์ด๋กœ ํ’€ ์ˆ˜ ์žˆ์—ˆ๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ด๋ชจํ‹ฐ์ฝ˜ ํ• ์ธํ–‰์‚ฌ (L2)
๐Ÿง  Algorithm
1result = [] 2 3def dfs(size, percent, users, emoticons): 4 global result 5 6 if len(percent) == size: 7 temp = [0] * len(users) 8 for i in range(size): 9 for j in range(len(users)): 10 if percent[i]*100 >= users[j][0]: 11 temp[j] += emoticons[i]*(1-percent[i]) 12 serviceNum = 0 13 income = 0 14 for i in range(len(users)): 15 if temp[i] >= users[i][1]: 16 serviceNum += 1 17 else: 18 income += temp[i] 19 result.append ((serviceNum, income)) 20 return 21 22 for i in [0.1, 0.2, 0.3, 0.4]: 23 dfs(size, percent+[i], users, emoticons) 24 25 26def solution(users, emoticons): 27 dfs(len(emoticons), [], users, emoticons) 28 result.sort(reverse=True) 29 return list(result[0]) ๋ฌธ์ œ ์นด์นด์˜คํ†ก ์‚ฌ์šฉ์ž n๋ช…์˜ ๊ตฌ๋งค ๊ธฐ์ค€์„ ๋‹ด์€ 2์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด users, ์ด๋ชจํ‹ฐ์ฝ˜ m๊ฐœ์˜ ์ •๊ฐ€๋ฅผ ๋‹ด์€ 1์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด emoticons๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ๊ฐ ์‚ฌ์šฉ์ž๋Š” ์ผ์ • ๋น„์œจ ์ด์ƒ ํ• ์ธํ•˜๋Š” ์ด๋ชจํ‹ฐ์ฝ˜์„ ๊ตฌ๋งคํ•œ๋‹ค ๊ฐ ์‚ฌ์šฉ์ž๋Š” ๊ตฌ๋งคํ•œ ์ด๋ชจํ‹ฐ์ฝ˜ ๊ฐ€๊ฒฉ์˜ ํ•ฉ์ด ์ผ์ • ๊ธฐ์ค€์„ ๋„˜์œผ๋ฉด ์ด๋ชจํ‹ฐ์ฝ˜ ๊ตฌ๋งค๋ฅผ ๋ชจ๋‘ ์ทจ์†Œํ•˜๊ณ  ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค์— ๊ฐ€์ž…ํ•œ๋‹ค ํ• ์ธ์œจ์€ 10%, 20%, 30%, 40% ์ค‘ ํ•˜๋‚˜์ด๋‹ค ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค์— ๊ฐ€์ž…์ž๋ฅผ ๋Š˜๋ฆฌ๋Š” ๊ฒƒ์„ ์ตœ์šฐ์„ ์œผ๋กœ ํ•˜๋ฉฐ, ์ด๋ชจํ‹ฐ์ฝ˜ ํŒ๋งค์•ก์„ ๋Š˜๋ฆฌ๋Š” ๊ฒƒ์„ ๋‘๋ฒˆ์งธ ๋ชฉํ‘œ๋กœ ํ–ˆ์„ ๋•Œ์˜ ์ด๋ชจํ‹ฐ์ฝ˜ ํ”Œ๋Ÿฌ์Šค ์„œ๋น„์Šค ๊ฐ€์ž…์ž ์ˆ˜์™€ ์ด๋ชจํ‹ฐ์ฝ˜ ๋งค์ถœ์•ก์„ 1์ฐจ์› ์ •์ˆ˜ ๋ฐฐ์—ด์— ๋‹ด์•„ ๋ฐ˜ํ™˜ํ•˜๋ผ TC input users: [[40, 10000], [25, 10000]], emoticons: [7000, 9000] ouput [1, 5400] ํ•ด๊ฒฐ๋ฐฉ๋ฒ• dfs๋ฅผ ์ด์šฉํ•ด์„œ ๋ชจ๋“  ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ์™„์ „ ํƒ์ƒ‰ํ•˜์—ฌ ํ•ด๊ฒฐํ•˜์˜€๋‹ค ํ• ์ธ์œจ์˜ ๊ฒฝ์šฐ์˜ ์ˆ˜๊ฐ€ 4๊ฐ€์ง€ ๋ฐ–์— ์—†์–ด์„œ ๊ฐ€๋Šฅํ–ˆ๋˜ ์ผ์ด๋‹ค
new ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ํƒ๋ฐฐ ๋ฐฐ๋‹ฌ๊ณผ ์ˆ˜๊ฑฐํ•˜๊ธฐ (L2)
๐Ÿง  Algorithm
1def solution(cap, n, deliveries, pickups): 2 answer = 0 3 tempD = 0 4 tempP = 0 5 for i in range(n-1, -1, -1): 6 tempD += deliveries[i] 7 tempP += pickups[i] 8 9 while tempD > 0 or tempP > 0: 10 tempD -= cap 11 tempP -= cap 12 answer += (i+1)*2 13 return answer ๋ฌธ์ œ ํŠธ๋Ÿญ์— ์‹ค์„ ์ˆ˜ ์žˆ๋Š” ์žฌํ™œ์šฉ ํƒ๋ฐฐ ์ƒ์ž์˜ ์ตœ๋Œ€๊ฐœ์ˆ˜ cap, ๋ฐฐ๋‹ฌํ•  ์ง‘์˜ ๊ฐœ์ˆ˜ n ํƒ๋ฐฐ ์ƒ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‹ด์€ deliveries, ์žฌํ™œ์šฉ ํƒ๋ฐฐ ์ƒ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ ๋‹ด์€ pickups๊ฐ€ ์ฃผ์–ด์ง„๋‹ค ํŠธ๋Ÿญํ•˜๋‚˜๋กœ ๋ชจ๋“  ๋ฐฐ๋‹ฌ๊ณผ ์ˆ˜๊ฑฐ๋ฅผ ๋งˆ์น˜๊ณ  ๋Œ์•„์˜ฌ ์ˆ˜ ์žˆ๋Š” ์ตœ์†Œ ์ด๋™ ๊ฑฐ๋ฆฌ๋ฅผ ๊ตฌํ•˜๋ผ TC input (cap, n, deliveries, pickups) 4, 5, [1, 0, 3, 1, 2], [0, 3, 0, 4, 0] ouput 16 ํ•ด๊ฒฐ๋ฐฉ๋ฒ• ๋ฐฐ์—ด์„ ๊ฑฐ๊พธ๋กœ ์ˆœํšŒํ•˜๋ฉด์„œ ๋ฐฐ๋‹ฌ, ์ˆ˜๊ฑฐ ์ƒ์ž์˜ ์ˆ˜๋ฅผ ๋”ํ•œ๋‹ค ํ•ด๋‹น ๊ฐ’์ด 0๋ณด๋‹ค ํฌ๋ฉด ํŠธ๋Ÿญ์— ์‹ค์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ ๊ฐœ์ˆ˜์ธ cap์„ ๋นผ์ฃผ๊ณ  ๊ฑฐ๋ฆฌ๋ฅผ ๊ณ„์‚ฐํ•ด์ค€๋‹ค
  • ««
  • «
  • 8
  • 9
  • 10
  • 11
  • 12
  • »
  • »»
๐Ÿง  Algorithm (104) ๐ŸŒŠ C/CPP (2) โ˜• Java (8) ๐ŸŒ Javascript (9) ๐Ÿ Python (9) ๐Ÿƒ Spring (30) ๐Ÿ”จ ๊ฐœ๋ฐœ ๋„๊ตฌ (2) ๐ŸŽธ ๊ธฐํƒ€ (7) ๐Ÿ‘จโ€๐Ÿ’ป ๋ชจ๊ฐ์ฝ” (38) ๐Ÿค– ์ธ๊ณต์ง€๋Šฅ (2) ๐Ÿซ ํ•™๊ณผ ๊ณต๋ถ€ (28)
๐Ÿท๏ธ boj (53) ๐Ÿท๏ธ c (5) ๐Ÿท๏ธ c++ (4) ๐Ÿท๏ธ celery (2) ๐Ÿท๏ธ cs (18) ๐Ÿท๏ธ django (3) ๐Ÿท๏ธ docker (2) ๐Ÿท๏ธ docker compose (1) ๐Ÿท๏ธ elk (1) ๐Ÿท๏ธ fastapi (4) ๐Ÿท๏ธ git (2) ๐Ÿท๏ธ github actions (5) ๐Ÿท๏ธ hackerrank (3) ๐Ÿท๏ธ https (2) ๐Ÿท๏ธ java (37) ๐Ÿท๏ธ javascript (2) ๐Ÿท๏ธ jwt (1) ๐Ÿท๏ธ kubernetes (4) ๐Ÿท๏ธ nginx (2) ๐Ÿท๏ธ ocaml (1) ๐Ÿท๏ธ open source (2) ๐Ÿท๏ธ programmers (48) ๐Ÿท๏ธ pytest (1) ๐Ÿท๏ธ python (111) ๐Ÿท๏ธ rabbitmq (2) ๐Ÿท๏ธ rag (3) ๐Ÿท๏ธ react (6) ๐Ÿท๏ธ security (3) ๐Ÿท๏ธ software-engineering (3) ๐Ÿท๏ธ spring (31) ๐Ÿท๏ธ sql (5) ๐Ÿท๏ธ ssl (1) ๐Ÿท๏ธ testing (4) ๐Ÿท๏ธ typescript (1) ๐Ÿท๏ธ vercel (1) ๐Ÿท๏ธ websocket (1)